做题记录

王熙文 · 2023-10-14 19:44:32 · 个人记录

博客分类：任务。

教练让写，火大。

格式为混乱邪恶。

难度为预估或实际的 CF 评级。

10.7

hte round 12 T1（*1700，最小生成树）：从小到大加边，感性理解一下连通块个数变成 gcd，直接算答案。upd on 11.2：关于证明，可以先证明若有 n 个数，每个数 x 连 (x+k)%n，最终会合并成 g=gcd(n,k) 个连通块。首先每条边的两个端点 %g 一定一样（加若干个 k 减若干个 n，都不会改变余数）。只需要证明所有 x%g 相等的 x 都在同一个连通块即可。反证，如果有 x=ag+c,y=bg+c 不在同一个连通块，可以推出 y+dn-x=ek 这个方程无解。ek-dn=(b-a)g。根据 exgcd，这个方程一定有解，矛盾。接下来要证明合并 n,k 后再加一个数 m 也可以这么做。合并 n,k 后，原来长度为 n 的序列每个数所在的连通块形如：1,2,...,g,1,2,...,g,... 这样，因此先让 m 模 g 答案一定不变。剩下的就是在 1,2,...,g 这里面操作了，连通块个数变成了 gcd(m%g,g)，而这个数等于 gcd(m,g)，得证。

hte round 12 T2（*2400，结论，容斥）：猜想答案为 max i-pi，之后枚举 max 得到每个 pi 的取值（后缀），从小到大计算答案。

10.8

CF925C（*2200，思维）：x<x^y 等价于 y 的最高位在 x 中为 0。可以发现最高位较低的插在最高位较高的不会影响最高位较高的位置的合法性，因此按照最高位从大到小排序，随便插入一下。

CF444E（*2700，二分，贪心）：二分，将边权大于等于二分值的边删掉，则每个点需要连向连通块外的点。应用 https://www.luogu.com.cn/discuss/704188 这个结论即可，但是这个结论我不会证明，不想管了。

10.9

zr round 1 T1（*1400，博弈论）：考虑先选 1，如果此时必败则第一次选令当前必败的那个数，这样也能包含 1。所以除了 m=0 其他情况都是 Alice 赢。

zr round 1 T2（*2400，dp，高斯消元）：注意到如果一个点的右下角有点与终止状态不相等，则这个点的具体值无意义。因此有意义的点组成了一个阶梯状，对这些阶梯暴力 dp 并高斯消元。

zr round 1 T3（*2500，多项式）：考虑枚举步数，维护当前步数下点的等价类，那么步数小于等于当前的答案为 [x^r]\prod(1+aix)。每次修改会将一个等价类拆成两个等价类，且只有 nm 次。考虑暴力记录多项式的系数，删除一个等价类可以认为这个等价类在最后加入，反方向撤销。

CF842E（*2800，树的直径，线段树）：注意到树的所有直径会相交在一个点或一条边，可以反证。而且新加一个点最多会移动一次。所以动态维护这个点，并使用 dfs 序维护有多少个点到这个点的距离达到最大值。

10.10

zr round 2 T1（*1500，构造）：易发现若 a<b+2 或 a=b+3 无解，其他的直接在一条链上加单点和一个菊花。

zr round 2 T2（*1700，二分，最短路）：二分，对于一个点希望走到这里的边数最小，因此 bfs 转移。

zr round 2 T3（*2700，结论，启发式合并）：若点数为偶数，答案为 n，否则为 n-1。因为对于一棵树可以从深到浅依次满足，对于一个连通块可以选一个生成树。枚举每一条边，检查删掉当前边产生的两个连通块是否满足。可以使用启发式合并大力记录较小的连通块。

CF1792E（*2400，暴力）：分解因数，对每个因数 x 二分出第一个大于等于 x/n 的因数，并暴力扫上去即可。不知道为什么复杂度对。

CF1795F（*2400，二分，dp）：二分，对每个点求出满足子树内的限制时需要向上的一条链最短可以向上多少个点。

CF1794E（*2400，dp，哈希）：本质要记录每个点与其他点距离组成的可重集。使用哈希记录，一个距离的哈希值为 base^dis，可使用换根 dp 求出。

10.11

zr round 3 T1（*1500，数据结构）：维护当前的每行、每列在最开始的矩形中是哪行、哪列。

zr round 3 T2（*2000，暴力）：大力枚举新的两个点和这四个点的权值。在 DAG 上按拓扑序从大到小放权值，检查是否全都能放下来。

zr round 3 T3（*2600，结论，dp）：发现最优解中每个点要么能看到要么贴上。考虑将问题转化成花 ai 的代价将当前点和对面的若干点覆盖，问最小代价。考虑最优解中按照下标位置从小到大放，如果一个点所在的行前面有没覆盖的，则当前在这一行覆盖的一个点没有意义。因此使用 dp 记录两行极长覆盖前缀，使用线段树优化。

10.12

zr round 4 T1（*2500，贪心）：评分是对我而言的，我完全不会做这种题。考虑将每个账号的参赛情况压成一个 0~15 的数。按照 popcount 从大到小贪心，能凑就凑即可。因为 popcount 越小越灵活。

zr round 4 T2（*1800，dp）：考虑 dp 记录一个点的子树内有 0/1 个度数大于 k 的点，特殊的，对于当前点条件是度数大于 k-1。直接转移。

zr round 4 T3（*2800，dp）：注意到 (1,1) 可以使 2a-b 相同的对满足条件的为一段后缀。发现如果一个对满足，一定存在一种方案使得每个对不同。证明考虑调整法，若有 (a,b),(a,c)，可以调整为 (a,b+c-1),(1,a)。设 ans i 表示 2a-b=i 时满足条件最小的 b，枚举每一个对更新答案。可以简单地优化掉 b 的枚举，只需枚举 a，而 a 只需枚举到根号。

CF1773D（*2600，网络流，二分图匹配）：注意到如果选的两个位置横坐标加纵坐标的奇偶性相同，则一定不合法，所以当 n>=2100 时答案一定为 1e6。否则先求出一组完美匹配，枚举第一个点，使用匈牙利算法 O(n) 调整出没有这个点的最大匹配。则答案为最大匹配中必定存在的点的个数。这是个经典问题，从不必定存在的点开始，找到这个点的邻居，则邻居的匹配的点不必定存在。而如果没找到，则这个点必定存在。因为如果不必定存在一定存在一个换边的路径但搜索时没找到。

10.13

CF1765G（*2600，交互）：考虑从左到右依次确定两个。随机一种查询，如果答案大于等于 2 则一定能找到答案。通过列出所有的方案还可以发现剩下的三种组合也有一种能找到答案。剩下的再使用一次询问即可，期望次数 1.5。因为两种查询一次能找到答案的互补，所以这样做是对的。

CF1765I（*2800，最短路）：限制可以转化为单点不能通过和一条横向的边不能通过。对于单点涉及到的每一条列上的每个点都建出一个点，那么相邻两列这些点的最短路即为直接走的最短路。总之直接建图即可，难度在于码量。

CF461E（*3000，dp，矩乘优化）：对于一个串 s，最小操作次数一定为每次能走就走得到的操作次数。设 dp i,s 表示 i 次操作，下一个字符为 s 的字符串最小长度。转移只涉及到 i-1，直接矩乘优化即可。

10.14

CF464E（*3000，最短路，主席树，分块）：直接使用主席树维护二进制即可。修改只会将 log 个区间变成 0，可以先处理出一个 0 的区间，每次直接将指针指向那个区间即可。我为了好写写了分块，思想是一样的。

10.16

zr round 5 T1（*1500，独立集）：最终图一定是若干条链组成，且当 a>=2 时链长度为 log，所以可以枚举。特判 a=1。

zr round 5 T2（*2200，dp，gcd）：暴力 dp 可以记录后三个数。gcd 具有结合律，所以可以记录最后一个数、最后两个数的 gcd、最后三个数的 gcd，也是可以转移的，而状态数减小了。

zr round 5 T3（*1800，暴力）：可以列出 min(b-a,|a-x|+|b-y|) 这样的式子。枚举 a，发现这两个数的函数分别是一个向上的斜线和一个先向下再向上的折线。那么一定存在一个分界点使得前面第一个函数优，后面第二个函数优。随便算一下。

10.17

zr round 6 T1（*1900，dp）：注意到交换操作只会交换 io，因为其他的不优于插入，可以先判掉。剩下的设 dp i,j 表示前 i 个字符产生一个长度为 j 的 noip 前缀的最小操作次数，可以根据操作转移。

zr round 6 T2（*1800，树状数组）：分讨当前点是从 (1,1) 怎么走下来的，随便用数据结构维护即可。

zr round 6 T3（*2500，dp，二项式反演）：首先 10^i%p 相等的可以视作一个，可以先求出 10^i%p=r 的个数，问题可以转化成在 k 位里放 0~9，使得总和为 m 的方案数。这个可以二项式反演，钦定 x 个位置超过了 9，先给这些位置减 10，剩下的方案数可以插板法算出来。

10.18

zr round 7 T1（*2100，思维）：考虑枚举第一个左括号的位置，发现如果这个括号一直到最后，则剩下的地方有一种方案可以使除了这个左括号后面连续的正数，其他数都取到正的，所以如果这个括号走过了连续的正数一定不如走到最后。如果没走过，则一定不如不添加。这样答案就好算了。

zr round 7 T2（*2300，分层图，最短路）：发现如果 min 不取最小的或 max 不取最大的都不优，或者说任取路径中两个作为 min/max 并取 min 等于答案。因此建分层图表示这三段路径。

zr round 7 T3（*2600，dp）：注意到如果一个人可以满足填入 i+1 大小的组，则它也可以填入 i 大小的组。也就是说可以填但是没填在 i+1 大小的组的人都可以放入剩下的组。设 dp i,j 表示大小大于等于 i 的组中放了 j 个人。可以枚举大小等于 i 的组有多少个，转移比较简单。

zr round 5 T4（*3000，思维，乱搞）：考虑将一个位置与它要到达的颜色连边。在这个基环森林上找性质会更简单一些。性质以及证明比较繁琐，不写在这里了。最终要统计没有自环且并非全环的 n - 叶子总和、存在自环的个数、一个自环加一条链和一些非自环的环的个数这三个东西。前两个比较简单，对于最后一个，注意到一个环从任意一个地方断开就长这样，所以这个个数即为所有都是非自环的环的个数乘 n。而这些都可以通过错排和 n^{n+1} 求出来。对于后者，考虑将 n 分解成最小的质因数 p 乘 x，那么 n^n=(p^p)^x · (x^x)^p。对于质数可以暴力求出 p^p，因为 p<=sqrt(n) 所以可以使用光速幂求 (p^p)^x。对于后者发现 max pi-pi-1 是 ln pi 级别的，所以可以暴力预处理从 pi-1 到 pi 乘上的数，即 (x^x)^{pi-pi-1}。之后每次乘上这个数即可。复杂度为 sum ln n/i = O(n)。

10.19

zr round 8 T1（*1400，贪心）：遍历 t 的每个字符，每次从上一次的位置加一开始找，找不到就新增一个 s。

zr round 8 T2（*2500，思维，二分）：问题可以转化为，在长度为 1~n 的区间中任选一个，使得平均数组成的序列极差最小。因为一个区间删掉左边、右边组成的新的区间一个比它小，一个比它大，所以越靠近越好，而最靠近的可以被操作出。注意到长度为 n 的区间是唯一的，所以剩下的区间只可能是同长度中最后一个比它小的和第一个比它大的。所以把这些区间拿出来，枚举最小值求答案即可。

zr round 8 T3（2800，思维，乱搞）：一个简单的想法是每次使用操作将一个数到该去的位置的距离除以二，次数为 log 次。考虑倒推操作，即将序列分成两段，每次先去右边第一个再去左边第一个依次铺上去。这样一个位置的期望次数是 (\sum i n/2^i)/n=2。需要先随机若干次操作将序列打乱以保证期望次数。

10.20

acc round 16 T1（*1300，无）：对每个镜面计算出有多少个存在对应关系的点对。可以枚举点对更新镜面。

acc round 16 T2（*2200，倍增）：显然最大独立集为从第 n 层开始，隔一层选一层的点。可以将模 k 相同的层放在一起求，推一下式子可以发现是等比数列求和。可以使用倍增求出。

acc round 16 T3（*2400，贪心，思维）：考虑将一个点从蓝色改成红色会增加什么贡献。 发现贡献之和当前红色点的个数和自己有关。比如一共有 all 个红的，前面有 cnt 个红的，则后面有 all-cnt 个红的，有 n-i-all+cnt 个蓝的。当前会减去 cnt·c 的贡献加上 (n-i-all+cnt)·c 的贡献，与 cnt 无关。所以将每个点的贡献排序，取一个前缀即可。

10.23

zr round 9 T1（*1500，最短路）：虽然要求的内容比较复杂，但是还是满足最短路的贪心性质，即较小的数对以后的贡献也是更小的，而且更新后答案一定更大。所以可以直接跑最短路。

zr round 9 T2（*2300，思维）：考虑将问题转化为有 n 堆石子，每次操作可以将一堆中的一个移到相邻的一堆，问从 a 状态变成 b 状态的最小操作次数。考虑满足第一堆的移动方式是唯一的，在满足第一堆后第二堆也是唯一的，一直这样操作下去就行了。

10.24

zr round 10 T1（*1700，计数）：首先因为 pi 可以相同，所以这三种情况可以分开统计最后再乘起来。发现这三个图形中都有一个点数为 3 的链。考虑对每个点统计它作为链的一段的链的个数。可以使用打 tag 的方式统计出来。剩下的随便算一下。

zr round 10 T2（*2000，并查集）：如果每次合并的复杂度是 O(点数) 的，则复杂度可以接受。考虑不真正新建一个点，而是用并查集存一下表示这些点都被合并成了一个点。这样每次合并的时候类似树剖的方式每次往上跳并合并即可。

zr round 9 T4（*2800，思维，容斥，乱搞）：首先每个 <=n-1 的点一定连最大的与它互质的点。因为至少存在一个比它大的与它互质的点（x+1），所以树的形态是满足的，而且根据伯特兰定理，对每个数 lcm 最大的一定就是这个数。考虑比 n 小的第一个质数与 n 相差不多（实测最多 20），因此考虑枚举这些数并求出有多少个数的最大互质点是它。对于 n，可以使用莫比乌斯反演求出。对于其他的 x，一个满足条件的 y 需要满足 x+1~n 中的每个数都存在至少一个质因数被 y 整除（即不互质）。考虑每个质因数集合选一个数并将这些数乘起来，那么这些组成的集合需要满足存在至少一个被 y 整除。考虑容斥，有被整除的限制还是可以莫反求出来的。但是这样过不去，考虑对于这个集合里较大的数直接枚举它的倍数，暴力检查即可。

10.25

zr round 11 T1（*2000，差分，树状数组）：发现 l 必然为 ai,ai-d 中的一个，所以暴力枚举并计算二维数点。实际上可以考虑每一个点对 l 的贡献，发现是区间加等差数列，可以两次差分。

zr round 11 T2（*2500，dp）：大力 dp，设 dp i,j,k,l(0<=j,k,l<=1) 表示 i 的子树内 i 是否连边（j），dfn 最小的叶子是否连边（k），dfn 最大的叶子是否连边（l），转移比较简单。

zr round 11 T3（*2800，最小割）：路径一定不经过重复的点。考虑将路径表示为一个长度为 n-1 的 01 串，表示从 i->i+1 时走的上下哪条边。选边有代价，选了两个边也有代价，这是一个切糕模型。具体地，一个点连源点表示 0，连汇点表示 1，一条限制连一个反向边表示如果这么选则还需要切断这条边以保证不连通。

zr round 11 T4（*3200，dp）：题解是生成函数，但是这题暴力 dp 可以过。设 dp i,j,k 表示序列中所有数的出现次数均 >=i，长度为 j，不同数的个数为 k 的方案数。这样做的好处是 k<=j/i。再枚举出现次数为 i 的个数暴力转移，可以分析出复杂度为 O(n^3)。

10.26

zr round 12 T1（*1600，思维，线段树）：我的做法是发现所有数一定小于等于最大值，因为每次找到最大值，暴力更新最大值两边的数，并递归处理。正解是正着用 a[i-1]-m 更新 ai 一遍，反着一遍。

zr round 12 T2（*2600，暴力，记忆化搜索）：注意到序列中 1 的个数是可以统计的，且除了 1 其他数的个数是 log 级别的，因此考虑搜索。维护一个序列，每次将一个数拆成两个数，使得更新后的总和可以对应上 b 序列。发现一个数的因数个数很少，所以状态数很少，记忆化搜索一下就没问题了。

zr round 12 T3（*2700，交互，思维，二分）：首先可以通过全局的极差和前缀的极差求出最大值、最小值其中一个在序列中的位置。接下来使用二进制，每次查询二进制的某一位为 1 的位置，得到数的集合。那么对于每个数就知道它所在位置的每一位是 0 还是 1。这样就可以确定了。

10.27

zr round 10 T3（*2700，凸包，旋转卡壳）：发现题目本质要让两条平行的直线包含所有点，求直线距离的最小值。这个问题很像旋转卡壳。结论：至少一条直线为凸包上的一条边。证明：首先两条直线必然切到凸包上的点，否则不优。考虑每次朝着对面那个点的方向移动，根据勾股定理距离一定变小，且最终会变成凸包上的一条边。这样使用旋转卡壳算法即可。

10.28

zr round 4 T4（*3000，思维，分块）：考虑如何判定，发现每次操作每个数右侧小于它的数的奇偶性不变，而感性理解一下一个数需要跨过这么多个数，所以猜测充要条件是每个数右侧小于它的数都为偶数。首先如果不为偶数一定不行。否则每次复位最左的一个即可。考虑分块，块内维护每个值比它小的个数的差分。发现如果值存在奇数则差分也存在奇数，而且如果每个差分都对应到了值上（即将值排序后看成一个序列的区间加），差分存在奇数则值也存在奇数。因此分块大力维护差分以及差分数组中奇数的个数即可。

10.30

zr round 13 T1（*2000，dp，bitset）：dp i,j,k 表示 s 的前 i 个是否能被若干个完整的 x 加上 x 的前 j 个、若干个完成的 y 加上 y 的前 k 个组成。对 k bitset 一下。

zr round 13 T2（*2400，dp）：赛时的做法是设 dp i,0/1 表示在 i 的子树内走，当前点在 i，0 表示不回来了，1 表示还回到点 i。0 体现的是 B，1 体现的是 A。大力 dp 并换根。赛后（10.31）看题解的做法是，考虑将 A 操作视作加重边，这样可以提前 A 操作，接下来的问题是小学奥数的“多笔画”问题，需要走 max(奇点个数/2,1) 次。剩下可以考虑设 dp i,0/1,0/1 表示在 i 的子树内，i 的度数是奇数还是偶数，i 的子树内除了 i 是否存在奇点。转移比较简单。关于“多笔画”问题的证明，我想了一个：首先每条路径只能将两个奇点变偶，所以操作次数至少为奇点个数/2。考虑在每对奇点之间加一条边，剩下的图一定存在欧拉回路。再将欧拉回路上新加的边删掉，就会剩下 max(奇点个数/2,1) 条路径，也就证明了下限可以取到。

zr round 13 T3（*2800，dp）：考虑将 k 次方转化为选 k 个点。新建 n+1~n+k 这些点，这些点的父亲为 1~n，这样就可以转化为有多少种树可以使 n+1~n+k 都在 i 的子树内。设 dp i,j 表示只考虑 i~n 作为这些点的父亲，n+1~n+k 这些点组成了 j 个连通块的方案数。每次考虑 i 作为一些连通块的根的父亲，合并一下。

10.31

zr round 14 T1（*1800，计数）：考虑对每个数算贡献。将每个数连带下标排序，统计当前这个数作为中位数的个数。可以暴力枚举比它小的和比它大的在哪几个集合。

zr round 14 T2（*2100，思维）：首先若图有非自环的环，则 f 要么在 0、1 之间波动，要么逐渐增大。否则若图上的一个自环可以到达另一个自环，则可以选择一个时刻到另一个自环，f 逐渐增大。否则 f 收敛。

zr round 14 T3（*2400，博弈论）：通过找规律或归纳等方式可以发现：若序列中每个数的出现次数均为偶数，则先手必败，否则先手必胜。证明：只需证明先手必败的状态不管怎样都会走到先手必胜的状态，先手必胜的状态可以走到先手必败的状态。对于先手必败的状态，若操作了一个数，则比它小的数必须要补上来。而这样就相当于操作了比它小的数，迟早会没有小的补上来。对于先手必胜的状态，若 n 为偶数，考虑将最大值 a 减到最小值 b，并将 a-b-1（因为至少拿掉一个）分给剩下的，使得剩下两两匹配。考虑将剩下的排序后相邻两个匹配，此时需要的石子数为 a[3]-a[2]+a[5]-a[4]+...，这个数一定小于等于 a-b。而这个数不会等于 a-b，因为如果它等于 a-b，就一定是先手必败的状态了（每一个对的后一个等于下一个对的前一个）。所以可以变成先手必败的状态。若 n 为奇数，直接将最大值 a 拿光，并将 a-1 分给剩下的。接下来就与上面类似了，而且不用讨论 =a 的情况，因为最小值 >=1，极差 <=a-1。

11.1

zr round 15 T1（*1500，无）：考虑枚举每一个绝对值怎么拆开。注意到如果这个绝对值拆错了，那么肯定不优，因此直接算一个 max 并加当前的值即可。

zr round 15 T4（*2400，dp，矩阵树定理）：注意到满足条件的子图一定由若干个交到同一个点的环和环外的树组成，因为如果有一个环与另外两个环的交点不是同一个，则必然产生一个新的环，而这个环与另外两个环有边的交。考虑枚举交点，使用状压 dp 求出环的方案数，并将环看成一个点，套上矩阵树定理即可。

11.2

zr round 16 T1（*2100，dp，期望）：首先期望就是每种选数的异或乘以概率。考虑拆位，从小到大枚举位数，那么当前的贡献就是平方加上自己乘上前面的和。对于前面的和，可以再次拆位。总之要求第 i 位和第 j 位都为 1 的概率之和，可以 dp。

zr round 16 T2（*2500，组合数，二项式反演）：考虑想象串的组成是 0 将 1 切成了很多段。可以先求连续段长度 <=k 的方案数。本质上要求一个问题：将 m 分成 n-m+1 个数，每个数在 0~k 之间的方案数。考虑二项式反演，钦定有 x 个大于 k 的，那么先选 x 个位置将这些位置 -k，剩下的就可以任选了。而 x 的上限是 (n-m+1)/k，所以复杂度是调和级数。

zr round 15 T2（*2300，字符串）：注意到一个 i 在跳 fail 的时候，若 x 是 i 跳若干次得到的数，则 i-x+1 组成的集合为所有点到 i 是字符串前缀的点集（或者说如果一个位置不能通过 i 跳 fail 得到，则这个位置到 i 不是字符串的前缀），可以通过 fail 的定义证明。那么每次令 z[i-x+1]=max(z[i-x+1],x) 即可。所以已知 fail 就可以唯一确定 z。考虑构造一个满足条件的字符串，之后暴力求 z。使用以下构造方法：如果 fail[i] 不为 0，令 s[i]=s[fail[i]]，否则 s[i] 为一个新的字符。考虑归纳证明这个构造方法的正确性，现在要证明在 1~i-1 满足条件的情况下，根据构造方法新加一个 i 也满足条件。首先根据 kmp 算法，新的 fail[i] 一定满足前后缀相等。还需要证明没有比 fail[i] 大的位置。首先这个位置一定在 i-1 跳 fail 的某个后面。可以发现这种构造方式一旦有两个字符相等，就是必然相等的。那么如果存在这样的位置，就说明 fail 不合法了。

11.3

zr round 15 T3（*2500，最短路）：将每个点放到新的坐标系上，(x,y) -> (x+1,x-y+1) 可以发现限制就是 (i,j),(j,k),(k,j) 满足三角形不等式。对新图跑全源最短路即可。证明：首先最短路满足三角形不等式。如果有一个点比最短路大，则在最短路上一定存在一个点不满足三角形不等式。

zr round 16 T3（*2600，线段树）：注意到如果有三个相等的段满足左右都大于中间（可以赢），则中间的可以替换成这个相等的数。而且这么操作若干次之后一定可以变成只有一种颜色。因为如果有一种状态没法删了，则第一个段一定大于第二个段，第二个段一定大于第三个段（否则第二个段就会被删），一直到最后，最后一个段会被删。通过这个证明也可以想到一种暴力的做法：维护一个栈表示前缀没被删的数，每插入一个数，若这个数比栈顶大，则弹出栈顶并根据栈是否为空决定是否加入当前数；若相等，则不动；若比栈顶小，则加入这个数。最终的答案即为栈顶。可以发现每次更新这个数一定在栈顶，那么答案就是栈的大小为 1 的最后一个数。考虑栈的大小变化是：要么 +1，要么不变，要么 -1 并与 1 取 max。结论：答案为在 -1 的时候不取 max 得到的序列最后一个最小值的位置。证明：首先这个最小值后不存在，否则可以替换。其次若最后一个 1 在最小值前面，则移动的总和是非正数，移动过程中一定会找到新的 1，矛盾。因此维护一个线段树支持单点修改前缀 max。

CF1313D（*2500，状压 dp）：将区间离散化。对每个离散化后的一段，覆盖的区间是一定的，对这些区间选不选状压。转移时在上一个区间的区间的选择情况是固定的，剩下的取个 max。

CF1322B（*2100，拆位，二分）：对每一位分别统计有多少对加起来的这一位是 1。考虑将一个数的第 x 位是 1 转化为这个数模 2^{x+1}>=2^x。这样先将每个数对 2^{x+1} 取模。之后即统计两个数 (a+b)%mod>=c 这样的对数。枚举 a，分讨 a+b 与 mod 的关系，可以确定 b 可能的两个区间，分别二分。

CF1875C（*1400，思维）：这个题的证明好难啊……考虑最终的若干个数被分成 m 组后的形态，这些组的总和都为 n/m。可以证明这些组的的集合都相同，而且就是 n/m 的二进制上的每一位。因为二进制的表示是唯一的，其他情况都会存在相等的两个值，而合并这两个相等的值（如果小于 1 则在分裂的时候就不分这个，大于等于 1 则看成加起来的值），一定更优。这样也可以看出如果 m/gcd(n,m) 不是 2 的幂，就无解。根据这些组的集合都相同，可以证明将 n,m 都除以 gcd(n,m) 后分别计算并将答案乘上 gcd(n,m) 是正确的。这样 m 就变成了 2 的幂。可以将 n 转成二进制，再右移 m 位便是 n/m 的二进制形式。再对每一位算贡献即可。

CF1875D（*1600，dp）：删除的数一定是递减的，而且大于等于 mex 的数没有意义。VP 时的做法是设 dp[i][j] 表示前 i 次操作使 mex=j 的最小代价。转移需要再枚举上一次的 mex。但是注意到相同次数的数一定选最小的优，这样最多有根号个数是可能被选的，复杂度就正确了。后来发现注意到无论如何到最后 mex 都变成 0 了，而且 mex 变成 0 之后不会产生贡献，因此不需要记录第几次操作。这样就变成 O(n) 的了。

11.4

upd：我最近对记录这个博客的意义的想法变了，之前是为了提交作业，现在感觉确实有必要记录。因此之前只会记录打比赛写的题，现在也会记录一些有意义的 CF 题。

未知比赛 T1（*2500，组合数）：考虑在一个表格里记录答案，行表示胜场加负场的个数，列表示负场的个数，递推答案，直到列 >=m 或行-列 >=n。可以发现这是一个组合数，要求这么递推的过程中数都是整数。推推式子可以发现答案为在一个条带状的区域中 n-(C(n,m) 在二进制下末尾 0 的个数) 的 max。可以发现后者最多为 log（组合数为一个长度相等的后缀减前缀，对于每个 2^i 出现次数最多差 1），所以前者与最大值的距离不能超过 log。暴力枚举 log^2 的区域，随便优化一下即可。

未知比赛 T2（*2600，单调队列）：首先距离越小，极差越小。如果有一个位置的 dp 值不是后缀最小值，则一定不如后面的最小值。那么 dp 的后缀最小值和极差是两条单调的直线，max 的 min 在交点出取到。可以发现如果 i 加一交点会右移，所以使用单调队列维护 dp 的 min、a 的 min/max 就行。

未知比赛 T4（*2100，并查集）：可以发现修改强制在线了但询问是离线的，所以本质上还可以离线。直接对每个时间点记录以后会查询到的询问即可。

11.6

CF1325D（*1700，位运算，构造）：首先若 x>y 或 y-x 是奇数则无解，因为异或和加法的区别在于进位，而进位到的位 >=1，贡献一定是偶数。注意到如果答案的 n>2，可以构造 x,(y-x)/2,(y-x)/2。现在只需要判断 n=2 是否可行。从小到大枚举位，若异或的当前位与和的当前位不同，则无解，否则如果都为 1 方案是唯一的；如果都为 0 当前可以选择 0,0 或 1,1，而后者会对下一位有贡献。讨论下一位的两个数是否相同从而决定当前放 0 或 1 即可。

zr round 17 T1（*1600，数论）：首先 b 补足 a 在分解中指数为奇数的数。剩下的 b 可以乘上一个完全平方数。预处理 1~1e6 每个数的完全平方数后对 l/b 二分。

zr round 17 T2（*2400，数论，计数，高维前缀和）：注意到 gcd 是 m 的因数，因此可以枚举 gcd 并算出 lcm。先将 lcm 除以 gcd，将问题转化为选择 n 个数使得 gcd=1,lcm 等于当前数。这些数一定是 lcm 的因数。现在可以求出任意 gcd,lcm 的选 n 个数使得 gcd 整除数 gcd、数 lcm 整除 lcm 的方案数。而这个放到质数的高维上就是一个前缀和。对前缀和差分即可。

zr round 17 T3（*2500，dp，均摊复杂度）：在 dp 过程中需要记录一个 sum 数组，sum[i] 表示前面 a[j]=i 的 dp[j] 总和。而这个的更新是 O(1)，但查询是 O(2^m)。考虑记录 sum[i][j] 表示前面 a[k] 的前 10 位是 i，后 10 位是 j 的子集。这样更新和查询就都变成 O(2^{m/2}) 了。

CF1338B（*1800，思维，构造）：注意到如果一个叶子与其他叶子的路径异或和为 0，那么限制就满足了，因为异或消掉了。考虑随便拎出来一个叶子作为根。对于最小值，猜想如果其他叶子的深度都为奇数则答案为 1，否则为 3。深度都为奇数的情况都填一种颜色即可；否则，两种颜色一定不能填充，因为归纳可以证明第奇数层可能的异或和为 x,y，第偶数层可能的异或和为 0,x^y。三种颜色的方法是使用 1,2,3，如果下一个点不是叶子，选择一个与之前异或和不同的数填，否则选择与之前异或和相同的填。对于最大值，答案最多为 n-sum max(一个点周围叶子个数-1,0)。一种构造方法是 dfs，如果下一个点不是叶子就设为一个之前没用过的 2^i，否则设为当前的异或和。

CF616E（*2200，整除分块）：a%b=a-(a/b 向下取整)·b，直接整除分块。

CF612E（*2200，排列，思维）：考虑将 i->q[i] 建出一个图，会形成若干个环，问题转化为要复原出这些环，使得一个点往后两个的点是 p[i]。可以先将 i->p[i] 连边，对于长度为奇数的环自己就能满足，长度为偶数的环需要用两个合并。随便合并就行了。

CF1874C（*2300，dp，期望）：普通的 dp 不用多说。结论：每次第一个人选择概率（dp 值）最大的点。证明：考虑数学归纳加邻项交换。假设已经证明了比 n 小的情况，当前选了不是最大值的点（设概率为 y），最大值的概率为 x。因为已经归纳了，所以选完这个点如果还可以选，一定选 x 这个最大值。考虑求出以 y,x 这个顺序，最终走了 x,y 中的一个的期望和以 x,y 这个顺序的期望，并比较，因为剩下的无论选的顺序如何都一样。两者分别为 1/n·y+(n-1)/n·1/(n-2)·x，和 1/n·x+(n-1)/n·1/(n-2)·y，显然后者更大，这样就证明完了。接下来考虑设 f[i][j] 表示长度为 i 的序列按照上述贪心策略选到排名为 j 的概率。转移即考虑当前随机到的那个位置在它之前还是之后即可。upd on 12.22: 回来看这题，结果发现之前的证明思路是错的，那个式子之间应该有个 (n-1)/n，而且别的地方也假了。现在写了一篇题解：https://www.luogu.com.cn/blog/wangxiwen/solution-cf1874c。

11.7

CF603C（*2200，博弈论，sg 函数）：每个石子堆是独立的，可以使用 sg 函数。sg 函数的值只与 k 的奇偶性有关。当 k 是偶数时，会形成一个 0,1 的循环节；当 k 是奇数时，可以发现奇数的 sg 函数是 0。对于偶数，可以直接递归求解，是 log 的。

zr round 18 T1（*1700，并查集）：对于一个数都出现过的连续段，答案为 (len+1)/2，而两个连续段互不影响。因此使用并查集维护答案。

zr round 18 T2（*2300，线段树）：本质需要求 f(n,x) 表示有 n 个点，根的标号为 x 时编号总和。注意到每个点都是 x 的一次函数，所以总和也是一次函数。所以只需要处理出一次函数即可。发现线段树上的区间长度的个数只有 log 个（为 n,n/2,n/2+1,n/4,n/4+1,...），所以复杂度是对的。再放到线段树上查询即可。

zr round 18 T3（*2500，线段树）：考虑对于 (a,b),(c,d)，将 max(a+c,b+d) 拆开，当 a+c<=b+d 时 a-b<=d-c，贡献为 b+d；否则 a+b>d-c，贡献为 a+c。直接将 a-b 或 d-c 放到线段树上，线段树的一个区间维护的是所有 a-b 或 d-c 在其中的贡献最小值。这样做的好处是利于合并，因为左右区间的大小关系是确定的。更新的时候对每一个 l=r 的区间记录四个 multiset，暴力更新。为什么要这么建线段树？可能这个思路来源于分治，即处理左对右的贡献后分治两边。

zr round 18 T4（*3000，dp，斜率优化）：首先走的路线一定是在 k 左右反复横跳的。设 dp[i] 表示从 k 走到 i 后所有草的高度和没除掉的草与 i 的距离总和。这样就可以发现，一次从 i 移动到 j（j<i），i 左边的高度加距离不变，而右边的加 2。可以每次找到 dp 最小值，那么这个 dp 值就是真实的了，用它更新其他 dp 值。可以发现这些确定的 dp 值是一个区间，考虑每次扩展两个，求出它们从这个区间内转移过来的 dp 值。那么两者较小的就是真实的值，扩展它。现在把问题转化为：加入一个位置，求一个位置从这些位置转移过来的最小值。可以使用斜率优化解决。不过我现在也不知道出题人怎么想到的，以后需要再看看，理解一下。

acc round 26 T1（*2100，拆位）：将平方展开，对每两位计算区间这两位的异或都为 1 的个数。使用异或前缀和，并用 map 记录前面区间的前缀和情况。

acc round 26 T2（*2400，算贡献）：对每个位置计算有多少区间满足区间并集包含这个位置。将区间离散化，那么只有 O(n 种不同的位置。考虑每次移动一个位置，维护每个区间是否包含它。相当于维护一个 01 序列，支持单点修改，求 0 的极长连续段的 len·len+1)/2 的总和。使用 set 维护连续段即可。

11.8

zr round 19 T1（*2200，构造，容斥）：当 m<n-1 时，一个贪心思路是尽量用大的限制住小的，2->1,3->2 这样连边。但是在最后，需要 n->m 而不是 m+1->m。这样一定是最优的，且没有别的边的集合一样优，所以答案为 m!。否则，边的集合中必然有 2->1,3->2,...，所以问题转化为求多少长度为 n、值域为 m 的序列，满足 1~k 都出现至少一次。考虑二项式反演，钦定 x 个数没出现过，剩下的可以任选，这样就好算了。

zr round 19 T2（*2200，构造）：可以先连边，形成若干环，这样更形象一些。考虑从 i-1->i 的 a 变化。如果有一个左边的点与 i 有连边，则移动区间后 a 减 2。如果有一个右边的点与 i 有连边，则移动区间后 a 加 2。考虑若 a 不变就连一个自环，若 a 减 2 就匹配前面一个需要跟右边匹配的连一个二元环，否则将它视为需要跟右边匹配的点。因为 a 不可能小于 0，所以这个过程类似括号匹配，一定有解。或者感性理解二元环一定比其他的环优。

zr round 19 T3（*2700，dp，bitset）：对于 s 中的一个点会变成 t 中的一段。考虑若这段的长度大于等于 2，如何判定是否可以被字符变成（此时无需关注字符具体值）。可以发现充要条件是这段中没有 T、第一个字符是 A、最后一个字符是 C 或 G。首先不满足一定不行。如果满足条件可以递归构造：若倒数第二个字符不是 A，则可以在最初将字符分裂成两个，并用第一个字符递归处理前面这段。否则取出 A 的连续段，仍然将字符分裂成两个，对于第一个仍然是递归处理前面，对于第二个可以每次用字符的第二个分裂，这样就能形成 AAAC 这种。考虑设 dp[i][j] 表示 s 的前 j 个字符变成了 t 的前 i 个字符是否可行。对于相等的可以直接转移。剩下的记录一个 bitset 类型的 now 表示所有 i+1 到当前没有 T、[i+1]=A 的 dp[i]<<1 或起来。如果当前是 C 或 G 则可以或上 now。这样就完成了 dp。对于构造可以对于每个字符找到从后往前一个满足要求的段，并按照上述构造方法构造。

acc round 26 T3（*2700，主席树，启发式合并，口胡）：首先动态加边可以用启发式合并维护，转化为静态问题。考虑对每个节点维护它到根的前缀和减数值的主席树，和根到它的前缀和减数值的主席树。树上差分，问题转化成了求线段树中比 x 大的数的个数。对于主席树的更新，可以考虑打 tag。

acc round 26 T4（*2800，虚树，口胡）：叶子节点 O(k)（k=100）个等价于儿子个数大于 2 的节点 O(k) 个。考虑对分叉的路径和一个节点到祖先的路径这两种分别求。显然 f 和 g 在一条链并且起点固定的情况上只有 log 种。的对于分叉的路径，从子树中合并上来分叉的路径，并对子树两两合并求答案。因为子树内叶子节点个数为 O(k) 个，所以不同的 (f,g) 对只有 O(k·log) 种。而合并的复杂度是树上背包的复杂度，所以这部分的复杂度为 O(k^2 · log^3)，可以使用科技将快速幂的 log 优化掉。对于点到祖先的路径，可以枚举这个点，二分出 log 种 (f,g)。

acc round 27 T2（AT_agc034_e）（*2600，换根 dp，口胡）：枚举最后所有点都在的那个点，考虑 dp。设 dp[i] 表示将 i 的子树内的所有点移动，使得这些点与 i 的距离最小。因为在移动过程中距离逐渐减 2，所以过程中一定涉及到最初的距离之和到 dp[i] 所有奇偶性相同的值。每次转移只需要考虑子树内的距离之和，所以这样做是对的。转移时相当于有若干个区间，对于每个位置可以选择在这个区间内与区间左端点奇偶性相同的点，选出点后每次将两个点分别减 1，使得最后点的总和最小。考虑如果点是确定的，如果最大值大于剩下的，则答案为最大值减去剩下的，否则答案为总和模 2（可以归纳证明）。对于区间的问题，考虑钦定一个区间作为最大值，并计算它是否所有情况都是最大值。如果存在这样一个区间，则答案为这个区间取到最小值，剩下取到最大值相减的值。否则答案为区间左端点总和模 2。证明可以考虑调整。直接换根 dp 即可。upd on 12.19: 之前口胡的不太对，这次写了一下（O(n^2) 的，换根应该好办），应该是对的。考虑枚举根。结论：若一个点为另一个点的祖先，则不会操作这两个点。证明：如果操作了一次，则上面的点会下来，而它最终需要上去，所以考虑让它上去的那个点，换成操作下面的点和这个点是一样的。对于儿子，如果一个儿子尽可能多操作后与当前点的距离还大于剩下不操作的距离，则答案就是这两个相减。否则，答案是 0 或 1。证明类似上面区间的问题。这样就可以 dp。dp[u] 表示在 u 子树最多操作后所有点与 u 的距离。根据上面可以转移。

11.9

zr round 20 T1（*2000，dp）：对于编辑距离问题，可以先删除后插入。这样相当于将 s 删除一些字符后变成了 t 的子序列，再补上一些字符。所以答案为 |s|+|t|-2·lcs(s,t)。普通 的 lcs 是设 dp[i][j] 表示 s 的前 i 个字符与 t 的前 j 个字符的 lcs。但是注意到 j 和 dp[i][j] 都是 O(|t|) 的，所以设状态为 dp[i][j] 表示 t 的前 i 个字符与 s 的一个前缀的 lcs 为 j 时的前缀最短长度。转移时讨论 t[i] 选不选就行了。

zr round 20 T2（*2400，二分，线段树）：如果一个区间包含另一个区间，则被包含的区间一定不是最优的。将被包含的区间都删掉，剩下的区间满足左右端点都单调递增。从大到小加点，对每个区间维护当前有多少个数在这个区间。显然一个点被连续的区间包含，所以维护一个区间加、区间最大值的线段树即可。

zr round 20 T3（*2800，爬山，拉格朗日乘数法）：正解不会，但是可以爬山。每次将一个变量加 x，另一个变量减 x。使用一个常见的优化——x 的范围随着枚举的次数减小即可通过。出题人提供了一种随机化算法：每次选择两个变量，将它们调整到最优，可以求二次函数的顶点。这样严格优于爬山。

P6144（*2500，dp，二项式定理，线段树）：先考虑 k=1 的情况。设 dp[i] 表示线段集合的最右边的点是 i 时连通块个数的和。将线段按左端点从左到右排序，动态插入线段，维护 dp 值。每次插入线段 [l,r] 会影响 dp[r]。对于 i<l 的线段右端点，会使连通块个数加一；对于 i∈[l,r] 的线段右端点，连通块个数不变。对于前者需要维护 k=0 时的答案。插入这条线段还会影响 i>r 的 dp[i]。因为按左端点排序了，所以这条线段一定被之前某条线段包含，此时连通块个数不变，那么这些 dp 值会乘 2（是否选择 [l,r]）。使用线段树维护区间乘，区间和。若 k>1，可以根据二项式定理从 a^0,a^1,...,a^k 推到 (a+1)^k，所以直接维护 0~k 次方即可。为什么不能按右端点排序呢？因为插入这条线段后可能会合并两条线段，让连通块个数减少，不好维护。

11.10

acc round 28 T1（*1200，前缀和）：k 的因数只有根号个，因此可以对每个因数分别计算答案。求一个异或前缀和，开一个桶记录就行了。

acc round 28 T2（*1600，思维）：最后的一个数的组成一定为若干个下标具有相同奇偶性的数加起来。可以对奇偶分别求。显然的贪心策略是选 a[i]>=0 的位置。计算可以得到对于奇偶性相同的若干方案，如果不考虑首尾，操作次数相同。对于首尾，选比不选优。因此直接选所有 a[i]>=0 的位置即可。

acc round 28 T3（*2300，思维，堆）：首先单调不降的限制没有用，因为如果 a[i] 要到 b[i] 的路上被 a[i-1] 挡住了，那么 a[i] 就不可能挡住 a[i-1]，再考虑 a[i-1] 是否能移动，一直考虑下去最后 a[1] 一定可以移动。考虑一个数 a 拆成了 x 个数，这 x 个数需要尽量平均（可以用调整法证明）。感性理解一下，随着 x 的增大，新的贡献会逐渐减小，即函数是凸的。如果没有拆成的数是整数的限制，是好证的，但是有了就只能感性理解了。这样每次选择贡献最大的位置扩展一定是最优的（也可以用调整法证明），于是使用堆每次找到贡献最大的位置扩展。

acc round 28 T4（*2500，线段树）：大力使用线段树维护。堆每个区间记录假设将 A 看成 x[0]，B 看成 x[1]，C 看成 x[2]（x 是一个排列），从 y 出发走到最后会变成什么字符。这样修改好办了。注意如果真实交换了两个字符，需要先在原来的基础上交换，再放到排列上。

11.11

upd: 由于简单题难度太难评价，若点数小于 2000 且不是 CF 题，记为 *<2000。

洛谷 noip 模拟赛 T1（*<2000，数学）：考虑每次只给数乘上质数，这样一个质数的贡献是 (cnt+2)/(cnt+1)，cnt 是这个质数之前在数中出现的次数。这个贡献是单调递减的，所以每一次选择贡献最大的一定更优，即每次取出 cnt 最小的操作。可以使用堆维护。

P4244（*2400，仙人掌）：对每个点记录从这个点往下的最长链，按照圆方树的顺序转移。统计答案时相当于在一个环上求两点的权值加距离的最大值，可以单调队列优化。

11.12

P4630（*2500，圆方树）：结论：在点双内任意三点 u,v,w 存在 u->w->v 的简单路径。证明：根据点双的定义，可以找到包含 u,w 的简单环。删掉 u，之后环和 v 之间一定存在一条路径，否则 u 是割点。这样这条路径再加环的一部分即为满足条件的路径。建圆方树，两个圆点作为起点、终点时中间点的个数即为路径上的方点大小减 2。可以对每个方点计算贡献。

11.13

acc round 30 T1（*2200，st 表，猫树）：如果询问较少可以使用标记永久化线段树。其实 st 表也可以标记永久化。每一次找到一个区间对应的两个 st 表上的区间，让它们与查询的值取 max。最后反推到单个值即可。也可以使用猫树，大同小异。

acc round 30 T2（*2800，线性基，01 Trie）：如果起点终点固定，则这题就是 最大 XOR 和路径，做法是建 dfs 树，将树上所有只经过一条非树边的环放进线性基里，再任意挑选一条路径，查询这条路径与一些环的异或最大值。原理是，如果放进线性基里的是所有环，任意一条路径都可以被这样组成出来（两条路径会组成环，这样一条路径异或一下环就变成另一条路径了），而且任意一种组成都是合法的。接下来需要证明只经过一条非树边的环可以表示出所有环。可以使用归纳证明，先证明只经过一条非树边的可以表示出只经过两条非树边的，等等。详细证明略。接下来就将问题转化成了，要在一个集合 A 里选出两个元素 x,y，并在一个集合 B 里选出若干元素 S，使得它们异或起来最大。考虑将问题转化为在 B 中选出两个集合 S1,S2 使得 x^y^S1^S2=(x^S1)^(y^S2) 最大。考虑线性基能做的就是让一个数在有数的位置上为 1，剩下的听天由命（是唯一的）。强制让 x 选择让它在所有数的位置上为 1 的方案，再让 S2 找补。那么 y 一定选择让它在有数的位置上为 0 的方案，即最小值。这样直接使用 01 Trie 做就行了。

CF1895E（*2300，并查集）：考虑将 B 的攻击值和防守值交换，并放到平面上，这样就将问题转化为对于先手的 A(xa,ya) 和后手的 B(xb,yb)，若 xa>xb 则 A 可以压住 B，若 yb>ya 则 B 可以压住 A。发现每次压住的牌是满足条件的另一维度最大的牌。因为这次压住之后只需要关心另一维度的值了。这样建一个图。如果一个连通块是一个树，那么树根属于哪个人决定了这里面所有牌的胜负情况。否则一定是平局。

11.14

信友队 noip 模拟赛 T1（*2400，前缀和，二分）：首先可以发现不同的正方形全 1 且右下角的向下、向右都为 0 的个数是 O(nm) 级别的，因为对于一个左下角，最多对应一个正方形。考虑枚举这样的正方形，再枚举矩形的下边界。这样的复杂度是对的，因为对于一列，行的枚举和下边界的枚举本质上是枚举 0 的连续段，是 O(n) 的。对矩阵的每一个元素预处理向右的 0 的个数即可求出矩阵的右边界的个数。

信友队 noip 模拟赛 T2（*2300，01 Trie）：首先必然要建 Trie 树。大小关系可以在 Trie 树上体现，因为 Trie 树本质上是按某一位分治。因此可以对 Trie 树的每一个节点预处理出 0 对 1 的贡献和 1 对 0 的贡献。对于查询可以对 x 的每一位讨论，如果是 0 则要求 1 在左边，0 在右边的逆序对个数，否则要求 0 在左边，1 在右边的的逆序对个数。

洛谷 noip 模拟赛 T2（*2400，思维，构造）：首先可以发现无序二元组的个数和相邻的对数是相等的，所以每个二元组会出现恰好一次。又发现二元组的差为 i 时有 n-i 个，也恰好对应每一行的个数，因此考虑将相同差的二元组填入相同的行。不过仔细想想会发现这种方法不行，原因是在一行的两个相邻二元组需要共用元素，而它们的差又必须相等。但是如果把这样的思路放到列上，就少了这个限制，而新增的限制是一行中的差递增。而这个限制就比上一个限制好处理。考虑对每个数加减构造，比如 x,x+1,x-1,x+2,x-2,...，直到某个数超过了限制。并将一个 x 引导的序列按长度排序，就构造好了。容易证明这样做是对的。

洛谷 noip 模拟赛 T3（*2500，dp，贪心）：注意到至少有 \prod cnt_i! 种方案达到某一优美度（因为相同 f 的内部可以任意排列），所以当 n 比较大的时候答案就是优美度的最小值。此时相当于有两个数组，需要让一个数组重新排列，使得对应位置乘积之和最小。显然将第一个数组从小到大排序，第二个数组从大到小排序是最优策略。可以使用调整法证明。f 的值域是 log，所以随便计算答案。当 n 比较小的时候（n<=29）发现优美度 <=8000，因此可以大力 dp。可以转化为统计优美度为某值的序列个数。大力记录前若干个数，f 值为 1,2,3,4,5 的个数分别是多少，以及当前的优美度。每次枚举最后一个值是什么即可转移。

11.15

洛谷 noip 模拟赛 T4（*3000，思维，线段树）：https://www.luogu.com.cn/blog/wangxiwen/solution-p9839。

信友队 noip 模拟赛 T3（*2600，扫描线，线段树）：显然要求出 i,j 使得 a[i]>a[j]，并使得 [i+1,j-1] 之间值域在 [a[j],a[i]] 的个数最大。显然可以发现如果一个数不是前缀 max，则它不可能作为 i。同理如果一个数不是后缀最小值，则它不可能作为 j。剩下的两个序列都满足值域单调递增。考虑对每个 k 对 (i,j) 做贡献。显然需要满足的条件是 i<k,a[i]>a[k],j>k,a[j]<a[k]。发现 i,j 在序列上都是一段区间，把 (i,j) 看成点，相当于矩形 +1，最后再求全局 max。可以使用扫描线加线段树解决。

P5658（*2100，括号序列）：可以对每个点求出从根到它的路径，以它为结尾的区间为括号序列的个数。求前缀和，则当前可以通过上一个前缀和相等的位置转移。如果当前的字符为左括号则答案为 0。

AT_arc084_b（*2500，同余最短路）：整数倍等价于模 k 为 0，因此考虑在模 k 意义下生成 S。考虑从 1 开始，每位乘 10，再加若干个 1，就可以生成任意一个数，而且可以动态维护数位和。而且一定是按照这样的方式生成的，如果通过若干个 +1 进位，数位和一定更大。

11.16

CF1695C（*1700，思维）：一个套路是，如果从最小值到最大值的调整每次只会 +1 或 -1，则这之间任意一个值都会遍历到。这道题类似，只是每次 +2 或 -2。因此只需要求最小值、最大值并检查 0 在之间、与它们同余即可。

P3403（*2300，同余最短路）：考虑模 x、y、z 同余的数是否能到达一定都有单调性。因此考虑在模 x 意义下使用剩下两个操作连边。一个更好写的方法是转圈法，对于每个 +y 后产生的环转两圈就可以保证每个点都可以更新剩下的点了。

P2371（*2300，同余最短路）：与上一道题同理。

P9120（*2600，扫描线，线段树）：显然最小值和最大值不能在同一行里，否则已经达到最大值了。这样可以钦定最小值在第一行，枚举最大值的行，就确定了两行的最小或最大值。考虑二分，这样就确定了两行的范围。对于 m=3，考虑每种移动是否满足这两行的要求，如果满足，把第三行拿出来，即询问是否存在一个限制的区间满足 n 列都存在一个在内。可以排序后双指针解决。对于 m=4，考虑转化为在二维上有若干个点，是否存在一个边长为 mid 的正方形中满足 n 列都存在一个在内。双指针一维，在另一维用线段树维护每个左端点开始能包含多少个列。可以发现每次加点、删点只需在线段树上区间加或区间减。有一种随机化可以通过这题。考虑一个假贪心是，每次从左到右选择可以使当前答案最小的旋转的方法。虽然很假，但是发现大部分区间都不会使答案增大，因此有决定答案优劣的区间可能很少。因此随机一种顺序并贪心即可通过。

P5687（*2000，最小生成树）：直接模拟 kruskal 的过程。可以发现，每次加入一条线段，如果它是同方向的第一个，则全都可以。否则，可以放 max(相反方向的个数-1,0) 个，因为虽然一些线段是断开的，但是在点上还是连续的。如果一条线段不是第一条且把两个相反方向的线段连起来了，考虑找到向左同方向且连接这两条线段的第一个。如果相反方向的线段没有缺口，则直接形成环。否则缺口的位置一定是之前有一条同方向的在这一段连起来了。如果这一条线段在当前线段的左边，则与之前的定义矛盾。否则向右看也矛盾。总之手模就可以得到结论，证明比较麻烦，但也是可以证的。

P5665（*2600，思维）：结论：使得最后一段的和最小的方案最优。证明。大概的思路是：归纳证明，对于两种情况，前面的区间一定是交错的，否则可以推上去。可以将问题转化为一些交错的段，证明最后一个段较短的更优。可以调整，将最后一个等于 b1 的加一、第一个等于 bn 的减一，相当于平移了一个单位，这样 b 会变优。如果调整过程中有前缀和相等的时候，就分别处理。最终会变成 a。如果交错的段个数不相等，一定是 a 多一段，考虑将第二段往左平移，直到第二段的右端点与 b 的第一段的左端点重合或者第二段的左端点与 0 重合了。如果是前者，直接使用第二段的左端点当做 0，使用上述方法调整即可。如果是后者，相当于消去了 b1。总之调整的操作都是使 a 更劣或 b 更优。有了这个结论之后使用单调队列优化 dp 即可。

P5666（*2700，树的重心、倍增、树状数组）：考虑先求出原树的重心。以重心作为根建树，可以发现剩下的点需要割掉的边必须是父亲的那个子树。因为这个子树大小一定大于 n/2，这样可能会好做一些。先求出重心的答案，比较好做。对于剩下的，分割的边是祖先或不是祖先两种情况讨论。推一推式子发现问题变成了求子树或链上权值（这里是子树大小）在某个区间内的个数。前者可以离线树状数组后者因为有单调性所以可以倍增。

11.17

P7077（*2500，拓扑排序）：感觉这题和接下来的 NOIp T2 有点像，而这题我当时做了两个多小时，可能这就预示着我 NOIp 的遭遇吧。考虑给每个加法也看成一个数，需要求出这个数的系数。先对每个函数使用拓扑排序求出如果调用它会乘上多少的系数。接下来对每个函数求出当前函数的操作会被乘上多少的系数。最初在操作序列中的函数的系数是操作序列的后缀积的和。之后再跑一次拓扑排序，对于每个函数按顺序更新它的子函数。最后，每个加法就知道了它的系数，更新到下标即可。

P7113（*<2000，拓扑排序）：直接拓扑排序，模拟分数即可。值域：分母不超过 60^最大层数，因为可以归纳证明，每层到下一层都会最多乘 60=lcm(3,4,5)。分子最多是分母的 n 倍。所以 int128 可以开下。

P7114（*2200，哈希，二分）：先预处理出后缀的 f 函数。枚举 AB，维护一个 qzh 表示当前所有的 A 的 f 值的前缀和。二分出 AB 可以连接几次（可以使用判断 [1,(len-1)·i] 与 [i+1,len·i] 是否相等来判断连接 len 次是否可行），再枚举所有可行的 C，使用 qzh 得到答案。注意到两次 ABAB 可以抵销，所以 C 可能的 f 值只有两种，不需要枚举。另外 qzh 可以树状数组维护。所以这个做法的复杂度是 O(sum log n/i + n log 26)=(n log 26)。写这个文章的时候发现一个性质是，查询的位置每次只加减 1。因为对于 AB 出现奇数次的，相当于出现一次，而每次 AB 只会移动 1，因此 f(C) 也只加减 1。对于 AB 出现偶数次的，f(C) 与整个串的 f 相同，f(C) 不变。这样每次修改只需要开一个桶、记录当前询问的答案即可。每次移动减去或加上桶的值即可。

P7914（*2200，区间 dp）：之间就做过，重新做了一遍。显然需要区间 dp。可以发现有的时候需要转移的区间要求两边匹配，有的时候不需要，因此设两个状态表示匹配或不匹配的方案数。转移比较简单。可以使用前缀和优化。

11.23

P9748（*<2000，模拟）：whk 的时候随便做的。第一问直接模拟就行。第二问发现如果 n 不被取，则下一次它的编号还是苹果个数。所以也直接模拟看什么时候它被取了。

P9749（*<2000，模拟）：问题等价于每次可以在已经走过的加油站中的任意一个加油，因为当前需要的提前加上没有坏处。因此直接贪心，每次缺油的时候加油即可。因为如果不缺油还加油没必要，下一次加油肯定比这一次更优。

11.24

CF1781D（*1800，思维）：答案肯定大于等于 1。如果答案大于等于 2，则一定会有 i,j 满足 ai+x=y^2,aj+x=z^2。作差，ai-aj=(y-z)(y+z)，可以暴力枚举 ai-aj 的因数，并检查。

P9751（*2100，同余最短路）：在 k 的整数倍时间出发可以看成在 0 时刻出发，在任意时刻等待 k 时间。考虑对每个点建 k 个点，表示在时间模 k 为该值的情况下到达的最早的时间。直接跑最短路，按照上面的方式加时间即可。

P9750（*<2000，模拟）：直接模拟。

12.7

P5180（*2800，支配树）：算法详见：《IOI 2020 中国国家候选队论文集》的《浅谈支配树及其应用》。

12.8

P2597（*2500，支配树）：是上一题的弱化版，在 DAG 上的支配树。可以直接用上面的做法做，也可以按照拓扑序动态维护支配树，一个点的 idom 一定是能到它的点在支配树上的 lca。

12.9

CF1898D（*1900，思维，二分）：可以把绝对值看成线段的长度。考虑固定 ai,bi,bj 的大小关系，看 aj 在什么时候对答案贡献最大。随便讨论一下就可以知道，这里不细说了。条件大概是在 bj 与 ai,bi 满足某种大小关系时 aj 或 bj 最小或最大。可以二分或者使用数据结构维护。

CF1899G（*1900，dfs 序，树状数组）：求 dfs 序，并把 pi 替换成 dfs 序。这样问题就可以转化为求区间内是否有值域在某个区间内的数。可以离线树状数组解决。

CF1854C（*2500，思维，dp）：考虑对每个数计算到达下一个数或者超过 m 的期望次数。可以发现，除了这个数和下一个数，剩下的数不用管。因为比它小的数永远不会超过它，下一个数如果顶到下下一个数了，那下下一个数可以看成下一个数。所以只需要对两个数求答案，可以直接 dp。

12.10

CF1858E1&CF1858E2（*2500,2600，主席树）：考虑每加一个数就新建一个版本，维护值域线段树，同时维护一个加法的序列表示主席树的根。减法操作直接将序列长度减 k 即可。复原时对于加法需要额外记录加法前的数，这样就可以直接复原；对于减法直接将序列长度加 k 即可。

CF1859E（*2500，dp）：考虑一个暴力 dp，dp[i][j] 表示前 i 个数总长度为 j 的价值总和最大值。转移的时候枚举 i 的区间，直接转移。因为转移的时候区间都是要选的，所以将 j 改为 i-j 会使转移时的 j 不变。而且还可以发现，将绝对值拆开分 4 种情况讨论可以覆盖到所有情况，且不会把答案算大。因此枚举 j，维护四种情况的最大值即可。

CF1866K（*2500，树的直径，李超线段树）：首先求出原树的直径。显然，新的树的直径为 max(原树的直径,过 x 的路径最大值)。首先可以通过换根 dp 求出每个点开始的路径最大值和次大值（两个值走出的邻居不一样）。对于每个 x，考虑离线处理。对 x 的所有邻居求出从 x 到邻居再走出去的最长路径（通过 dp 值求），可以将问题转化为：平面上有若干条直线，求横坐标为 x 时纵坐标的最大值和次大值。可以考虑先求出最大值以及位置，再在位置两边离线求前缀、后缀的最大值。取个 max 就是次大值。

P4313（*2600，最小割）：考虑使用最小割来解决这类每个点有两种选择的问题。首先将 a,b,c,d 都求和，再减去得不到的。每个点连 s 和 t，割哪条边就是选哪个。再新建一个点表示全选文科或理科的贡献。新建一个点与 s 连接，边权为 c，再连接一个点以及相邻的点，这样只有这些点都连向 s 才不会割边权为 c 的边。另外也不会出现新建的点影响连通性的问题，因为如果一些点全割了 t 的边，则在右边新建的点也必然要割。

P3227（*2800，最小割）：考虑对每个点新建 r-1 个点，连接起来并连接 s,t，这样产生了 r 条边，割哪条边就相当于选哪个位置。考虑对于每个两个相邻的链，对任意一个点往回连长度为 d-1 的边，这样就恰好满足了绝对值的限制。而且，对于任意满足的方案在图上也是不连通的，因为差距满足传递性。

CF1592F1&CF1592F2（*2600,2800，差分，二分图最大匹配）：首先 (n,1) 和 (1,m) 的操作一定没有用。考虑从 (n,m) 到 (1,1) 差分，这样 (1,1) 的操作相当于单点修改，(n,m) 的操作相当于修改 (i,j),(i,m),(n,j),(n,m)。首先可以发现，如果 i 或 j 重复出现，一定不优，因为相当于花了 4 的代价改了 4 个点，不如单点修改。先不考虑 (n,m)。发现只有 (i,j),(i,m),(n,j) 都为 B 的时候修改才更优，贡献为 1。否则贡献为 -1，即使算上 (n,m) 也是 0。而且如果贡献是 1，即使让 (n,m) 从 R 变成 B 了贡献也是非负的，所以能操作就操作。因此对 i,j 连边，求二分图最大匹配即可。对于 F1，只会操作一次 (n,m)，直接枚举检查是否存在四个点都是 B 的即可。

12.11

acc round 1 T2（*2600，最小割）：如果 k=1 就是最小割。考虑判定。跑最短路，对每个点求出走到这个点的最少的地雷。考虑建立分层图，并对每个点的入点连向下一层的出点，意思是经过了这个点，增加了路径上的一个地雷。这样的正确性证明是：对于最优方案，在经过这个点最小的地雷这一层割掉这个点即可。对于不合法的方案，根据最短路，一定存在一种方案从 s 流到 t。这个做法本质上是将最短路的过程放到了最小割上，所以一定是正确的。

acc round 1 T3（*2800，dp）：先按 a 排序。考虑使用如下方法生成这个图：加一个右部点，没有任何边；加一个左部点，连向所有右部点。考虑最终环在这些点中的体现。它会形成若干条链。设 dp[i][j] 表示环在前 i 个点中的体现是 j 条链。如果当前是右部点，可以选择新增一条链或不新增。如果当前是左部点，因为这个左部点连接的点恰好就是这些右部点，所以它必须合并两条链。考虑钦定链是有方向的，因为如果没有方向，合并的时候长度大于 1 的链和等于 1 的链的贡献不一样。而钦定后就很好合并了。答案是每次更新左部点前的 dp[i][1]，因为加上左部点后恰好形成了链。

P2053（*2500，最小费用最大流）：考虑对每个技术人员新建版本，表示在修倒数第 x 辆车的他。对于一个人的倒数第 x 辆车，贡献为 x·时间。直接连边，在每个人都有技术人员的情况下求费用最小即可。

12.12

AT_arc132_e（*2600，计数，期望）：观察最终形态，考虑最后一个人，一定会把他左边覆盖成 < 或者右边覆盖成 >。所以最终的形态一定是 <<<->>>，中间的是两个 . 之间原来的形态。因此考虑枚举中间的位置，现在将问题转化为了有若干个点，求将所有的点的左边都变成 <，且不涉及最右的点往右的部分的概率。如果求出来了这个，因为两边互不涉及，所以直接将左右两边乘起来就是全部的概率。设 dp[i] 表示 i 个点时的答案，可以发现，每次只需要保证不将最后一个点向右走即可。所以 dp[i]=(1-1/2i)·dp[i-1]。这样求出概率后随便计算一下 < 的个数即可求出期望。

CF1253F（*2500，最短路，并查集，启发式合并）：如果走到了一个 >k 的点，都可以走到距离它最近的 <=k 的点（设距离为 dis[i]）再走回来。如果走不到，则它无论如何都出不去。而且当前的电池容量不可能大于 c-dis[i]，因为它一定是从一个 <=k 的点走过来的。所以每走到一个点更新一下一定是不劣的。这样每个点的电池容量都是确定的。考虑看一条边 (u,v,w) 是否能走。如果 c-dis[u]-w>=dis[v]，即 c>=dis[u]+dis[v]+w，则能走，否则不能。因此将所有边的 dis[u]+dis[v]+w 作为新的边权，建立 kruskal 重构树，那么 lca 处的点权即为答案。另一种做法是离线，并从小到大加边。每次将询问放到并查集的根上，启发式合并询问即可。通过这道题我发现如果启发式合并的权值与集合大小不相等也是可以合并的，因为每个集合里的元素还是只会被合并 log 次。

CF1876D（*2500，思维，计数，并查集）：首先，红蓝之间没有区别，所以字典序大的个数和字典序小的个数相同，答案即为总方案数减去相等的方案数并除以 2。第二个限制相当于将同值的颜色拿出来后不存在相邻且相等的颜色。发现一个值的相邻两个位置（1 和 2，3 和 4，等等），必须匹配。考虑将这两个位置看成一个区间，这样更加形象。结论：若有一个区间被领一个区间包含，则无解。证明：将区间按左端点排序。考虑找到第一个包含别的的区间，如果只考虑前面的，一定有解。当加入这个被包含的区间时，它一定会在两个序列上都加上一个数。而因为包含的区间已经在一个序列上加入了一个数，这样一定会错一位，就无法匹配了。所以最终是若干个没有包含的区间，而且这样一定有解。可以发现过程比较像队列，先进先出。发现对于区间的并覆盖全了的一段，确定了第一个放在哪里就确定了所有。将这样的若干个区间拿出来。这些区间之间也有限制关系。如果一个数同时出现在两个区间，则这两个区间确定了一个另一个也就确定了。所以将这些互相限制的区间连边，求连通块个数，那么 2 的这个数次幂就是相同的个数。

CF1446D1&CF1446D2（*2600,3000，思维，根号分治，双指针）：发现答案的众数中必然有全局众数 m。因为如果没有，则可以往左右扩展，直到 m 的出现次数赶上当前的众数了。根据这个思想，问题转化为了求一个区间，使得存在一个数的出现次数等于 m 的出现次数（如果这里有比 m 大的，就可以扩展）。考虑根号分治，对于出现次数大于根号的将这个数设为 -1，m 设为 1，其他设为 0，即求一个最大的区间使得和为 0，可以 O(n) 求出。对于出现次数小于等于根号的，直接枚举出现次数，这样就可以双指针出 m 出现这么多次的区间。这个区间一定是越大越好。得到区间后检查剩下数的出现次数最大值是否大于等于枚举的次数即可。有一种 O(n) 的做法。直接枚举另外的众数 x，现在希望在 O(x 的出现次数) 的时间内求出 x 和 m 的出现次数相等的区间长度最大值。考虑求出所有可能作为区间中的一个的 m 的位置。发现只有存在它作为左端点或右端点的区间满足 x 的出现次数大于等于 m 的出现次数，m 才是有希望的（如果两边次数都小于，则在最终的区间内次数之和也是小于的）。因此考虑从左到右枚举 x，将向左第一个之前不是有希望的 m 设为有希望的。再向右做一遍。这样做的正确性的证明是：有希望的 m 与 x 会组成若干个区间，表示它们的出现次数相等。找到的 m 与 x 之间的出现次数一定相等，且别的点之间的出现次数一定不相等（否则会被合并）。再从右到左做一遍，就可以得出所有有希望的 m。将这些 m 和 x 放到一起，再用 -1 和 1 的算法做即可。但是这样需要排序。考虑将枚举顺序改变，从右往左枚举 x，这样找到的 m 不变（可以把区间提出来，利用前缀和证明），而序列已经排过序了。接下来只需要归并即可。

12.14

P9058（*3000，支配，点分治，树状数组）：对于求数对的最值问题的题可以考虑是否有一些对被其他对支配。在这道题，支配的定义是 (a,b) 支配 (c,d) 当且仅当 c<=a<=b<=d 且 dis(a,b)<=dis(c,d)。考虑点分治，将问题转化为有若干个数，每个数有下标和权值，求一些可以支配其他的对。考虑钦定枚举对中 dis 较大的那个。结论：找到下标比它小且最接近它的、dis 比它小的点和下标比它大切最接近它的、dis 比它小的点。那么剩下的对都不可能成为答案。证明：如果剩下的对成为了答案，比如有 a<b<c 且 dis[a],dis[b]<=dis[c]，那么 (a,b) 一定优于 (a,c)。因此找到这些对，根据点分治，只有 O(nlogn) 个，并离线树状数组维护即可。

12.15

acc round 2 T1（*2500，思维，dp，矩阵快速幂）：考虑直接在操作过程中维护折痕，设相同为 0，不相同为 1。容易证明，每次操作是将两个距离为 k 个点改为 1，中间的改为 0。可以发现最后一次操作一定会产生一个距离为 k 的相邻的两个 1。进一步思考，如果之前的操作在最终不是相邻的两个距离为 k 的 1，一定被之后的操作覆盖了。如果这两个对的距离 <k 就会被覆盖。因此，最终的折痕合法当且仅当从一个 1 出发一直往左走或往右走，可以在不走到距离大于 k 的点走到距离等于 k 的点。根据上面的分析，这个结论是容易证明的。注意，0 和 n 的位置可以看成 1。考虑 dp，设 dp[i][0/1] 表示第 i 个为 1，i 与前面组成的极长距离 <=k 的段中是否有距离等于 k 的。转移直接枚举上一个 1 即可。考虑使用前缀和优化。可以发现，每次转移只需要前面 O(k) 个值，因此可以矩阵快速幂优化。这里有一个套路：多次询问的矩阵快速幂可以优化成 O(k^3 logn + T k^2 log n)。这是因为，发现快速幂中统计答案的变量是一个向量，而向量成矩阵是 O(k^2) 的。另一个变量可以预处理。

acc round 2 T2（*2700，kruskal 重构树，dp）：求 d 的过程就是 kruskal 重构树干的事。所以根据 d 可以求出 kruskal 重构树。具体来说，先将每个 d 值合并的两个连通块求出来（可以二分图染色），然后按两个连通块大小之和排序，因为每次合并连通块大小都会增加。接下来根据连通块的形态就能求出来每个点是由哪两个点合并上来的了。对于树的部分分，直接求出一个树的拓扑序个数即可。这个问题可以 dp 或者 n!/prod siz[i]。考虑剩下的边，可以发现这些边的限制是：找到将这条边的两个点合并成一个连通块的边，那么前者要在后者出现后。可以将这个问题转化为，在一个树加上若干条从非树上的点到树上的点的边，求这个 DAG 的拓扑序个数。考虑 dp，设 dp[i][j] 表示第 i 个点的子树中，有 j 个非树上的点的出现位置在 i 后面时子树的排列个数。这个状态看上去比较难理解，但是如果将点的排列看成从叶子到根逐渐将一个点插到某个位置，这个状态就合理了，这个状态的意义是确定了 i 这个点在排列中的哪里。考虑对于 i 的一个儿子 v，从 dp[v] 推到 dp[i]（假设它只有一个儿子），因为 i 可以插在 v 之前的任意一个位置，而 v 之前都是 j 这里面的，所以直接将 dp[v] 求一个后缀和即可。对于多个儿子，可以做一个树上背包进行合并。直接将在 i 之前的和在 i 后面的分别合并即可。最后还要加上连向 i 的这些点，这些点必须要在 i 的后面，所以直接与在 i 后面的那部分合并即可。

12.16

P4141（*<2000，dp）：考虑先求一遍背包。因为背包插入的顺序无关，所以可以直接撤销。

P8392（*2600，dp）：对于最多的问题，可以考虑先全加起来，再变成求最小。这样的好处是最小会有一些性质，比如重复经过某个状态，对于最小可以直接忽略掉。考虑先求出全选的总和。接下来的算法假设总和大于 l。如果小于等于 l 是同理的。一直删除最大的，直到让总和在 [l-m,l] 之间。考虑调整，每次加入或者删除一个数，使得总和在 [l-m,l+m] 之间。结论：如果总和重复，则这之间删除的数大于加入的数，即总和不能重复。证明：在这之间，如果让总和增加了，一定是删除负数或者增加较大的正数。否则一定是删处较小的正数。因为较大的正数比较小的正数大，所以较小的正数需要的更多。这样总和只能在 [l-m,l+m] 之间且不能重复，说明一共只会调整最多 2m+1 次。这样就可以跑多重背包了。

CF1603E（*3200，dp）：https://www.luogu.com.cn/blog/wangxiwen/solution-cf1603e。

12.17

THUPC 2024 初赛 D（P9964）（*2500，区间 dp）：直接区间 dp 是 O(n^3) 的。考虑所有满足条件的位置，猜想这样的位置较少。枚举的过程本质上是求每个点向外延伸的长度总和。感性理解一下，这个数很小，可能是 O(n) 或 O(nlogn) 级别的，因此总复杂度只会再乘个 n。不会证明。

12.18

acc round 3 T2（*2600，网络流）：考虑按边权从小到大在网络流上加边，并动态维护网络流。但是如果每次都跑一遍 bfs，复杂度是 O(m^2) 的。发现流的大小最多为 n，所以只有 n 次 bfs 会有意义，所以考虑动态维护 s 到 t 的连通性。设 vis[i] 表示 s 是否能到 i。每次加一条边 (u,v)，如果 vis[u]=1 且 vis[v]=0，则将 vis[v] 以及 v 能到的、vis 等于 0 的点的 vis 设为 1。每次增广重构 vis。这样在两次增广之间总复杂度为 O(m)，而每次增光的复杂度也是 O(m)，总复杂度为 O(nm)。

12.19

acc round 3 T3（P7294）（*2800，保序回归，单调栈）：考虑设每一列的最后一个点为 wz[x]，推式子后会得到 wz[x]<=wz[x+1]，且要求 sum (wz[x]-v[x])^2 最小的东西，其中 v[x] 是推式子得到的参数。这就是一个保序回归的板子。算法详见：《国家集训队 2018 论文集》——《浅谈保序回归问题》。这样将询问离线下来，在单调栈上二分，动态维护前缀和即可。感觉正解的凸包和这个本质上差不多，大概都是将一些不满足大小关系的位置放到一起，直到满足大小关系。

P5336（*2700，dp）：设 dp[i][j][k][l] 表示区间 [i,j] 中删除若干个数，使得剩下的 min=k,max=l 的最小代价，ans[i][j] 表示区间 [i,j] 都删除的最小代价。这个状态的好处是可以体现删除区间后将左右合并这个过程。考虑转移，看 j 是否在删除的区间内。如果 j 是删除的，则枚举哪一个区间将 j 删掉的。否则可以从 [i,j-1] 这个区间推过来。使用刷表法。

AT_agc035_d（*2600，dp）：首先，最后剩下的两个数一定是 1 和 n。考虑最后一次删除的数是什么，这样就可以将区间划分成两半。因为最后的贡献都是给到两边的，所以可以对于每个区间记录，左、右端点的值会乘以多少倍加到最终的答案。如果当前区间 [l,r] 的上述值分别是 [a,b]，则到左边会变成 [a,a+b]，到右边会变成 [a+b,b]。直接大力记录下来就是对的，因为这两个值会形成一个二叉树结构。

CF573B（*1600，思维）：设 ans[i] 表示将第 i 列消去需要的操作次数。考虑这一列如果不因为周围两列减的更多，则答案就是 h[i]。否则，考虑它最后一次因为周围两列减的更多的时候，它的答案就是周围两列的答案加 1。因此可以正着推一遍，反着推一遍，就可以得到答案。

qoj 5407（*2800，竞赛图，强连通分量）：考虑求整张图的强连通分量。在这样的链状结构上如果修改的边在不同的强连通分量，如果两个强连通分量挨着且大小都为 1，答案不变，否则答案减少它们的距离。接下来只需考虑在一个强连通分量里的答案。结论：在竞赛图中一个强连通分量中存在哈密顿回路，且可以在 O(n^2) 的时间内找到。证明：考虑归纳证明。任选一个点 x，剩下的会组成一个链状结构。那么剩下的强连通分量都有哈密顿回路。因为最终会形成强连通分量，所以 x 到第一个强连通分量有边（设那个点为 a），最后一个强连通分量到 x 有边（设那个点为 b）。直接将第一个强连通分量的哈密顿回路从 a 开始，中间的任意排列（因为前面的强连通分量任意点到后面的任意点都有边），最后一个的哈密顿回路到 b 结束，再加上 x 即可得到新的哈密顿回路。所以对每个额强连通分量求出这个哈密顿回路，如果不在哈密顿回路上的边不会对答案改变，在上面的有两种算法，一种是直接 O(n) 求一遍，因为这种边只有 O(n) 种。另一种是在哈密顿回路上差分。

12.20

CF573B（*1600，思维）：对于一列，记录消除这一列需要的次数。那么 dp[i]=min(h[i],min(dp[i-1],dp[i+1])+1)，因为如果不是一个一个消的，一定存在一个时刻它跟随着旁边的脚步。这样正着、反着转移一遍即可。

CF1268D（*3200，竞赛图，强连通分量）：结论 1：如果一个竞赛图强连通分量大小 >=4，则存在一个点使得将这个点的出边翻转后仍然是强连通分量。其实这个结论的充分条件是存在一个点使得剩下仍然是强连通分量，因为这个点与剩下的一定存在一条正向的和一条反向的边，那么翻转后也仍然存在。证明：任取一个点，删掉这个点，剩下的会形成一条由强连通分量组成的链。考虑找到这个图的一条哈密顿回路。如果剩下的强连通分量大小都为 1，则随便删一个就行。否则删除一个强连通分量在哈密顿回路的第一个或者最后一个就行。结论 2：如果存在一个强连通分量大小 >=4，则答案最多为 1。证明：将这个强连通分量使用结论 1 翻转使得剩下的还是强连通分量。这样，这个强连通分量存在两类点，它既可以被别人到也可以到别人。结论 3：如果存在 >=3 个强连通分量，则答案最多为 1。证明：在中间的强连通分量中任选一个点，翻转。这样，对于任意点，可以先到最后一个强连通分量，再到这个点，再到第一个强连通分量。接下来就想去哪里去哪里了。综合以上两个结论，可以发现 n>6 时答案最多为 1。所以当 n<=6 时暴力做，n>6 时枚举点，更新每个点的度数，并按度数排序（顺序和强连通分量链上的顺序相同），检查是否有一个非全部的前缀使得度数之和为 i·(i-1)/2（这意味着这个前缀是一个强连通分量）即可。

CF1082E（*2000，思维）：因为 k 是任意的，所以区间内等于 c 的个数就是出现次数最多的数。枚举这个数，问题转化为选择一个区间，选择 l 有某个贡献，r 有某个贡献。直接扫一遍记录 l 的最大值即可。

12.21

CF527E（*2600，欧拉回路）：对于这种问题，可以考虑先满足最基本的条件，然后猜想答案增加不了多少。因为出入度都是偶数，所以看成无向图后度数为偶数，即存在欧拉回路。所以先把奇点两两连边。还可以发现每个点的入度或出度总和是边数，所以如果边的个数是奇数也不合法。可以使用自环将边的个数变为偶数。接下来，对这个图求欧拉回路。令相邻的两条边方向相反。因为边数为偶数，所以这么做是对的。

CF547D（*2600，二分图，欧拉回路）：做法 1：对于同行、同列的相邻的两个连边（1 与 2 连边、3 与 4 连边等等，注意，2 与 3 没有边），这样如果能保证连边的两个颜色不同即可满足条件。因为对于每一个环，每走一条边方向都切换，所以这是一个二分图，一定能染色。做法 2：考虑将行、列看成点，点堪称边。对于点的度数为奇数的点，连向 0 号点。如果 0 号点度数是奇数，连一个自环。在剩下的图中跑一个欧拉回路，对于不包含 0 号点的，边数为偶数，直接相邻的边染不同的色即可。否则，让矛盾的两条边在 0 出发生即可。

CF1338E（*3500，竞赛图，强连通分量）：最开始写的是推一堆性质的做法，这里不写了。有一个比较优美的做法。首先 dis<=3，因为如果有一条长度为 4 的链且不存在更短的，那么一定有 3->4, 4->5, 5->3, 3->1, 4->1, 5->1 这些边，不满足图的性质。考虑对竞赛图缩点。结论：除了最后一个强连通分量，其他的大小为 1。证明：因为是竞赛图，所以大小不能为 2，那么一定存在一个哈密顿回路，在这里面一定存在一个三元环（每次选择一条内部的边，这样可以切割成更小的环），并都连向后面的点，不满足图的性质。这样除了最后一个强连通分量，其他的都容易算出来。考虑计算两点距离为 2 的个数。对于两个点 u,v（v->u），如果存在 a 满足 u->a,a->v，则这两个点的距离为 2。可以发现，这三个点组成了一个三元环，与图的性质有联系。如果存在一个点 b 使得 u->b 且 a->b，那么一定有 b->v 否则不满足图的性质。

12.23

P3546&CF961F（*2600，哈希）：枚举第一个 border 的长度，发现如果长度加一，第二个的长度最多减二。考虑倒过来做，那么长度最多加二。这样可以直接将长度加二后再减下去，可以证明复杂度是对的。

12.24

P9993（*2500，分块）：直接分块，维护块内每个值的值和历史最大值。排序，并将历史最大值求一个前缀最大值。对于整块加，对块内维护加的总和和加的总和的历史最大值。对于散块，直接重构即可。

12.25

CF1893D（*2600，贪心，堆）：考虑每一次都放不相同的 di 个来满足条件。这样放是充要的，因为一定存在一种方案使得先后两次 di 个的区间都没有重复。每一次看当前区间里是否有上一个区间的最后一个，如果有，就把它放到最后一个，以此类推。这样，显然每次将出现次数最多的数选 k 个放上去是最优的，因为这样可以使剩下的种类尽可能多。

12.26

P9994（*2500，根号分治）：把 x 相同的点放到一个集合，对集合大小根号分治，并对每个 y 维护所有 x 所在集合大小小于根号的点的点权和。如果集合大小小于根号，暴力修改并更新点权和；否则维护指数。查询时遍历大于根号的块，使用快速幂求出来真正的值即可。

12.27

P9990（*2800，线段树，历史版本和）：离线，从左到右遍历每个 r，并对每个 l 维护 [l,r] 数的个数的奇偶性。每次移动 r 会将一段区间取反，最后要查询的是某个区间的历史版本和。直接用线段树维护历史版本和即可。

P6242（*3000，吉司机线段树，历史版本和）：模板题，详见题解和我的代码。

12.29

P6893（*2600，思维，dp，堆）：分别维护连续食物和离散食物重量和为某个值时的答案。对于离散食物，可以对每种 w 相同的计算吃 i 个的最大收益。将所有食物放到堆里，每次取出当前最大收益的即可。对于连续食物，相当于有若干条直线，收益是前缀的面积。同样可以每次取出最大收益，直到这条直线与下一条直线相交。此时选择方式应该是两条一起选，所以考虑将这两条直线合并，变成新的并再放到堆里即可。

1.19

CF1912B（*2000，思维，组合数）：发现每一种距离会出现 2k 次，而且最优方案一定是每次增加一个距离的。那么可以计算出距离的最大值，然后考虑距离的最大值该怎么填。枚举填两个的个数，那么剩下填一个的就确定了，随便使用组合数计算一下就行了。

CF1920F1&CF1920F2（2500,3000，建图，启发式合并）：对于弱化版，可以二分后暴力检查。对于强化版，考虑如何判断一些点是否围了一圈。考虑从连通块出发，随便向某个方向画一条线，那么如果一条回路恰好经过这条线一次，则它包围了连通块。所以对每个点建立两个点，如果过这条线就连 01、10，否则连 00、11，如果一个点的 0 和 1 连通了，就说明存在一条经过它的回路。因此考虑离线，按照距离从大到小加入点，并在过程中启发式合并，暴力检查连通块中的点即可。

CF1469E（*2400，字典树）：考虑对 a 中所有长度为 k 的子串建立字典树，那么 b 中选 0 相当于管了左边，选 1 相当于管了右边。是否有解等价于字典树是否是满二叉树。发现 b 的前 k-log 个必然是 0。对于剩下的，如果 a 中的子串前面都是 1，则对它的后 log 个建立字典树。每一次看当前选择是否会导致接下来是满二叉树即可。

CF1450F（*2400，思维）：先判断无解，无解等价于众数出现次数大于 (n+1)/2。可以考虑将众数放在那里，然后插入别的数，这样就比较好证明。将每个 p[i]=p[i+1] 的位置断开，形成若干个段。那么这些段想要重排，等价于这个帖子中的问题，不过我还不会证明。那么如果超过 n+1，每次可以选择断开一个位置，使个数减一。所以答案就是个数-(n+1)。

CF1443E（*2400，康托展开）：显然 P 的前 n-O(1) 个数都是不会改变的，只需要考虑后面的数。记录往后的排列个数，使用逆康托展开即可求出最后 O(1) 个数。区间查询使用公式求出前面的数的总和，再暴力求出后面的数的总和即可。

CF1428F（*2400，分治，二分）：考虑分治，那么要求的东西形如 sum(i) sum(j) max(ai,aj,min(j,R)-max(i,L)+1)。枚举 i，发现后面的东西有单调性，所以可以求出 ai 取到 max 的一段区间。对于后面，如果 j<=R，可以发现一定是 min(j,R)-max(i,L)+1 取到 max。否则，后面的是定值，可以二分求出 aj 取到 max 的一段区间。使用前缀和即可得到答案。另一种做法是枚举右端点，维护左端点的答案总和。对于当前的 1 的个数，需要得到上一次达到 1 的个数的位置，然后在这区间内的左端点答案都可以加一。可以使用一个数组记录达到 1 的个数的位置，每次遇到 0 了就将上面这个 1 的区间的贡献放到数组里。

1.22

P10060（*2200，dp）：f 相同的会形成一个连通块，而这些连通块会形成一个新的树。可以直接在这个新的树上 dp。dp[i] 表示 i 是 i 所在连通块的 a，这个连通块的子树的方案数。可以枚举连通块的儿子和那个连通块的 a（j），并判断是否满足条件。分讨一下 i 与边的距离和 j 与边的距离即可判断。

CF605C（*2400，凸包）：考虑将 (ai,bi) 放到平面上。结论：只有凸包上的点有可能被使用时间。证明：对于一个不在凸包上的点 C，若它的横坐标在 A、B 之间（这两个点都在凸包上），则 A 和 B 可以通过加权偏序掉 C。结论：只需要对凸包上的相邻两点求答案即可。证明：和上一个证明类似，若有两个不相邻的点同时被使用时间了，那么中间一定有一个点可以偏序掉这两个点的加权。所以求出凸包，对相邻两个点求答案即可，这里可以解二元一次方程。

CF822E（*2400，dp，二分，哈希）：考虑一种贪心：遍历每个 s 中的字符，那么这个字符要么不匹配 t，要么选一个最长公共前缀匹配 t。正确性证明：如果不选最长公共前缀，以后匹配的可以提前到当前匹配而且不劣。所以使用 dp 来实现这个贪心。设 dp[i][j] 表示 s 的前 i 个字符分成 j 段匹配 t 的前缀最大长度。使用填表法，每次可以跳过，或者使用二分哈希求出最长公共前缀。

1.23

CF582C（*2400，思维，二分，哈希）：对于一个循环节长度为 a 的序列和一个循环节长度为 b 的序列，a 的每个位置都大于等于 b 等价于 a 中的模 gcd(a,b) 相等的等价类的最小值大于等于 b 中模 gcd(a,b) 相等的等价类的最大值。所以可以枚举 gcd，对每个数检查它是否可能成为这样的数。然后枚举 l%gcd(a,b) 的值，对每个块看它是否可能成为序列中的一段，将环上的极长可能成为序列中的一段的连续段找到，并随便求一下答案。

P9965（*2500，思维，贪心）：先考虑第二问。对于 ai!=0 的颜色，显然需要将 ci 都用完，这样肯定不劣。接下来考虑将 ai=0 的颜色用上 ci。对于每个 ai!=0 的颜色，贡献是 min(bi,ai+ci)，这些球可以对一个 ai=0 的颜色给一个球，并产生 ci 的贡献。同时，它也会可以出去的球的总和造成 min(bi,1+ci)-1 的贡献。所以，对于 ai=0,bi!=0 的球都可以给一个球，不会劣。对于 ai=0,bi=0 的球，按 ci 排序，并依次给它们即可。对于第一问，和第二问类似。同样维护一个可以出去的球的个数，这些球既可以贡献到 ai=0,bi!=0 的位置，也可以给到当前颜色。对于 ai=0,bi=0 的球可以不用管，因为给它也出不去。

CF1909G（*3000，字符串，二分，哈希）：题解：https://www.luogu.com.cn/blog/wangxiwen/solution-cf1909g。

1.30

1.24~2.5 之间的比赛题目在游记中写了。

CF1924C（*2400，思维）：发现除了第一次对折，剩下的每次对折对两边产生的贡献是相等的。因此只需要求出总共的折痕长度，推一下式子可以发现这是一个等比数列求和，使用公式即可。可以实现一个 a+sqrt(2)b 的类，否则需要进行分母有理化。

1.31

P5960（*2000，差分约束）：这题在我打板子的题单内，但是我之前没做过，所以当做一道新题写一下。a-b<=c 这个不等式可以理解为 b 到 a 连一条边，边权为 c，那么 dis[a]-dis[b]<=c。所以这么连边之后设一个虚点，将这个虚点到每个点连一条边权为 0 的边，求虚点出发的最短路即可。如果出现负环了，可以将环上的不等式相加，会得到 0<=负数 这样恒不成立的式子，一定无解。

2.3

CF1198F（*2900，随机化）：考虑维护两个集合，并依次对每个数考虑它加入哪个集合。如果它模第一个集合的 gcd 为 0，一定加入第二个集合；如果它模第二个集合的 gcd 为 0，一定加入第一个集合。否则，考虑随机选择一个集合放进去。这样，每次两个 gcd 中的一个会除以 2，决策的次数最多为 2logV。因此随机若干次大概率能找到。这样已经可以过了，但是发现 gcd 里面我们不需要考虑一个质因子出现的次数，只需要考虑它是否出现过，这样就可以将 logV 降成 max w(V)。这样就更对了。

2.6

CF1922F（*2500，区间 dp）：详见我的题解：https://www.luogu.com.cn/blog/wangxiwen/cf1922f-ti-xie。

2.7

CF1918F（*2500，思维）：发现 k=0 时答案为 2(n-1) 减去与 1 的距离最大的点的距离。考虑路径的形态，一定是在一个 dfs 的过程中将若干个到达叶子的时候直接变成根，再走下去。k=0 的做法启示我们，每搜索一个子树最后要停留到与 1 距离最大的点。那么对于一个点的若干个子树，与 1 距离最大的点所在的子树最后走，对其他的子树计算使用一次 2 操作可以带来什么贡献。设这个子树内与 1 距离最大的距离为 a，当前点与 1 的距离为 b，则贡献为 a-2b。将这些贡献放到一个数组里，取前 k 大减去即可。考虑如何证明每次停留到与 1 距离最大的点。画一个图可以发现，这个问题本质等价于将数列中的两个数 a,b（a>=b）让 a 减去 c，b 加上 c，且满足 b+c<a，证明改变后数列的前缀和小于等于改变前数列的前缀和。因为 b+c<a，所以这个问题等价于若干次 a 减一，b 加一且始终满足 a>=b。而因为 a,b 的相对位置不变，这个问题是容易证明的。

CF1917F（*2500，思维，dp，bitset）：考虑确定一条直径后，最优的策略一定是加上一个菊花。所以可以将问题转化为：判断是否可以选择若干个总和为 d 的点，使得这个点集可以分成两部分，总和较小值大于等于剩下点的最大值。将数组从大到小排序。考虑枚举剩下点的最大值。如果它不是 a[1] 或 a[2]，如果剩下的这些点中可以选出一个总和为 d 的子集，则 a[2]<=d/2（因为 a[1]>=a[2]）。将 a[2] 单独作为一个子集，则另一个补集总和 >=d/2。而 a[2]>= 枚举的点，所以这样满足条件。否则，如果剩下点的最大值是 a[1] 或 a[2]，考虑对剩下的点 dp。设 dp[i][j][k] 表示后 i 个点是否可以选出一个子集使得总和为 j，再在这个子集中选出一个子集使得总和为 k。因为 dp 的值只有 0,1 所以可以使用 bitset 优化。

2.8

CF1917E（*2500，思维，构造）：发现 k=4 和 k=6 都可以构造，考虑用这两个图形组成所有的 k。如果 k=2 或 n^2-2 只有在 n=2 时有解。否则如果 k%4==0 用 k=4 构造即可。否则，先用 k=4 构造，直到还剩 6 个用 k=6 构造即可。k=4 填的时候要留出一个三角而不是一行。

CF1737F（*3300，思维，构造）：详见我的题解：https://www.luogu.com.cn/blog/wangxiwen/cf1737f-ti-xie。

2.9

CF1919E（*2600，dp）：考虑画出折线图。考虑从大到小加入点，发现可以看成对某个最底的位置添加一个向下再向上的折线。所以设 dp[i][j][0/1] 表示考虑 >=i 个数中，i 这个数有 j 次，剩下的数有原来那么多次。使用组合数算出每个 i+1 下面要画多少个向下再向上的折线即可。0/1 表示当前这个数是否占据了最后一个位置，是细节。

2.10

CF1906B（*2600，思维）：放到前缀和下考虑。如果 i>1 且 qzh[i]!=qzh[i-1]，将 qzh[i-1] 和 qzh[i] ^=1。如果 i=1 且 qzh[i]=1，将 qzh[2]~qzh[n] ^=1。发现第一个操作本质上是交换前缀和相邻元素，所以如果只有第一个操作只需判断 0 的个数是否相等即可。加上第二个操作算一下操作之后的 0 的个数再判断即可。

CF1905F（*2600，思维，二分，前缀和）：先特判掉升序的数组。交换的两个一定是逆序对，否则一定不优。结论：设最优的交换的为 i,j，则 i 是前缀最大值，j 是后缀最小值。证明：如果不是，则中间的一段都不会满足条件，替换成前缀最大值/后缀最小值更优。结论：如果一个逆序对的区间被另一个逆序对的区间包含（左右端点不能碰到），则它不可能成为最优。证明：对于一个逆序对，中间的一段都不会满足条件，所以交换里面的逆序对不会有意义。考虑取出前缀最大值和后缀最小值的数组，根据结论，对于前缀最大值，与后缀最小值交换可能最优的是一段区间，且相邻两个区间的交集最多为 1。这样暴力对这些 O(n) 个区间求答案即可。求答案：两边是否满足条件不会被影响，可以预处理出来；这两个点的答案易求；可以对这两个点二分求出它们作为前缀最大值的最右、最左位置，在这两个位置之间，如果之前左边恰好有一个比它大、右边恰好有一个比它小，则这个位置可以变成满足条件的。

2.11

CF1898F（*2600，bfs）：详见我的题解：https://www.luogu.com.cn/blog/wangxiwen/solution-cf1898f。

2.12

CF1896F（*2600，思维，构造）：无解：1 的个数是奇数或者 s[1]!=s[n]。考虑如果能将每一对相邻的 1 挨着下一对相邻的 1，则可以构造形如 (()()())（这个构造对应 10000001）这样的使得这一段全变为 0。考虑将问题转化为让 2~n 这一段相邻两个相等。对于相邻两个，如果原来已经相等，放一个 ()，否则放一个 (( 或 ))，根据前面是否有空余的 (( 决定。因为不相等的两个中恰好有一个 1，所以 (( 和 )) 可以匹配。这样构造后再判断一下 s[1] 是否为 1，如果不是就使用 ()()() 翻转整个字符串。最后使用最初说的构造方法即可。

2.14

CF1895F（*2600，计数，差分，矩阵快速幂）：考虑将问题容斥成 min <=x+k-1 减去 max<x。前者的限制只有 min 属于 [0,x+k-1]，而后者的限制是所有数在 [0,x-1]，这两个不一样，所以计数方式也不一样。前者可以根据 n-1 个差分确定这些数的关系，再根据关系将最小值放到 [0,x+k-1] 即可，所以答案为 (2k+1)^(n-1)·(x+k)。后者可以直接 dp，并用矩阵快速幂优化。

AT_arc107_f（*3200，最小割）：考虑最小割。对于一个连通块，先假设每个点都取到了绝对值，然后考虑一个点放入了总和为正的连通块的代价是 2·max(-b[i],0)，负的代价是 2·max(b[i],0)。考虑使用连接源点、汇点来描绘这个代价。中间每个点拆成两个点，左边你的连源点，右边连汇点，中间连一条边表示删掉这个点的代价（a[i]+|b[i]|）。考虑描述一条边的关系。对于 (u,v) 连接 (u+n,v) 和 (v+n,u)。这样可以发现，如果 u 和 v 都不删掉，则它们会形成强连通分量，它们必须同时割左边或右边。而且如果 u 被删掉了，则它的边都作废了（因为它没有出边）。所以这样就描述了整个问题。

P3679（*2800，二分图，霍尔定理，高维前缀和）：根据一些结论的证明中的 9 可知，可以分别对左右的集合判断是否存在一个匹配覆盖它。根据 10 可知，可以对每个集合判断它出边的点的集合大小是否大于等于这个集合的大小，如果小于，就认为所有包含它的集合不存在一个匹配覆盖它。因此可以使用高维前缀和知道每个集合是否存在一个匹配覆盖它。再排序后双指针即可。

CF1572D（*2800，费用流）：这个图是二分图。如果直接建图 n,m 都很大，考虑优化。因为每个点的边数都是 n，所以如果选了一条边相当于将 2n 条边不让选了。因此我们只需要保留前 2nk 大的边。然后将源点拆点可以实现 k 这个限制。剩下的直接跑费用流即可。

CF1383F（*3200，网络流，最小割）：考虑将问题转化为最小割。因为 k 比较小，所以可以预处理出前 k 条边是否割的 2^k 种情况。如果割就将边权设为 0，然后在询问的时候加上，否则将边权设为 inf。但是如果暴力跑复杂度不对。发现边权的值域较小，而且如果不割，可以将边权设为 25 而不是 inf，因为如果设为 25 的时候割了这条边，一定不如设为 <=25 的时候割了这条边。所以可以增量构造，即在 dfs 的过程中加入每条边，并即刻增广。因此边权 <=25 所以答案最多增加 25，那么每次加入边的复杂度为 25m。这样复杂度就对了。

2.15

P10157（*3000，思维，构造）：详见我的题解：https://www.luogu.com.cn/blog/wangxiwen/solution-p10157。

mars round 1 T1（*2300，思维，dp，bitset）：考虑判定每个数最终为正或负时是否能被组合出来。此时每个数只有四种可能：奇正，奇负，偶正，偶负。设这四种分别为 1,2,3,4。根据操作可知一共有 4 种操作：12->3 或 4,13->1,24->2,34->3 或 4。问题转化为是否存在操作最终剩下 1 或 3。首先可以发现 1 的个数要大于等于 2，否则一定会剩下 2。还可以发现 1 的个数最多为 2 的个数 +1，否则会剩下两个 1。剩下的问题，可以根据最后剩 1 还是 3 找到结论，这里不再赘述。这样可以求出 1 的个数和 2 的个数，然后再枚举 3 的个数。先用 dp 预处理出来 1 的个数为某值时可以凑出哪些数、3 的个数为某值时可以凑出哪些数。然后相当于做偶数的个数次卷积。不过可以先将 3 的个数这些直接合并出来，就只需要做一次卷积了。暴力卷积即可。

mars round 1 T2（*2800，dp，李超线段树）：首先可以发现操作之后每个树的深度 <=2，即不可能连了一个已经练过的点，因为合并更优。设 dp[u] 表示 fa[u] 连进 u 的子树内，u 的子树的答案最小值。同时设 sum[u] 表示 u 的儿子的 dp 之和。每次转移时，记录一个 dis 表示路径上的 sum[u]-dp[v]，到了一个叶子将 dis 加上两个权值之积即可。上面过程可以使用李超线段树合并实现。如果不会也可以使用 dsu on tree。

2.16

CF1929E（*2300，虚树，lca，状压 dp）：赛时的思路是对每个路径集合算出它们的路径是否有交，然后将这些有交的路径拿出来。考虑去掉没有用的，对于一个集合，如果有一个集合包含它且那个集合也满足条件，则这个集合没有用。这个过程可以使用高维前缀和。之后状压 dp，使用填表法，每次对于一个状态 i 遍历集合的状态 j，并更新 i|j。当时觉得这是一个乱搞，但是其实可以证明是对的。考虑对路径的 2k 个点建虚树，那么可以发现满足条件的集合只有虚树的边数，即 O(k) 个。而且更好的写法是对于每个边求出它被哪些路径包含了，那么这些路径的集合满足条件。

CF1929F（*2300，中序遍历，组合数）：对树求出中序遍历，则问题转化为对于一个数组，有些位置是 -1，将这些位置填值使得数组递增的方案数。对于一段 -1，这个问题相当于从 (0,0) 走到 (n,m) 的方案数这个问题，直接组合数即可。组合数的 n 比较大但是 m 比较小所以可以暴力枚举上下 m 个数。

P6189（*2500，dp，根号分治）：这个问题可以转化为背包问题。但背包会 T。考虑根号分治，发现对于比根号大的数一共不超过根号个。设计另一种 dp：dp[i][j] 表示将 i 拆分为比根号大的 j 个数的方案数。每次考虑是否存在根号 +1。如果存在则减去即可转移。否则考虑将所有数减 1，那么不存在的方案数就是将 i 减去 j 后的方案数，也可以转移。将这两种 dp 拼起来即可。

P3287（*2000，dp，二维树状数组）：显然操作的区间是一个后缀。因此可以将问题转化为给序列加上一个单调不降的序列（序列的最后一个值 <=k），使得最长不下降子序列最长。设 dp[i][j] 表示在前 i 个数中第 i 个数在最长不下降子序列中，它加上了 j 的最长不下降子序列长度。转移的时候可以枚举上一个数 a[k] 和它加的值，这是一个二维偏序问题，可以使用二维树状数组。可以优化，发现加上的值与 dp 值有单调性，所以只需要枚举上一个数，它加上的值就是 j 和 a[i]+j-a[k] 的最小值，分讨一下谁更小，可以使用数据结构单 log 求出。

CF1889C1&CF1889C2（2000,2600，dp，st 表）：如果对区间 dp 会比较难办。考虑枚举没被覆盖的点。设 dp[i][j] 表示第 i 个点是没被覆盖的点，删除 j 条边后前 i 个点没被覆盖的最大值。考虑所有包含这个点的区间（如果个数大于 k 一定无法使这个点不被覆盖），如果这个区间覆盖了上一个点，则它不应计入删除的边，否则计入删除的边。可以将这些点按左端点排序，然后枚举区间，表示这个区间的后缀不包含上一个点。这样可以求出上一个点所在的区间和上一个点删除的边，使用 st 表即可转移。st 表支持动态在后面加点。

CF1863F（*2600，区间 dp）：设 dp[l][r] 表示区间 [l,r] 是否可以走到。考虑一个可以走到的区间 [l,r] 可以更新哪些区间。枚举分界点 k，现在需要比较 (qzh[l-1]^qzh[k]) 与 (qzh[k]^qzh[r]) 的大小。求出 qzh[l-1]^qzh[r] 的第一个 1，在这一位上如果 qzh[k] 与 qzh[l-1] 不同则 [l,k] 可以走到，否则 [k+1,r] 可以走到。考虑打两个 tag，tag1[l] 表示所有能以 l 为左端点，走到左边的区间的所有可行的位，tag2[r] 同理。那么对于一个区间 [l,r]，检查 (qzh[l-1]^qzh[r]) 是否与上 tag1[l]，或与上 tag2[l] 后不为 0 即可。

P4590（*2800，dp 套 dp）：首先考虑最长公共子序列是怎么做的。dp[i][j] 表示 s 的前 i 个和 t 的前 j 个的最长公共子序列。注意上面的 dp 可以看成每次加入一个 s 的字符，并将后一维的 dp 值改变。还可以发现，在这个问题中，后一维的 dp 值只有 2^k 种（相邻两个之间差 0 或 1），所以我们可以将这个 dp 值记录到状态中。设 dp[i][j][k=0/1/2] 表示前 i 个字符与奖章串的 dp 值集合为 j，与 NOI 匹配了 k 位。可以刷表法转移。

2.17

P10167（*2800，dp，拉格朗日差值）：首先枚举 x 的位数。发现 f(x) 是关于 x 的多项式，所以考虑使用 dp 求出多项式的系数。注意这里不能直接大力对所有数 dp，因为对于一个算式 x 是相同的。考虑一个暴力 dp：对每个替换成乘号的问号枚举上一个这样的问号，然后计算出这个区间 x 的二项式，并乘上前面的多项式。考虑优化。可以类似哈希的方法，考虑每次加上一个数或者一个 x 系数的变化，可以发现相当于将 dp·now 变成 dp·(now·10+x)。那么维护 dp·now 和 dp 的总和即可。求出系数之后，需要对一个区间求出 k 次幂的和。这是一个经典的拉格朗日差值。

2.18

AT_abc341_g（*2300，凸包，李超线段树）：赛时的思路是二分平均值，检查是否有 j 满足 sum[j]-sum[j-1]>=ave·(j-i+1)。并使用李超线段树求出一次函数在某个位置的最大值。正解是建立 n 个点 (i,sum[i])，那么 [i,j] 的平均值就是 i-1 和 j 之间直线的斜率。考虑动态维护一个凸包，那么与 i-1 挨着的那个点就是 i 的右端点。

CF1380E（*2300，启发式合并）：显然答案为相邻不同颜色的个数。使用启发式合并，合并过程中统计有多少个位置之前不相同现在相同了即可。

P10160（*<2000，思维）：考虑取出所有极长的不存在两个 0 的段。结论：如果这一段中所有 1 不是连在一起的，可以缩成 1 个 1，否则改变不了 1 的个数。证明：后者显然。前者考虑构造。先找到 1 后面的第一个 0。从这里开始找到 01 交替的一段，直到出现了两个 1。那么先操作这一段，再继续找 01 交替的一段，一直这么做就可以变成 1 个 1。而且如果存在两个 0 一定不能穿过。所以找到所有极长连续段算一下答案即可。

P10161（*2200，思维，dp）：首先可以发现，如果括号序列合法，则最优构造为 ()()()...。因为一个括号序列可以看成在一个 ()()() 中间插入若干个 ()()()（可以在之前插入的内部再插入），那么将这些一层一层提出来一定更优。考虑证明非法括号序列的构造一定不如合法括号序列的构造。考虑画出折线图，然后对每个点找到最远的右端点使得这一段是合法括号序列。如果一个点没有就单独划分一段。这样整个序列划分成了若干段。那么一个非法括号序列相当于若干个合法括号序列拼接（容易证明两段之间不可能有合法的）。因为之前的证明一个合法括号序列可以看成若干个 ()()() 的答案之和，那么非法括号序列的答案也是若干个 ()()() 的答案之和，且数量不小于合法的。根据这两个结论，答案可以表示成若干个 ()()() 的答案之和，且可以构造。因为一个 ()()() 的答案在长度的平方级别，所以可以暴力 dp。

P10168（*<2000，思维，构造）：最优情况显然是 000111，且 0 和 1 的个数差为 n%2。不过看样例可以发现，这种情况有可能达不到。当 n 是偶数且 0 的个数与 n/2 不同时，0 和 1 的个数差为 2，因为每次修改 0 的个数奇偶性不变。考虑构造。先从左到中间依次填 0，再从右到中间依次填 1。这样就已经做完了，容易证明这种构造达到最优情况。

P10171（*2300，bitset）：考虑枚举相等的两个数 a[i],a[j]，那么 |a[i]-a[j]| 的因数都不满足条件。由此也可知，如果序列中没有重复元素，比 max a 大的数一定满足。考虑求出 |a[i]-a[j]| 组成的集合。枚举 a[i]，那么将 a[i] 组成的 bitset 右移 a[i] 位即可得出所有 a[j]-a[i]。将这些 bitset 求个或即可。接下来遍历 |a[i]-a[j]| 的所有因数即可。

P10163（*2100，贪心）：首先显然要把所有出度不是平方数的通过连接别的连通块使其变成平方数。此时会有两种可能，一种是变成了一个连通块，另一种是所有出度都变成了平方数。对于前者显然要把所有出度不是平方数的连向若干个新建的点使其变为平方数。对于后者显然要用走向下一个平方数的次数最小的点，即出度最小的点连。使用小根堆，每次取出出度最小的点并让它走向下一个平方数。

P10164（*2500，思维，dp）：考虑对于一个 01 串 s 需要使用多少次交换变成 01 串 t。对于 s 和 t 不相同的位置，01 和 10 出现的个数一定是相等的（因为 0 和 1 的出现次数都是相等的）。那么答案就是 s 和 t 不相同的位置 /2。考虑 dp，设 dp[i][j][k] 表示前 i 个，第 i 个为 1，1 有 j 个，后缀 1 的个数有 k 个。转移可以枚举上一个极长 1 的连续段和上一个后缀 1 的个数。这两个都可以使用前缀和优化。需要交换枚举顺序并使用滚动数组。

2.19

marsoj round 3 T2（*2800，思维，哈希，矩阵快速幂）：首先可以发现，第 i 个字符串的答案为 i-1 的答案加 i-2 的答案再加跨过 i-1,i-2 的答案。设 a=s[1],b=s[2]，观察斐波那契串的形态。发现，在 i>=6 时，i-1 的最后一个字符串（这个字符串指基本的字符串，即 a,b）与 i-2 的第一个字符串拼接起来的结果与 i-2 的拼接起来的结果相同。因此当 i-5 的长度大于等于 t 的长度时，i 的跨过答案与 i-2 的跨过答案相同。所以当 i>O(log) 时 i 的答案可以使用矩阵快速幂求出。接下来考虑前面的答案怎么求。暴力求出 i<=O(log) 时每个串，对 t 求出所有循环移位的哈希，求出每个串跨过的一段并暴力与 t 的循环移位匹配即可。为了更优的复杂度可以对 t 的长度数据分治，当 t 的长度较小时预处理出 s 的哈希值使用 t 匹配。

marsoj round 3 T1（*2500，思维，主席树，二分）：这个要求很适合搜索，只需要保证每使用 soft-O(1) 的复杂度能搜到一个复杂度就是对的。考虑对子序列的形态搜索，对于一种形态，我们只关心它的所有出现位置的最后一个位置以及它有多少个。接下来可以将问题转化为从小到大遍历一个后缀所有出现的数。可以使用主席树上二分解决。

marsoj round 2 T1（*2600，扫描线，线段树）：问题可以转化为检查被询问的区间包含的区间的并是否为询问的区间。考虑离线对右端点进行扫描线。这样可以先解决右端点小于等于询问的右端点这个限制。考虑将区间问题转化为点的问题。对于每个点记录覆盖它的区间左端点最大的是什么，那么如果一个询问的区间的该值最小值等于询问的左端点，则满足条件，否则不满足。相当于区间取 max 区间求 in，可以使用线段树维护。

2.20

AT_arc172_a（*<2000，思维）：考虑按面积从大到小插入。每次找到最左、最上的位置放上即可。正确性证明：考虑对于每种面积 2^x 将 n·m 划分成了 (n/2^x)·(m/2^x) 个方格。那么从大到小插入时面积大的一定恰好覆盖了一些面积小的方格。所以对于方格的个数一定是最优的，即插入某种面积时方格的个数达到最大值。据此复杂度可以从暴力模拟变为 O(n)。

AT_arc172_b（*<2000，思维）：发现两个序列有多个位置不同，不如有一个位置不同，因为可以将别的位置推到左右。那么限制转化为对于所有 n-k+1 的区间内部数都不同。直接对每个数计算前面满足条件时它有几种可能即可。

AT_arc172_c（*2100，思维）：无脑的做法是使用对前缀、后缀分别哈希并看哈希值是否相同。下面是一个有思维含量的算法。先求 2 开始的前缀和。考虑在 i 处插入和在 j 处插入时是否相同如何判定。前后显然不会变，只需要考虑中间。发现从 j 处插入变成 i 处插入时会将中间一段加上 a[1]（A 是 1；B 是 -1）。发现如果一个位置是 -1 或 0 或 1，则后面必须加上 a[1]，否则后面可以随便加。因此可以将问题转化为一个 01 序列，如果 i+1~j 之间没有 1 则 i 与 j 等价，求有多少个等价类。可以发现答案就是 n 减去 0 的个数。

CF1793E（*2600，dp，二分）：将 a 排序，则满足条件的人一定是一个前缀 1~k，否则调整（交换）更优。而且与 k 一组的一定优先是 k 以前的，因为它们的限制一定满足。进一步可以发现，分组情况一定是若干连续段。也可以使用调整证明。而且还可以发现，除了 a[k]>k，有限制的不可能与没限制的分在一组，因为如果分在一组了可以将有限制的放在有限制的组内，并释放没有限制的。这样就可以 dp 了。设 dp[i] 表示 1~i 有限制的分组最大值。每次在 1~i-a[i] 之间找到一个最大的 dp 并加一即可。对于询问可以二分并检查最优组数是否大于等于 k。

CF1773H（*2600，思维，交互，二分）：考虑查询 (0,1),(0,0).(1,0)，如果这两次的字符串不同，则点不在 x,y 轴上，且第二个字符串代表“近”。否则可以查询 (0,1e6) 和 (0,1e6-1) 来得到“近”。之后考虑横纵坐标同时二分。设当前的点在 (x1,y1) 与 (x2,y2) 所围成的矩形内，查询 (x2,y1),(x1,y1),(x1,y2) 可以将矩形的面积除以 4。最终会缩到只有一个点，即为答案。

2.21

marsoj round 4 T3（*2700，dp，计数）：考虑计算所有没找到的位置的期望，然后使用 q·(1+m)/2 减。如果某次操作后没找到，只需要关心此时的最大值。考虑设 ans[i][j] 表示第 i 次操作后最大值为 j 的概率。枚举 j。接下来需要对 j 的前后分别 dp。前面要求若干次操作后没删到 j，后面要求若干次操作后删完。发现一个必要条件是每个后缀或前缀放的个数小于等于/大于等于和。再想想容易证明它也是充分条件。因此可以根据这个 dp。比如对于左边，设 dp[k][l] 表示 k~j 中放了 l 个的方案数。转移时枚举 k 放了几个。注意这里只考虑了没有顺序的方案数，加上顺序需要除以 k 放的个数的阶乘，最后再乘上总共的个数的阶乘。求出 dp 后枚举左边有几个，可以计算出右边有几个，直接相乘即可得到方案数。除以 m^i 即可得到概率。

marsoj round 4 T1（*2600，数论，根号分治，dp）：考虑如何将 a[1] 分解质因数。考虑一个性质是 a 中的数都是 a[1] 的因数。如果存在一个 a[i] 既不是 1 也不是 a[1]，则 a[i] 和 a[1]/a[i] 都是 a[1] 的因数，而这两者中有一个 <=sqrt(a[1])。可以对它分解质因数，就可以至少得到 a[1] 的一个质因数。将所有的数都除以它，再继续找。如果所有的 a[i] 都是 1 或 a[1]，则 a[1] 此时也可以当成一个质因数。分解后考虑使用一种计算“有一些二进制数，计算子序列满足二进制数依次包含的个数”的方法：将二进制数分成两部分，对每一部分分别暴力遍历子集。具体来说，记录 sum[i][j] 表示前面第一部分包含 i，第二部分恰好为 j 的 dp 值之和。那么对于当前得到 dp 值可以枚举包含第二部分的二进制数。更新 sum 可以枚举第一部分包含的二进制数。而这个问题是同理的，如果可以将质因数分成两个部分，满足质因数乘起来的因数个数较小（比如 <=1000），就可以。发现 10^18 一类的因数个数最多为 1e5 左右。考虑直接选择一个质因数的前缀，得到两个因数个数的 max 最小，那么这个满足条件。可以发现，因数个数每次最多乘以 log，所以 max 小于等于 sqrt(1e5)·sqrt(log)，这个值就比较小。而且完全跑不满，可以暴力枚举这两部分，得到更优的 max。分成两部分后就可以使用上面的方法做了。

CF1924E（*3100，思维）：首先问题可以看成每次随机向上或向左走若干步，求走到 i·j<k 的位置的期望。考虑算贡献，转化为计算每个 i·j>=k 的点被走到的概率。考虑如果 j=m 时答案是什么。发现对于在走到这个点或越过这个点之前的最后一个点，走到这个点的概率是 1/(n-1+i)。而每次走都会存在这么一个点，所以概率就是上面这个值。经过这个的启发我们同样可以使用类似的方法对任意的 i,j 求答案。考虑路径一定是走到 i 相同或 j 相同的点，然后再使用上面的概率走到 (i,j)。那么我们还是看没到 i 相同或 j 相同的点时的最后一个点，走到这里的概率是 2/(i+j)。走到后还需要 1/(i+j-1) 的概率，将这两者乘起来即为概率。接下来考虑计算答案。发现 i+j 相同的点概率相同，因此枚举 i+j，并计算满足条件的 i。这是一个一元二次方程，求解集即可。

2.22

AT_mujin_pc_2017_c（*2500，dp）：设 dp[i][j] 表示以 i 开头最小的右端点使得 i 到这个右端点合并成了一个字符 j。考虑转移。如果 s[i]=j，答案显然是 i。如果 s[i]<j，则 s[i] 不可能经过若干次合并后被删掉（因为过程中必然经过 j），所以答案就是先合并成 j-1 再合并成 j，dp[dp[i][j-1]+1][j-1]。如果 s[i]>j，s[i] 必然经过若干次合并后删掉，所以答案就是将 s[i] 删掉后的最小右端点的答案，即 dp[dp[dp[i][25]+1][25]+1][j]。求出这个之后就可以求出从 i 开始最小的右端点使得区间可以删完，这样建一棵树检查 l 的祖先中是否有 r+1 即可。

AT_abc312_h（*2600，字符串）：结论：存在 n,m 使得 s^n=t^m 等价于 s 和 t 的最小整除长度的周期相等。证明：设最小整除长度的周期的长度为 len。如果它相等，则 len 是 gcd(|s|,|t|) 的因数，当 s^n 的长度等于 t^m 的长度时显然满足 s^n=t^m。如果 s^n=t^m，根据弱周期引理，对于 s^n 一定存在长度为 gcd(|s|,|t|) 的周期。而更小的周期一定是它的因数（否则取 gcd 有更小的），因此这两个周期一定相等。这样我们可以把最小整除长度周期相同的放在一起，解决下面这个问题：有若干个数，保证总和 <=2e5，顺序遍历每个数，如果 x 出现过就变成 2x,3x,... 直到没出现过，求每个数最终的系数。可以发现每个数都一定小于等于总和，可以归纳证明。那么考虑对每个数记录一个指针表示这以前的系数都出现过了，之后的未知。这样复杂度会变为调和级数，即可通过。

CF1468M（*2300，根号分治）：这个问题等价于找到二分图的一个四元环。考虑根号分治。如果某个右部点的度数大于根号，可以枚举另一个右部点以及它的出边进行判断。否则枚举一个左部点 i，以及它的出边 j。这里只需要考虑 j 的度数小于等于根号。那么可以再枚举 j 的出边 k。如果有多个 j 找到了同一个 k，则找到了四元环。

AT_arc058_d（*3000，dp，二分，哈希）：一个简单的想法是设 dp[i][j] 表示前 i 个字符串凑成长度为 j 的串的字典序最小串。但是状态里要装字符串，直接爆炸。发现一个性质，如果存在 dp[i][j] 和 dp[i][k]（j<k）满足接下来都有方案凑成，且 dp[i][j] 不是 dp[i][k] 的前缀，则两者字典序较大的一定不是最优解。因此这样去掉这些后只剩下若干个是一个串的前缀的状态（从小到大维护一个栈，如果不是前缀则淘汰一个，直到是前缀）。称这个串为母串。根据上面这个栈的思路维护一下若干个前缀即可。发现一个状态的转移相当于上一个母串的前缀加上这个串的前缀，所以只需要实现求这两个拼接的 lcp。可以使用哈希完成。

2.23

marsoj round 5 T3（*2400，思维）：观察路线的最终形态应为：从中间出发，走到最左边的点，再走到最右边，在此期间依次满足从右到左的依赖关系（向左再向右），再走到中间。因为一个边不会走超过三次，所以这显然是对的。考虑将区间按左端点排序，并求区间并。对每个区间计算加入当前区间后区间并多了多少。发现出发的点和结束的点都是区间并中的某个区间的右端点/左端点，而且如果不是答案一定更劣。因此枚举出发的点和结束的点（出发的点为区间的前缀的右端点最大值，结束的点为区间的后缀的第一个的左端点），那么中间重叠的部分即为中间区间的并，可以使用前缀和求出。发现左右端点的答案是独立的，因此维护一个后缀 min 即可。

2.26

CF1427F（*3200，思维，贪心）：设先手取的颜色为 0，后手取的颜色为 1。首先考虑构造一种不满足交替取的方案。使用栈从前向后贪心，如果存在三个颜色相同的就弹栈。考虑这个构造方案有什么性质。首先如果构造不出来一定无解。考虑将三个颜色的最左和最右作为左右端点，得到若干个区间，那么这些区间不存在相交且不包含关系。可以从颜色相同和不同两个方面证明。考虑建立区间树，还可以发现，父子的颜色一定不同，也是容易证明的。接下来将问题转化为了，有一个森林，每个点有 0 或 1 的颜色，满足 0 的个数与 1 的个数相等，先后手依次取颜色与人对应的叶子，构造一种方案使得能取完。结论：如果存在一个根的颜色为 1，则有解。这个结论会在接下来的构造中证明。为什么这么构造出来的一个树一定是最优的呢？这里需要用到上面的结论，可以发现所有树可以从这个树经过颜色相同的 ()() 变成 (())（把区间表示成括号）这样的变换得来，这些变换不会影响根的颜色为 1 的存在性，所以所有树要么都能构造，要么都不能构造。考虑对于这棵树构造一种方案，同时证明结论。对于先手，选择任意一个颜色为 0 的叶子即可。因为此时 0 的个数与 1 的个数相等，且存在一个根的颜色为 1，所以不可能不存在颜色为 0 的叶子（考虑将颜色为 0 的点与任意一个儿子匹配，那么如果不存在叶子，则 1 的个数一定大于 0）。对于后手，需要保证任意时刻都存在一个根的颜色为 1。考虑尽可能选一个不是根的颜色为 1 的叶子，实在不行再取一个是根的颜色为 1 的叶子。如果存在前者，则不会改变根的颜色为 1 的存在性，一定可以；否则当前取的一定为一个单独的颜色为 1 的点。如果当前点数不为 1，则剩下一定存在一个根的颜色为 0，且剩下的 0 的个数与 1 相等，则这里面一定存在一个颜色为 1 的叶子，与假设矛盾。否则点数为 1 就随便取了。

marsoj round 5 T1（*2300，思维，分段打表）：发现走不到等价于存在一条斜线上放满了车。我之前不会证，放在这里问了，现在会证了。证明：只需要证明对于相邻两条斜线一定存在一个缺口可以从一条斜线到另一条斜线。考虑对于一条斜线的某个没有车的位置，那么与它相邻的两个格子就必须有车。因为行、列都不存在两个车，所以又可以推出当前斜线的两个位置没有车。就这样一直向左、向右推过去，最终另外一条斜线一定填满了车。发现斜线有可能有两条，所以还需要容斥一下。对于左上半边的斜线，直接计算答案。对于右下半边的斜线，它需要满足左上没有斜线。这个答案相当于是更小规模的原问题的答案，所以可以递推。进一步可以发现，对于 dp[i] 答案是某个常数减去 dp[0~i-1]，那么对于 dp[i+1]，dp[0~i] 这一部分也是某个常数。所以现在就不需要递推了，可以直接将答案表示成一个式子。推一推式子可以发现要求的是阶乘之和，可以分段打表解决。

CF1930F（*?，思维，记忆化搜索）：钦定序列中的某个 a 作为最大值，b 作为最小值，考虑转化 max (a|x)-(b|x)。按位贪心，发现如果 a 的某位为 1，b 的某位为 0 则答案可以加上那一位的贡献。所以 max (a|x)-(b|x)=a&(~b)。考虑将问题转化为：维护一个集合，支持动态加数或给一个数求这个数与集合中的数的与的最大值。考虑动态维护集合每个数的子集，即使用一个数组记录。覆盖的过程中可以考虑记忆化搜索，如果当前数已经被标记过了，就不管，否则标记它并遍历所有将它的某位 1 改成 0 的数。接下来考虑查询。维护一个数 tmp，最初为 0。从大到小遍历所有查询的数是 1 的位 i，如果 tmp^(1<<i) 被标记过，则当前位可为 1，将 tmp 异或上 (1<<i)。这样就解决了这个问题。显然原问题可以转化为这个问题。

CF161D（*1800，dp）：设 dp[u][i] 表示 u 子树内与 u 距离为 i 的点的个数。dp[u][i]=sum dp[v][i-1]。求答案即钦定 u 为 lca，枚举路径的一边的长度，将两边的 dp 值乘起来。需要对都来自同一个儿子的容斥。

CF165E（*2200，高位前缀和，记忆化搜索）：a&b=0 等价于 b 是 ~a 的一个子集，因此可以对 b 的所有包含它的集合用 b 更新，然后直接查询 ~a 即可。这个过程可以使用高维前缀和。不过也可以使用 CF1930F 的套路记忆化搜索。

2.27

P10200（*2600，思维，Trie 树）：详见我的题解：https://www.luogu.com.cn/blog/wangxiwen/solution-p10200。upd：正解是发现条件等价于排序后相邻两个满足异或大于等于 k。这样将序列排序后 dp 就是多项式复杂度了。容易将状态数优化到一维，再想想可以发现相当于在 trie 上加入一个点以及 dp 值，或清空 trie，查询是查询某个值与加入的值异或大于等于 k 的 dp 值之和。可以直接做。

P10199（*2100，bfs，前缀和优化建图）：考虑对边看成一个点并连边。如果一条 (a,b) 的边与一条 (b,c) 的边满足前者的 [l,r] 被后者的 [o,c] 包含，则它们之间连一条边。连边之后求出从 s 的出边开始能走到哪些边，并使用这些边的 r 更新每个点的 t 即可。考虑如何优化连边。因为 l,o 比较小，所以考虑对 r,c 排序并使用双指针。剩下的问题容易使用前缀和优化建图解决。

P3804（*2800，SAM）：模板题，详见 lovely_ckj 的博客：https://lovely-ckj.github.io/post/samhou-zhui-zi-dong-ji-xue-xi-bi-ji。

SP1811（*2800，SAM）：考虑新建一个形如 s1+'#'+s2 的串，并对这个串建 SAM。对于每个前缀所在的状态，考虑标记为第一个串或第二个串的前缀。因为子串是前缀的后缀，所以只需要在 sam 上将每个点的标记或上子树内的标记，并找到长度最大的拥有两个标记的节点即可。

2.28

CF1930E（*2500，思维，计数）：考虑判定一些位置被删除了是否满足条件。设删除的位置为 1，否则为 0，显然我们只关心 1 的若干个极长连续段，设其为 b1,b2,...,bm。结论：满足条件当且仅当存在一个分界点满足前一半和后一半都 >=k。证明：如果不存在，考虑最后一次操作的中间，它需要不在任意一个连续段内。但是因为这个中间存在前一半或者后一半 <k，所以它不可能被操作。如果存在，可以发现一次操作一定可以将长度减去 max(1,b[i]-1)（这么减去之后一定有解），而操作后的长度可以至少 /2。在满足前一半和后一半都 >=k 的条件下一直这么操作直到总和等于 2k（因为至少 /2 所以一定能这么操作），那么最后一次操作一定满足。这样我们找到了判定条件。考虑枚举 k 并枚举 1 的个数（此时是调和级数），考虑正难则反，统计存在一半 <k 的个数。考虑最初有若干个 1，现在需要插入 0，那么满足这个条件需要让 0 插在前 k 或后 k 个空内。因此这是一个插板的问题，可以组合数求出。

P10202（*2500，计数，区间 dp）：问题等价于问区间组成的序列不同的个数。考虑删除区间的形态，它会形成一个区间树。那么只需要对区间树的个数进行统计，再乘上树的拓扑序个数即可。所以区间 dp 过程中需要记录当前区间内有多少个区间。设 dp[l][r][i] 表示区间 [l,r] 是一次使用的区间，使用了 i 个区间删完的方案数。再设 ddp[l][r][i][j] 表示区间 [l,r] 使用了 i 个区间删到剩下的数全是 j 的方案数。当 a[l]=a[r] 时，显然有 dp[l][r][i]=ddp[l+1][r-1][i-1][a[l]]，否则 dp[l][r][i]=0。对于 ddp，考虑枚举内部的若干个区间。对于左端点，如果等于 j 可以选择保留，无论是否等于 j 都可以选择一个右端点进行区间的删除。因此 ddp 也是好转移的。这样的时间复杂度为 O(n^6)，已经可以过了，但是还可以优化。发现如果将 ddp 过程中的连续的区间都合并，那么 ddp 就无须记录 j，因为 j 必然等于 a[l]。所以可以将 dp 的状态变为删完这个区间的方案数即可将 ddp 的状态少一维。

CF1864F（*2300，思维，扫描线，线段树）：先将 [l,r] 内的数提出来，不在区间内的不用管。考虑一个暴力：每次选择最小值并将全局减去最小值，然后对每个极长不为 0 的连续段分别做。正确性证明。思路大概是建出区间树然后调整到这个暴力的形态。接下来可以发现答案是区间存在的数的个数加上 i 与 pre[i] 之间存在 [l,a[i]-1] 的数的对数。我的方法是从大到小扫描线，每次加入一对 [pre[i],i] 将它放到线段树上，每次加入一个数 i 查询线段树上它能贡献到哪些区间，并将这些区间设为已经贡献过。

CF1916E（*2300，dfs 序，线段树）：考虑直接 dfs，枚举每个点作为 lca。维护一个线段树，每个节点表示它与当前 lca 之间的颜色个数。一个套路是处理出它的祖先第一个与它颜色相同的 lst[i]，那么 lst[i] 如果高于 lca 它就会被记入答案。考虑在搜索的时候对于 u 如果开始往下搜了，就把所有 lst[i]=u 的 i 的子树全加 1，且把自己子树减一（因为它不在路径内了）。考虑如何计算答案。可以枚举儿子，然后在儿子子树求一个最大值，并取最大值和次大值乘起来即可。

CF1930C（*?，思维）：结论：将重复的元素中的一个减去 1 直到没有重复的数，排序即为答案。证明：考虑最终减 1 形成的若干个段，问题可以转化为给一个非正数序列满足存在一种划分成若干个子序列的方式使得每个子序列形如 0,-1,-2,...，每次可以选择一个 0 的位置删除并后面的都 +1，求一种构造方案使得删掉所有的数。显然每次只能删掉最后一个 0，接下来只需要证明接下来一定存在 0 即可。因为删 0 后一定还是存在一种划分成子序列的方式使得每个子序列单调不增且相差 <=1。那么除了子序列没了的情况，一定存在 0。

P5341（*2700，SAM）：建出 SAM 后对每个出现次数为 k 的等价类差分一下即可。

SP1812（*2700，SAM）：与 SP1811 一样，使用分隔符分开字符串后对前缀打 tag。注意分隔符要不同。

SP8093（*2800，SAM，线段树合并）：对模式串建出 SAM 后对每个前缀节点打上某个字符串的标记，并对子树取或即可得到一个节点上有多少个标记。可以使用线段树合并维护。

3.15

CF388D（*2700，高斯消元，线性基，数位 dp）：详见我的题解：https://www.luogu.com.cn/article/sbrbgyzg。

3.18

P10220（*2600，dp，贪心）：考虑答案的第一位怎么求。可以通过二分转化为有一些位置不能走。接下来设 dp[u] 表示在 u 子树内走到可以走的位置的代价。那么 dp[u]=dp[u·2]+min(w[u],dp[u·2+1])。接下来考虑如何确定多位的答案。直接在树上搜索，并决策当前往哪里走。考虑求出这个子树内下一个要走到的点（即上面的问题），设这个点权值为 x。如果这个点在右子树，那么一定需要左边设置方案大于等于 x，设其代价为 k。因为先走右子树，那么右子树可以使用的魔力值就是 m-k。注意，需要在递归的同时记录花费的代价，因为魔力值不一定全花费完。递归右边后，左边的魔力值也就可知了。因为左边的魔力值一定 >=m-k，所以左边的字典序一定比右边大，不存在先向左走的情况。如果这个点在左子树，那么右边需要的代价为 k=min(a[u],右边设置方案大于等于 x 的代价)。这样左边可以使用的魔力值就是 m-k。递归左边后，右边的魔力值也就已知了。如果右边设置方案大于等于 x 的代价小于等于右边的魔力值，那么一定不操作 u，因为使用这些魔力值操作出来的右边的第一个一定大于等于 x。否则，一定操作 u，要不然右边的第一个就小于 x 了。于是继续递归右边即可。具体实现的时候可以预处理 dp[u][i] 表示在 u 的子树内走到所有 >=i 的位置的最小代价，而不需要在递归中二分。因为所有子树大小的和是 O(nlogn) 的，所以可以预处理出来。

3.21

P10253（*2500，思维）：发现若 x=abcd 这样拼凑起来，f(x)=a·1111+b·111+c·11+d·1。这样也可以发现对于一个 y，x 是唯一的（证明可以证 b·111+c·11+d·1<1111，可以再转化为 c·11+d·1<1111-111·9=112，接下来可以归纳证明）。发现 111 这样的数本质上是 (10^x-1)/9，所以推一下式子可以发现 x=(9y+x 的数位和)/10。可以枚举 x 的数位和，那么 x 只会若干次加一。可以暴力维护 x 并维护它的数位和，看是否等于枚举的数位和。因为如果有一次进位大于 6 位了以后就再也不会进位了，所以复杂度是对的。

3.29

P10254（*2800，思维，dp）：因为权值中既有 i 又有 a[i]，所以很难 dp，算贡献复杂度又很劣。所以考虑转化一下式子。结论：式子等于 sum i^2 - sum [i<j,a[i]>a[j]] a[i]-a[j]。证明：考虑冒泡排序的过程，每次交换一个相邻的逆序对，会使权值加上 a[i]-a[i+1]。因为每个逆序对都会交换一次，所以权值就是排序后的权值减去所有的逆序对的值之差。这样就容易 dp 了。现在只需要计算 sum [i<j,a[i]>a[j]] a[i]，因为 a[j] 同理。考虑从小到大插入数，枚举当前这个数插入在哪里，那么逆序对可以体现出来，且权值可以计算。于是这样就做完了。

4.3

P10218（*2800，Trie 树）：详见我的题解：https://www.luogu.com.cn/article/5g5ny3yx。

4.9

P10255（*2700，根号分治）：详见我的题解：https://www.luogu.com.cn/article/p67q98zu。

4.10

CF1948G（*3100，最大匹配，最小生成树）：最大匹配等于最小点覆盖，因此问题转化为选择一个点覆盖以及一个生成树满足生成树中每条边至少有一个点在点覆盖中，使得生成树的边权之和最小。枚举点覆盖，将满足条件的边拿出来直接做最小生成树即可。

4.13

CF986F（*3300，思维，同余最短路）：问题可以转化为 n 是否可以被所有 k 的质因数凑出来。如果 k 有一个质因数，判断 n 是否是其倍数即可；如果 k 有两个质因数，问题转化为判断是否存在非负整数对 (x,y) 满足 n=xa+yb。发现 yb 和 n 模 a 的值相同，因此 y 的最小值为 n 乘上 b 的逆元。接下来判断求出的 yb 是否 <=n 即可；如果 k 有三个质因数，根据小凯的疑惑 n<=p1·p2<=k^(2/3) 否则一定有解，而 p3>=k^(1/3)，所以可以使用 O(k^(1/3)) 的时间暴力枚举 p3 的倍数并使用两个质因数的方法判断；如果 k 有四个及以上的质因数，n<=p1·p2<=k^(1/2)，所以可以预处理出所有 n 的答案。还有一种做法是如果 k 有三个及以上的质因数，发现 p1<=10^5 所以可以使用同余最短路。

4.17

CF1943E1（*2900，二分，思维）：二分答案，将问题转化为：有一个可重集合，Alice 每次可以选择一个数删去，Bob 可以选择若干个数减去某些值，使得这些值的总和 <=k，若 Bob 某次操作后使得某个数变为非正数则 Bob 赢，否则 Alice 赢。可以发现 Alice 每次一定选择最小的数删，否则相当于凭空将某个数减去了一些，一定不优。将所有数排序。可以发现 Bob 的操作可以加一个限制：操作后序列仍然有序，而这两种操作是等价的。因为如果某次将某个值减一后小于前面的值了，这相当于将前面的值减一。所以序列排序后 Alice 每次删除的数一定是按顺序的。考虑枚举如果 Bob 赢变为非正数的那个数原来是哪个数，设它的下标为 x。可以发现 Bob 的最优策略一定是：从 x 开始找到第一个可以减的（与前面的数不同的）并将它减 1，设它的下标为 a。证明可以考虑如果当前操作不是 a 而是 b，为了满足条件 a 以后也一定会被减，那么将那次操作提前到现在一定不劣，而有可能更优是因为因为 b 以后可能直接被删除而不需要减了。因此模拟 Alice 和 Bob 的操作即可。

5.16

CF1945H（*2600，思维）：首先 A 集合一定只选两个数。枚举 gcd，接下来要计算去掉两个 gcd 的倍数的数后的与最小值。考虑与会改变的时候，只会在某一位上只有一个 0 或者两个 0 时。那么这些时候可以枚举。求出这些对的答案之后，将答案贡献到它们的 gcd 的因数上（可以发现复杂度为 log 乘上调和级数）。再枚举 gcd，接下来要检查是否可以不改变 and。直接暴力枚举两个 gcd 的倍数，如果他们在之前没有涉及到，则它们不会改变 and。因为涉及到的个数只有 O(nlog^2n) 个，所以复杂度是对的。如果必须改变 and，那么遍历涉及到的对数，再算出答案的最小值即可。

CF1949D（*2600，思维，构造）：详见我的题解：https://www.luogu.com.cn/article/79y4k6np。

7.18

中考完了终于回来了。打算先做一些简单题。

CF1989D（*1900，贪心，递推）：打造出的武器一定会被立即熔化。显然对于一种类型的金属锭会寻找 >=ai 且 ai-bi 最小的武器打造，因为这样的代价最小。发现 ai 的值域为 1e6，所以可以先将每个金属锭在 ai-bi 最小的武器上使用，直到个数 <=1e6。之后可以使用递推预处理出每种大小的金属锭的贡献。可以预处理出 ai 比某值小时 ai-bi 最小为多少。那么递推时可以找到最小的 ai-bi，并直接转移。

CF1994D（*？，思维）：可以先思考没有任何边时为什么存在 u,v 使得 (n-1)|(a[u]-a[v])。思考后发现 a[i]%(n-1) 有 n 个而值域只有 n-1，所以必然有重复的。可以将这个思路扩展到所有情况。倒着连边，对于第 i 次操作图上一定有 i+1 个连通块，在每个连通块中任选一个点，那么这 i+1 个点中必然有可以连边的。连上即可。

CF1994E（*？，思维）：首先可以发现若干个数或起来的值一定小于等于加起来的值，因为或相当于没有进位的加法。接下来发现一种删点的方案是每次删掉叶子，最终可以将大小变为任意值。因为现在可以将大小变为小于等于原大小的任意值，所以其他删除方案就没有意义了（既然小于等于大小），只需要考虑这种删除方案即可。考虑按位贪心。如果一位中有两个大小在这一位都是 1，则剩下的位都可以变为 1 了（其中一个提供 1???，另一个提供 0111）。否则这一位必然由那个唯一有 1 的树提供。而那棵树的这位以下的位置还不确定，直接将这一位删掉继续做就行了。

CF1994F（*？，欧拉回路）：问题本质上就是在一个给定的图上加入一些预备的边使得图存在欧拉回路，而且原图连通所以存在欧拉回路等价于度数全为偶数。发现对于两个奇点可以找一条路径并加入这条路径上的边，使得它们变成偶点且中间的不变。又发现可以重复添加边，因为添加两次相当于没添加。因此问题转化为给奇点配对，使得它们在预备的边上的图都连通。如果有一个连通块中有奇数个奇点，则一定无解，因为度数之和为奇数。否则一定有解，随意配对并随意找路径即可。具体可以任取一棵生成树并在树上差分。得到新图后求欧拉回路即可。

CF1935E（*2400，位运算，思维）：考虑按位贪心。对于最高位 i，考虑将区间分为三类：l>=2^i; l<2^i,r>=2^i; r<2^i。思考由谁来提供当前这一位。如果有第二类，如果有第一类或者另外一个第二类，则前者可以提供形如 1111 这样的数，而后者可以提供当前这一位，这样一定是最优的。否则第二类就要提供这一位了。如果没有第二类，则一定由第一类提供这一位。如果没有直接结束（第二类提供 1111），那么可以发现第二类的 l 变为 0，r 减去 2^i；第一类的 l 和 r 都减去 2^i，然后将 i-1 视为最高位处理。可以发现这个过程是确定的，所以对于每个区间都可以得到每一位上是第几类。对于询问，也可以直到它包含的区间中每一类的区间的个数，模拟上述过程即可。讨论是否有第二类本质上是在思考谁提供当前这一位。问题出在第二类提供了这一位有可能不优了。而解决问题的点在于如果有别的可能提供这一位，则答案一定确定了。