隔板法 学习笔记
前言 $2019.10.19$就$CSP$第一轮了(好慌 隔板法定义 在组合数学中,隔板法(又叫插板法)是排列组合的推广,主要用于解决不相邻组合与追加排列的问题。 隔板法就是在$n$个元素间插入$(b-1)$个板,即把$n$个元素分成$b$组的方法。——百度百科 普通隔板法 经典问题:求$x+y+z=10$的正整数解的个数。 这个问题与此问题相同:…
exgcd学习笔记
前言 今天膜你赛竟然要套$exgcd$ gcd [crayon-5db07714748db891501207/] exgcd 形如$ax+by=c$的方程,当$gcd(a,b)|c$时,存在整数解$x,y$。 也就是说$exgcd$可以解$ax+by=gcd(a,b)$的方程。 令$a=b,b=a\mod b$,那么$bx+a\mod b\time…
2019.10.6 CSP-S模拟赛T1
前言 考完以后感觉炸了,结果还好(大雾,竟然没有垫底 5+80+20=105(21/52) 题意 对于任意的$1\leq k \leq N$,求有多少个恰好有$k$个叶子节点的二叉树,满足每个节点要么没有子节点,要么有两个子节点,同时不存在一个叶子节点,使得根到它的路径上有不少于$M$条向左的边。 答案对$998244353$取模。 思路 此题发下…
BSGS&exBSGS 学习笔记
写在前面 在某次集训比赛时遇到了$esBSGS$毒瘤题,被大佬们暴捶,过了一个多月本蒟蒻才开始学习$BSGS\text{&}exBSGS$ BSGS $BabyStepGiantStep$算法,即大步小步算法,缩写为$BSGS$,而$esBSGS$,顾名思义,就是$BSGS$的拓展。 $BSGS$用来解决如下问题: 给定一个质数$P(2\l…
2019.9.15 CSP-S模拟赛
前言 一大波原题来袭!!!(大雾 考得不太好吧0+100+0=100(T3数据出锅了 T1-P5424 [USACO19OPEN]Snakes 题意 有$n$组蛇,每一组蛇有$a_i$条蛇,你有一张网,需要将蛇全部抓住。一次抓一组蛇,因此每次要使网比当前组的蛇的数量大。你可以改变$k$次网的大小,问抓住所有蛇的总浪费空间的最小值? 对于$100 \…
三校集训Part2 NBCX Day11 bracket 题解
题意 现在有一个长度为$ n $且合法的括号序列,每次询问将会翻转其中一个括号(左括号与右括号互相变换),你要对于每个询问,再翻转一个括号(可以与讯问中的相同),使得括号序列仍旧合法,且翻转的位置尽量靠前。 询问和回应的效果都是是叠加的,也就是括号序列在某个询问后,会按照询问和回应永久改变。 对于$100\text{%}$的数据,满足$ 2 \le…
三校集训Part2 NBCX Day8 Cloud 题解
题意 给出每个云的位置及大小以及移动方向,它们的移动速度均为$1$个单位长度每单位时间,在时刻0,所有的云没有重叠,问在所有时刻中(从负无穷到正无穷)中,云重叠层数最多是多少? 思路 非常显然,答案只有可能是$1$或$2$。 所以,直接$rand()\text{%}2$(逃: 咳咳,进入正题。 所以只要能判断是不是能有一片横着走的云和一片竖着走的云…
Luogu P3515 [POI2011]Lightning Conductor 题解
题意 题目传送门 已知一个长度为$n$的序列$a_1,a_2,...,a_n$。 对于每个$1\leq i\leq n$,找到最小的非负整数$p$满足 对于任意的$j$,$ a_j \leq a_i + p - \sqrt{| i-j | }$ 思路 首先先把题目中的式子化简一下: $p\geq a_j+\sqrt{|i-j|}-a_i$ 原来就是…
三校集训Part2 NBCX Day7 timegate 题解
题意 原题链接 订正链接 构造一个图,图的所有边权等于$1$,求使$1$到$n$的最短路距离为$k$的方案数。 对于$ 100\text{%}$的数据$n,k \leq 100$ 思路 (为了图(wo)方(tai)便(cai),下文的$m$代表上文题意中的$k$,下文的$k$详见下文) 考虑$dp$。 因为这张图的最短路距离为$k$,所以考虑分层图…
三校集训Part2 NBCX Day3 course 题解
题意 神秘男子的学校安排了$ N $门课,每门从时间$ start_i $上到时间$ end_i$。神秘男子一次只能上一门课。神秘男子想法很多,他想知道$ Q $个时间段$ planstart_j $到$ planend_j $内, 他分别最多上几节课。 对于$100\text{%}$的数据,$1\leq N,Q \leq 10^5,0\leq s…
三校集训Part2 NBCX Day2 XVII 题解
题意 有$n$个长度为$32$的只包含小写字母的字符串,问每个字符串读入时它之前有没有出现过? 输出$n$行,每行输出$Yes$或$No$。 时间限制:$6s$ 空间限制:$2M$ 思路 出题人好心地帮我们把$2M$标红了... 考虑使用$map$,虽然$map$的准确性高,但是不仅常数大(但出题人好心地给了$6s$)空间上也会$MLE$。 考虑使…
三校集训Part1 QZEZ Day6 B 题解
题意 一只萌萌的$ Galo $在沙滩上散步。突然,可怕的事情发生了!一只$ OvO $正在看着他! 为了逃脱被吃掉的命运,$Galo $稽中生智,扔出了自己研究了很久的一道题给昆西: 斐波那契数列是这样的一个数列 $F_0 = 1, F_1 = 2$ $F_i = F_{i−1} + F_{i−2}$ 对于一个数,Galo 定义它的斐波那契表示为…
三校集训Part1 QZEZ Day2 A洗牌 题解
题意 无聊的时间,小$ K $喜欢和他的室友们一起打扑克(这副扑克很神奇,上面写着$ 1 $到$ n $的数字各一张),打扑克前当然要先洗牌啦。 宿舍洗牌的方式十分简单,先将所有牌平均分成两份,然后交叉地混合到一起,举个例子,六张牌$ 1$ $ 2$ $3$ $ 4 $ $5 $ $6$ 在混合后后会变成 $1$ $4$ $2$ $5 $ $ 3$…
三校集训Part1 QZEZ 2019.7.15~2019.7.26
Day0 没想到窝又来集训了,其实这个Day0与绍兴集训的Day10是连在一起的。╮(╯▽╰)╭ 三校集训,故名思议就是三个学校的人一起集训(逃: 哪三个学校呢?当然是:qzez,cixi,yiwu Day1 一觉醒来已经是$7:30$,早饭在自己家里吃,中饭在食堂吃,菜还可以,但窝太菜点了一种最难吃的。。。上午讲题,是$zyr$巨佬讲的,我听得聚…
绍兴游记Day8 b 题解
Link 官方题目传送门 官方题解传送门 题意 $Hzy$有一个集合,一开始有$[0\dots a]$这些数字(如果$a=-1$则说明集合为空)。接下来有$m$个时刻,每个时刻都会有一种操作。 1. 插入一个数字$x$,保证$x$不在集合中。 2. 删去一个数字$x$。 3. 把目前不在集合中的最早被删除的数字,插回到集合中(如果一个数字曾经被删去…
绍兴游记Day1 b 题解
题面 【问题描述】 ξ成为了赛车手,但是她发现她没有实战经验。每参加一场赛车比赛她会获得$a_i$的经验,假设参加完这场比赛后她的总经验是$E$,那么她会获得$E ∗ b_i$的奖金。 ξ要参加的比赛场数是偶数,在参加完恰好一半的比赛后她会参加一个夏令营去练习飙车,这次夏令营会给她$X$点经验但是没有奖金。 ξ想知道如何合理安排参加比赛的顺序可以使…
绍兴游记2019.7.4-2019.7.14
Day0 来到绍兴花了$4$小时,吐槽司机...... 晚餐在浙江越秀外国语学院(镜湖校区)内的酒店里吃的,$30$元的快餐感觉还不如$3$元的方便面。 晚上认真学习了emmmm.....(心疼我的3.0GB流量)顺便吐槽一下酒店的$WIFI$,没连上就算了,好不容易连上了,最高网速$20KB/s$还不如不连呢。 晚上12:00准时睡觉 Day1 …
NOIP2019模拟赛(十)06.02
Link NOIP2019模拟赛(十)06.02 A. transfer 题意 有$n$个小孩,他们会进行$t$轮游戏。一开始,鲜花在第一个孩子手里,每轮游戏持有鲜花的小孩可以把鲜花传递给除了自己以外的任意一个小孩。那么,一共有多少种传递方法,可以让鲜花在游戏结束时回到第一个小孩上呢? 对于$100$%的数据,$n,t \leq 10^{18}$ …
Luogu P3232 [HNOI2013]游走 题解
题意 在一个无向图中,小$Z$以$1$为起点,每次以相等的概率选择当前顶点的某条边,沿着这条边走到下一个顶点,获得等于这条边的编号的分数。当小$Z$走到$N$(即终点),结束了这次游走,总得分为游走时经过的每一条边的编号之和。现在,请你对这$M$条边进行编号,使得小$Z$获得的总分的期望值最小。 输入保证: 1. $30$%的数据满足$N<=…
10188. 「一本通 5.6 练习 1」玩具装箱
Link 题意 你可以将一段连续的玩具扔到同一个容器中,如果要将 $i$ 号玩具到 $j$ 号玩具 $(i\le j)$ 放到同一个容器中,则容器长度不小于 $x=j-i+ \displaystyle\sum_{k=i}^{j}C_k$制作容器的费用与容器的长度有关,根据教授研究,如果容器长度为 $x$,其制作费用为 $(X-L)^2$,其中 $L…
B 酱的无向图 题解
[mdx_warning]本题目有版权,禁止复制[/mdx_warning] 题目描述 B 酱有$n$个节点的无向图,初始时图中没有边。他依次向图中加入了$m$条无向边,并询问你加入每条边后图中桥的个数是多少。被删除后能使图中连通块个数增加的边就称为桥。注意图中可能会出现重边及负环。 输入格式 输入第一行为三个正整数$n,m, p, p $的含义将…
10152. 「一本通 5.1 练习 3」矩阵取数游戏
题意 帅帅经常和同学玩一个矩阵取数游戏: 对于给定的 $n\times m$ 的矩阵,矩阵中每个元素 $a_{ij}$ 均为非负整数。游戏规则如下: 1. 每次取数时必须从每行各取走一个元素,共 $n$ 个,$m$ 次取完所有元素。 2. 每次取走的各个元素只能是该元素所在行行首或行尾。 3. 每次取数都有一个的分值,为每行取数得分之和,每行取数得…
EK (Edmond-Karp) 算法 学习笔记
什么是EK算法 EK (Edmond-Karp) 算法,说白了就是求最大流/费用流之类的问题的算法。 什么是最大流 定义 带权的有向图$G=(V,E)$,满足以下条件,则称为网络流图$(flow network)$: 仅有一个入度为$0$的顶点$s$,称$s$为源点。仅有一个出度为$0$的顶点$t$,称$t$为汇点。每条边的权值都为非负数,称为该边…
NOIP2019模拟赛(五)03.31 解题报告
Link NOIP2019模拟赛(五)03.31 A. 「NOIP模拟赛」电阻 题意 询问要得出一个电阻值为$\frac{a}{b}$的元件至少需要多少个电阻值为$1$的电阻。 元件由$3$种方式组成: 一个电阻 一个元件与一个电阻串联 一个元件与一个电阻并联 思路 并联电阻阻值计算 总电阻值为:$总R_总=\frac{1}{\frac{1}{R_…
Codeforces Gym 101002 H. Jewel Thief 题解
题意 类似于一个背包,空间为$M$,有$N$个物品,第$i$个物品体积为$w_i$,价值为$c_i$,求价值之和的最大值。 其中,$1 \leq n \leq 100000$,$1\leq m \leq 300000$,$1\leq w_i \leq 3$,$1\leq c_i \leq {10}^9$ 思路 首先注意到$n,m$非常大,所以普通的…
10238. 「一本通 6.6 练习 9」网格
题意 某城市的街道呈网格状,左下角坐标为 $A(0, 0)$,右上角坐标为 $B(n, m)$,其中 $n \ge m$。现在从 $A(0, 0)$ 点出发,只能沿着街道向正右方或者正上方行走,且不能经过图示中直线左上方的点,即任何途径的点 $(x, y)$ 都要满足 $x\ge y$,请问在这些前提下,到达 $B(n, m)$ 有多少种走法。 思…
「NOIP模拟赛」欧拉口算 题解
题目描述 令 $C(n)$ 表示 把 $n$ 拆分成 $a\times b=n(a\leq b)$ 且 $a,b$ 的因子个数相同的方案数 给定一个整数$n$,$(1 \leq n \leq 100)$。 求出$C(n!)$。 思路 先把$n!$拆成若干个质数的乘积。 即:$n!={p_1}^{c_1} \times {p_2}^{c_2} \ti…
10166. 「一本通 5.3 练习 1」数字游戏
题意 给定多组数据,每组数据给定三个数:$a,b,n$表示求在区间$[a,b]$内各位数之和模$n=0$的数的个数。 思路 这是一道数位$DP$的模板题。 设$f[i][S]$表示处理到第$i$位,$S$为和。 $f[i][S]=f[i-1][(S+i)%N](0<=k<=Dim[i] or 9)$ 其中$k$的取值范围根据上一位的状态…
NOIP2019模拟赛(二)03.10
T1 题意 题面 给定两个数$a$,$b$求出$b$个$a$相乘的结果。 数据范围 保证$a \leq 99.9999 ,b \leq 25$且$a$的有效数字不超过$6$位。 思路 对于20%的数据 你开$long\quad double$就好了呀。 对于100%的数据 你写高精度就好了呀。 说得很轻巧,但是打比赛的时候花了30分钟。。。 差不多…
10213. 「一本通 6.4 例 5」Strange Way to Express Integers
题意 给定 $2n$ 个正整数 $a_1,a_2,\cdots ,a_n$ 和 $m_1,m_2,\cdots ,m_n$,求一个最小的正整数 $x$,满足 $\forall i\in[1,n],x\equiv a_i\ (\bmod m_i\ )$,或者给出无解。 思路 其实题意就是求出: $x\equiv a[1] \bmod m[1]…
10181. 「一本通 5.5 练习 2」绿色通道
题意 高二数学《绿色通道》总共有 $n$ 道题目要抄,编号 $1\dots n$,抄第 $i$ 题要花 $a_i$ 分钟。小 Y 决定只用不超过 $t$ 分钟抄这个,因此必然有空着的题。每道题要么不写,要么抄完,不能写一半。下标连续的一些空题称为一个空题段,它的长度就是所包含的题目数。这样应付自然会引起马老师的愤怒,最长的空题段越长,马老师越生气。…
拓展欧几里得算法与应用
欧几里得算法 即:$gcd(a,b)=gcd(b,a$%$b)$ 欧几里得算法在oi里非常常用,几乎每个数学题都有欧几里得算法——$gcd$。 说白了就是求最大公约数。一行代码搞定: [crayon-5db0771492739332928076/] 拓展欧几里得算法 定理 定理1:设$a$和$n$不全为$0$,则存在整数$x,y$,满足$ax+by…
Luogu 2019三月月赛 P5239 回忆京都 题解
题意 题目背景讲太多了吧。。。一句话题意: 有$Q$个询问,每个询问求出: $$\sum_{i=1}^n\sum_{j=1}^m C_j^i$$ 对于$60$%的数据,$q \leq 10, n\leq100,m\leq100$。 对于$100$%的数据,$q \leq 1000,n\leq1000,m\leq1000$。 思路 对于60%的数据 …
10182. 「一本通 5.5 练习 3」理想的正方形
题意 有一个 $a\times b$ 的整数组成的矩阵,现请你从中找出一个 $n\times n$ 的正方形区域,使得该区域所有数中的最大值和最小值的差最小。 思路 设$dp[i][j][k]$表示以$i,j$为左上角的正方形变成为$k$内的最大值,$dp2[i][j][k]$表示最小值。 可知,$dp[i][j][k]=max(dp[i+1][j…
zkw线段树 学习笔记
前置知识 C++位运算学过线段树(其实关系不大) 什么是zkw线段树 就是一种线段树。(废话) 与普通线段树相比,zkw线段树更快、更短小。 本篇博客讲一个例题:Luogu P3372 普通线段树 zkw线段树 zkw线段树的实现 首先来看一看变量的定义与BuildTree操作 这是一棵求和的线段树(废话) 然后我们发现它有16个叶子节点。 而$1…
2240. 「CQOI2014」数三角形
三倍经验 LOJ #2240. 「CQOI2014」数三角形 BZOJ 3505: [Cqoi2014]数三角形 Luogu P3166 [CQOI2014]数三角形 (Luogu要大一些。。。) 题意 给定一个$n \times m$的网格,请计算三点都在格点上的三角形共有多少个。下图为$4 \times 4$的网格上的一个三角形。注意三角形的三…
主席树(静态) 学习笔记
在学习主席树之前 你必须学习: 线段树。 前缀和。 sort函数、unique函数以及lower_bound函数的使用方法。 什么是主席树 主席树又叫函数式线段树,又名可持久化线段树。所以主席树的名称与他的功能一点关系都没有。 主席树的时空复杂度为$O(n logn)$。 主席树的模板 由于主席树比较难理解,所以结合代码理解一下: [crayon-…
10137. 「一本通 4.4 练习 4」跳跳棋
题意 跳跳棋是在一条数轴上进行的。棋子只能摆在整点上。每个点不能摆超过一个棋子。我们用跳跳棋来做一个简单的游戏:棋盘上有三颗棋子,分别在 $a,b,c$ 这三个位置。我们要通过最少的跳动把他们的位置移动成 $x,y,z$(注意:棋子是没有区别的)。跳动的规则很简单,任意选一颗棋子,对一颗中轴棋子跳动。跳动后两颗棋子距离不变。一次只允许跳过一颗棋子。…
10187. 「一本通 5.6 例 4」Cats Transport
题意 小S养了$M$只猫,雇了$P$位饲养员。农场旁边有$N$座山,从$1$到$N$编号,第$i$座山与第$i-1$座山的距离为$D_i$,饲养员都住在$1$号山上。 有一天,第$i$只猫到第$H_i$座山玩,一直玩到$T_i$停止。饲养员们必须接回所有的猫,饲养员们行走的速度为$1$个单位每单位时间。 问如何计划每个饲养员从$1$号山出发的时间,…
10162. 「一本通 5.2 练习 5」骑士
题意 有$n$个骑士,每个骑士有一个自己的战斗值,每个骑士也有且仅有唯一一个自己讨厌的骑士,每个骑士不可能与自己讨厌的骑士一起上场战斗,问最高的战斗值之和是多少? 思路 这道题与没有上司的舞会很像。但是注意,这道题可能会有环的存在,所以我们需要对于每个环,把它切割成两部分,再分别树形dp,然后取最大值,加入ans中。 树形dp的思路很简单: 设$f…
10161. 「一本通 5.2 练习 4」叶子的染色
题意 给一棵有 $m$ 个节点的无根树,你可以选择一个度数大于 $1$ 的节点作为根,然后给一些节点(根、内部节点、叶子均可)着以黑色或白色。你的着色方案应保证根节点到各叶子节点的简单路径上都包含一个有色节点,哪怕是叶子本身。对于每个叶子节点 $u$,定义 $c_u$ 为从根节点到 $u$ 的简单路径上最后一个有色节点的颜色。给出每个 $c_u$ …
10206. 「一本通 6.3 练习 1」X-factor Chain
题意 输入正整数 $x$,求 $x$ 的大于 $1$ 的因子组成的满足任意前一项都能整除后一项的序列的最大长度,以及满足最大长度的序列的个数。 思路 题目读起来很困难?告诉你题目的实际意思。 给你一个数,要求你输出将这个数分解成因式相乘,并且后面一个因子至少是前面一个因子的2倍,问最长的因式相乘链有多长,有几条最长的因式相乘链。 为什么可以这样转化…
10204. 「一本通 6.3 例 2」Hankson 的趣味题
题意 已知正整数 $a_0,a_1,b_0,b_1$,设某未知正整数 $x$ 满足:1. $x$ 和 $a_0$ 的最大公约数是 $a_1$;2. $x$ 和 $b_0$ 的最小公倍数是 $b_1$。Hankson 的「逆问题」就是求出满足条件的正整数 $x$ 的个数。 思路 先从第二个条件入手。 $$lcm(x,b_0)=b_1$$ 因为$lcm…
10156. 「一本通 5.2 例 4」战略游戏
题意 有一座古城堡,里面的路形成一棵树, 某个士兵在一个节点上时,与该节点相连的所有边都将能被瞭望到。问最少需要多少士兵才可以使所有的路都被瞭望到。 输入数据表示一棵树,描述如下。 第一行一个数 $N$ ,表示树中节点的数目。 第二到第 $N+1$ 行,每行描述每个节点信息,依次为该节点编号 $i$,数值 $k$,$k$ 表示后面有 $k$ 条边与…
10230. 「一本通 6.6 练习 1」牡牛和牝牛
题意 牡 mǔ,畜父也。牝 pìn,畜母也。 ——《说文解字》 约翰要带 $N$ 只牛去参加集会里的展示活动,这些牛可以是牡牛,也可以是牝牛。牛们要站成一排,但是牡牛是好斗的,为了避免牡牛闹出乱子,约翰决定任意两只牡牛之间至少要有 $K$ 只牝牛。请计算一共有多少种排队的方法,所有牡牛可以看成是相同的,所有牝牛也一样,答案对 $5000011$ 取…
洛谷 P3419 [POI2005]SAM-Toy Cars题解
题目描述 Jasio 是一个三岁的小男孩,他最喜欢玩玩具了,他有n 个不同的玩具,它们都被放在了很高的架子上所以Jasio 拿不到它们. 为了让他的房间有足够的空间,在任何时刻地板上都不会有超过k 个玩具. Jasio 在地板上玩玩具. Jasio'的妈妈则在房间里陪他的儿子. 当Jasio 想玩地板上的其他玩具时,他会自己去拿,如果他想玩的玩具在…
CF293B Distinct Paths 题解
题意 给定一个$n\times m$的矩形色板,有kk种不同的颜料,有些格子已经填上了某种颜色,现在需要将其他格子也填上颜色,使得从左上角到右下角的任意路径经过的格子都不会出现两种及以上相同的颜色。路径只能沿着相邻的格子,且只能向下或者向右。 计算所有可能的方案,结果对 $1000000007 (10^9 + 7)$ 输入及输出格式 输入格式 第一…
洛谷 P1992 不想兜圈的老爷爷 题解
题目描述 一位年过古稀的老爷爷在乡间行走 而他不想兜圈子 因为那会使他昏沉 偶然路过小A发扬助人为乐优良传统 带上地图 想知道路况是否一定使他清醒 usqwedf补充:为了让欢乐赛充满欢乐 小A还想问你一些数学作业…… 输入输出格式 输入格式: 一行 n m k 表示乡间共有 n 个村庄 m 条道路 接下来 m 行 每行两个整数 x y 表示 村 …
CF2B The least round way 题解
题目传送门 题意(直接复制了QWQ) 题目描述 给定由非负整数组成的$n \times n$的正方形矩阵,你需要寻找一条路径: 以左上角为起点, 每次只能向右或向下走, 以右下角为终点 并且,如果我们把沿路遇到的数进行相乘,积应当是最小“round”,换句话说,应当以最小数目的0的结尾. 输入格式 第一行包含一个整数 $(2 \leq n \leq…
P4009 汽车加油行驶问题 题解
当然食用spfa啦。 但本蒟蒻不会分层。所以就二维spfa啦。 基本思路就是:一开始先把(1,1)点的状态扔进队列。 然后分类讨论 详细见代码 丑陋无比的代码: [crayon-5db07714a6e0b729562916/]
洛谷P1331 海战 题解
题目传送门 思路 肯定食用dfs啦。。。 但关键是两条船接触了怎么判断呢?? 上图: 可以发现一下规律 当两条船接触时,必有一条直线连续穿过两条船 当一条船不与另一条船接触时,没有一条直线连续穿过两条船 所以只需要在每一次碰见一条船的一部分(一条船内每个点都要拓展一遍)时,将其沿右上、左下分别拓展一遍,边拓展边用sum前缀和check一遍就好啦。。…
10082. 「一本通 3.3 例 1」Word Rings
题意 每组数据读入一个n和n个字符串。定义前2个与末尾2个字母相同可以连接。问使这个环串的平均长度最大。求这个最大值。不存在输出No solution。 思路 平均值公式: $$Average=(E_1+E_2+…..+E_n)/n$$ $$Average*n=(E_1+E_2+…+E_n)$$ $$(E_1-Average)+(E_2-Avera…
10086. 「一本通 3.3 练习 3」Easy SSSP
题意 给你一个图,问从源点到每个节点的最短路径分别是多少。 如果存在负权回路,只输出一行 -1;如果不存在负权回路,再求出一个点 S 到每个点的最短路的长度。如果 S 与这个点不连通,则输出 NoPath。 思路 当然食用spfa啦。 先跑一下非源点的。万一数据卡你其他有环呢? 然后再跑一次源点。得出Ans [crayon-5db07714aa3c…
10087. 「一本通 3.4 例 1」Intervals
题意 从$0\sim 5\times 10^4$中选出尽量少的整数,使每个区间$ [a_i,b_i]$内都有至少 $c_i$个数被选出。 思路 当然食用spfa啦。 设s[k]表示0~k中至少选多少个整数。根据题意可得: $$s[b_i]-s[a_i-1]\geq c_i$$ $$s[k]-s[k-1]\geq0$$ $$s[k]-s[k-1]\l…
10088. 「一本通 3.4 例 2」出纳员问题
题意 R(0)、R(1)、R(2)…R(23)表示第x个时刻需要R(x)个出纳员,有n个出纳员申请工作,第i个出纳员从t_i时刻开始工作8小时,问至少需要多少出纳员? 思路 设$x[i]$表示第$i$时刻实际上需要雇佣$x[i]$人,$r[i]$为第$i$时刻至少需要$r[i]$个人。 $$x[i-7]+x[i-6]+x[i-5]+x[i-4]+x…
10089. 「一本通 3.4 练习 1」糖果
题意 满足条件: 如果 X=1.表示第 A 个小朋友分到的糖果必须和第 B 个小朋友分到的精果一样多。 如果 X=2,表示第 A 个小朋友分到的糖果必须少于第 B 个小朋友分到的糖果。 如果 X=3,表示第 A 个小朋友分到的糖果必须不少于第 B 个小朋友分到的糖果。 如果 X=4,表示第 A 个小朋友分到的糖果必须多于第 B 个小朋友分到的糖果。…
10090. 「一本通 3.4 练习 2」布局 Layout
题意 有些奶牛是好基友,它们希望彼此之间的距离小于等于某个数。有些奶牛是情敌,它们希望彼此之间的距离大于等于某个数。 思路 如果两只奶牛是好基友,那么: $$A-B\leq D$$ 如果两只奶牛是情敌,那么: $$A-B\ge D$$ 即: $$D\leq A-B$$ 也就是: $$B-A\leq -D$$ 直接上代码: [crayon-5db07…
10117. 「一本通 4.1 练习 2」简单题
题意 有一个 $n$ 个元素的数组,每个元素初始均为 $0$。有 $m$ 条指令,要么让其中一段连续序列数字反转——$0$ 变 $1$,$1$ 变 $0$(操作 $1$),要么询问某个元素的值(操作 $2$)。 思路 当然是树状数组啦。。。 这里介绍C++的一大利器——位运算。 &在C++里叫做与运算。应该差不多吧。。大概就是这样的:(按一…
10121. 「一本通 4.2 例 3」与众不同
题意 定义完美序列:一段连续的序列满足序列中的数互不相同。 想知道区间 $[L,R]$ 之间最长的完美序列长度。 思路 设$las[x]$表示盈利$x$最近出现位置。 设$st[i]$表示以第$i$个数结尾的最长完美序列的起始位置。 $$st[i]=max(st[i-1],las[a[i]]+1)$$ 设$f[i]$表示以第$i$个数结尾的最长完美…
2597. 「NOIP2011」选择客栈
题意 有$n$个客栈,每个客栈都配有咖啡馆。有两名旅客想住在同色调的客栈中,又想在两客栈之间的咖啡馆中小聚,咖啡馆的价钱不能高于$p$。 对于 $100\%$ 的数据,有 $2\leq n\leq2\times 10^6$,$0<k\leq10^4$ ,$0\leq p\leq100$,$0\leq$ 最低消费 $\leq100$ 。 思路 …
10128. 「一本通 4.3 练习 2」花神游历各国
题意 每一次旅行中,花神会选择一条旅游路线,它在那一串国家中是连续的一段,这次旅行带来的开心值是这些国家的喜欢度的总和,当然花神对这些国家的喜欢程序并不是恒定的,有时会突然对某些国家产生反感,使他对这些国家的喜欢度 $\delta$ 变为 $\sqrt \delta$(可能是花神虐爆了那些国家的 OI,从而感到乏味)。 现在给出花神每次的旅行路线,…
10202. 「一本通 6.2 练习 5」樱花
题意 求不定方程: $$\frac{1}{x}+\frac{1}{y}=\frac{1}{n!}$$ 的正整数解 $(x,y)$ 的数目。 思路 $$\frac{1}{x}+\frac{1}{y}=\frac{1}{n!}$$ $$\frac{y}{xy}+\frac{x}{xy}=\frac{1}{n!}$$ $$\frac{x+y}{xy}=\…
10147. 「一本通 5.1 例 1」石子合并
题意 将 $n$ 堆石子绕圆形操场排放,现要将石子有序地合并成一堆。规定每次只能选相邻的两堆合并成新的一堆,并将新的一堆的石子数记做该次合并的得分。 请编写一个程序,读入堆数 $n$ 及每堆的石子数,并进行如下计算: 选择一种合并石子的方案,使得做 $n-1$ 次合并得分总和最大。选择一种合并石子的方案,使得做 $n-1$ 次合并得分总和最小。 思…
10153. 「一本通 5.2 例 1」二叉苹果树
题意 有一棵二叉苹果树,如果数字有分叉,一定是分两叉,即没有只有一个儿子的节点。这棵树共 $N$ 个节点,标号 $1$ 至 $N$,树根编号一定为 $1$。 我们用一根树枝两端连接的节点编号描述一根树枝的位置。一棵有四根树枝的苹果树,因为树枝太多了,需要剪枝。但是一些树枝上长有苹果,给定需要保留的树枝数量,求最多能留住多少苹果。 思路 设$f[i]…
10149. 「一本通 5.1 例 3」凸多边形的划分
题意 给定一个具有 $N$ 个顶点的凸多边形,将顶点从 $1$ 至 $N$ 标号,每个顶点的权值都是一个正整数。将这个凸多边形划分成 $N-2$ 个互不相交的三角形,试求这些三角形顶点的权值乘积和至少为多少。 思路 首先随便搞一个多边形: 然后给它顺时针每个顶点表上序号: 然后枚举$i,j$,要求:$i+1<j$,然后给$i,j$连一条线,分…
10106. 「一本通 3.7 例 2」单词游戏
题意 有 $N$ 个盘子,每个盘子上写着一个仅由小写字母组成的英文单词。你需要给这些盘子安排一个合适的顺序,使得相邻两个盘子中,前一个盘子上单词的末字母等于后一个盘子上单词的首字母。请你编写一个程序,判断是否能达到这一要求。如果能,请给出一个合适的顺序。多组数据。第一行给出数据组数 $T$,每组数据第一行给出盘子数量 $N$,接下去 $N$ 行给出…
10178. 「一本通 5.5 例 4」旅行问题
题意 John 打算驾驶一辆汽车周游一个环形公路。公路上总共有 $n$ 车站,每站都有若干升汽油(有的站可能油量为零),每升油可以让汽车行驶一千米。John 必须从某个车站出发,一直按顺时针(或逆时针)方向走遍所有的车站,并回到起点。在一开始的时候,汽车内油量为零,John 每到一个车站就把该站所有的油都带上(起点站亦是如此),…
树链剖分 算法学习
树你应该懂的吧o( ̄︶ ̄)o 学习树链剖分之前需要先学习:$dfs$、线段树(当然大佬们用树状数组代替线段树也可以O(∩_∩)O),据说一名普及+的$oier$应该都会呀 先来了解树链剖分的用处 Luogu题目传送门 已知一棵包含$N$个结点的树(连通且无环),每个节点上包含一个数值,需要支持以下操作: 操作1: 格式: 1 x y z 表示将树从…
博弈论之威佐夫博弈 算法学习
博弈论之威佐夫博弈 威佐夫博弈(Wythoff's game)是指的这样一个问题:有两堆各若干个物品,两个人轮流从任意一堆中取出至少一个或者同时从两堆中取出同样多的物品,规定每次至少取一个,至多不限,最后取光者胜利。 ——转自百度百科 就比如洛谷的P2252 取石子游戏就是威佐夫博弈的裸题。。。 威佐夫博弈的性质 首先,由题目可知,当这两堆石子一样…
缩点求强连通分量——Kosaraju算法 学习笔记
Kosaraju 算法学习 序 这星期捣鼓了一个新的算法——Kosaraju算法 今天分享给大家 简介 Kosaraju算法,其实与tarjan算法差不多。但是码量较小,容易记忆。其时间复杂度与tarjan算法一样,为O(n+m),所以,某种程度上来说Kosaraju可以替代tarjan算法。 算法思路 如果直接让我讲Kosaraju算法到底是基于…
fhq treap 学习笔记
序 今天心血来潮,来学习一下fhq treap(其实原因是本校有个OIer名叫fh,当然不是我) 简介 fhq treap 学名好像是“非旋转式treap及可持久化”。。。听上去怪怪的。其实就是可以代替LCT、BST等等码量很高的东东。 定义 [crayon-5db07714ba05e684016964/] 操作 最基本的操作 其实都不应该叫做操作…
矩阵快速幂 学习笔记
举例1:Fibonacci 题目传送门 题意 $$f[1]=1,f[2]=1,f[3]=2,f[4]=3 \dots f[n]=f[n-1]+f[n-2]$$那么输入$n$、$m$,求第n项Fibonacci的值$mod$ $m$,即$f[n]$ $mod$ $m$。$$1\leq n \leq 2 \times 10^9$$因为:$$f[i]=1…
欢迎来到yzx1798106406的博客
这是本博客的第一篇文章。本博客搭建于2019.2.14 12:20 。基于wordpress+Argon。 版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 3.0 许可协议。转载请注明出处!