2025 SSOI暑假集训补题题解

· · 个人记录

补题链接

Day 1 贪心构造交互思维

梦的开始。 ::::success[CodeChef-MINORPATH] 看到这种位运算的题目就立马想到按位考虑，从高到低，显然高位为 0 比低位更优。对于每一位，贪心地考虑其能否为 0，O(n) 跑一遍数列即可 check（每次能到达更大的就取 \max，不能走了就返回）。时间复杂度 O(n\log V)。 :::: ::::success[CF1763C] 首先容易发现，在序列最大值的一侧如果出现两个及以上的元素，可以直接让其全部变成序列最大值（即连续对该区间操作两次，使其全部变成 0，再包含最大值操作一次）所以事实上只需要考虑有一侧只有一个元素（也是 n=2）的情况和 n=3 的情况。

先看如何判无解。显而易见地，如果 \exists x>\frac{\sum a_i}{2} 或 \sum a_i \equiv 1\pmod 2 则无解。

然后是 1 次的情况，当且仅当有一个划分点能恰好将这个序列划分成相等的两部分。

其余的就是 2 的情况。先找一个划分点使得两边的差值尽量小，做法是将差值 d 拆成两个 \frac{d}{2}，在大的一侧分别减去，使得答案成立，正确性显然。然后转化为 1 的情况。 :::: ::::success[QOJ-12150] 题意其实就是构造一种方案（取区间内/区间外）使得整个序列都要被覆盖至少 \lfloor\frac{n-1}{2}\rfloor 次。

先考虑完全包含的，我们显然可以让被包含区间取外，包含区间取内，达成条件。完全不相交的也可以一个取内，一个取外。所以只要考虑两两相交的线段。

相交线段也比较好处理，令第奇数条取内，偶数条取外即可。可以用双端队列维护相交的区间，对于所有区间按左端点排序，则左端点必然递增。右端点只需要放进双端队列，从队头到队尾从右端点小到大递增。对于每一个新加进来的线段，先与队头比，若 l_i>r_{head} 则说明不相交，若不行再与队尾比，若 r_i<r_{head} 则说明包含。都不行再扔入队列。 :::: ::::success[Gym-105484B] 我们将奇数位的 0 和 1 反转，则问题变成：

给你一个 0/1/2 构成的串，若有连续的 01 串直接删去，问 2 可以变成任意 0 或 1，求操作后最短的序列长度。

因此在这个串中，剩下的部分一定是 0 和 1 中较多的那个。反转之后统计 0/1 的数量，并用多的减去少的。对于 2，尽量补少即可。 :::: ::::success[CF1153E] 注意到如果有一个蛇的端点在一个询问块内，则此块通出的边条数一定为奇数。所以可以枚举行列，由于两个点不可能在一格内，必定至少有两个行/列的回答为奇数。

这样要询问 2000 次，对于最后一部分，可以使用二分查找在列中的哪一行，或者反过来。次数应该是刚好的。 :::: ::::success[Luogu-P4604] 答案显然具有单调性，可以用二分答案。

二分答案 x，对于每一个数可以计算其达到 \ge x 需要加多少次。

那么将所有区间按 l 排序，依次加入优先队列中。因为每次取区间的时候，显然取 r 大的更优，所以优先队列是正确的，在每次取区间开始之前，先将 r 已经小于当前 pos 的区间弹出去。

对于区间加，单点查询，用树状数组维护，记得每次清空！ :::: ::::success[HDU-6299] 首先在每个括号序列内的成对括号可以先直接删掉。

删完的括号序列必定是一段右括号接着一段左括号的序列，那么这时需要让在前面的右括号尽可能的少。所以只需要分类讨论。

当 a 的右括号多于左括号且 b 的右括号少于左括号，则 a 在前必定更优，反之亦然。

而当 a 和 b 的左括号都比右括号少，让左括号多的放在前面。

当 a 和 b 的左括号都比右括号多，将右括号更少的放在前面。

然后对于排完序的序列再扫一遍统计答案。 :::: ::::warning[Luogu-P2541] 显然每个状态都是由比它小的状态转移而来，而直接暴力转移是很慢的，考虑如何优化。

以下内容我并不会证，也并不知道怎么想出来

首先按将读入进来的数列排序，再将每个序列按照次小值减去最小值排序。设 (x,y) 为当前考虑到第 x 行，选到第 y 个，有三种转移可以不重不漏地覆盖：

手玩所有情况发现这确实是对的，但是我不会证。 :::: ::::success[Luogu-P1852] 设三颗棋子的坐标分别为 x,y,z，且 x<y<z。则跳法一共只有两类：

对于第二种跳法，显然可以跳无限多次，但对于第一种跳法，结果具有唯一性。那么实际上整个跳的过程就是一个树形结构。而且由于只能是一颗棋子绕着另一颗跳到更近的地方，而中间的棋子显然是不动的。所以只有两种情况，是一棵二叉树。

那么设 x 到 y 的距离为 d_1，y 到 z 距离为 d_2，则有几种情况：

但是注意到题目数据很大，想到可以直接处理出每一种情况跳的步数。由于每一次平移的距离一样，所以可以平移 \frac{d_2-1}{d_1} 次后，d_1 与 d_2 的关系才会发生变化。

那么对于题目中所给出的两个状态，判断可不可达的方法即为全部跳到唯一状态的根节点，判断是否相等。而跳的次数则是它们在树上的 LCA，可以使用倍增。类似地，先将跳跃步数大的跳到同样步数，之后如果跳 2^k 步后达到了同一个状态则枚举更小的步数，更新答案即可。 ::::

Day 2 数据结构 I

万恶的数据结构 ::::success[CF1474C] 首先可以发现，x 一定是单调递减的，所以删除的数只能从大到小选择。而只要确定了第一个取值，后面的所有取值都能确定从而一个一个推出来。

那么只需要枚举第一个元素后逐个判断即可，时间复杂度 O(n^2) :::: ::::success[CF1237D] 个人的神奇做法。 首先数组需要开到 3N。

然后从后往前倒着做。对于一个位 i，首先如果 i+1 走到某处会停，它肯定也会停。另外如果发现[1,\frac{a_i-1}{2}] 区间有比它更小的，就可以更新答案。所以可以开一个动态开点权值线段树，保存每一个值出现的最前位置。支持单点修改，区间查询。时间复杂度 O(n\log n) :::: ::::success[CF1924B] 考虑第一种操作：

设 x 港口左边的港口为 l，右边的港口为 r，则添加港口 x 时，对于 [l+1,x-1]，他们的代价为 a_l \times (x-i)，是一个以 a_l \times (x-l-1) 为首项，公差为 -a_l 的等差数列。对于 [x+1,r-1]，代价是 a_x \times (r-i)，是一个首项为 a_x \times (r-x-1)，公差为 -a_x 的等差数列。那么只需要用线段树维护，支持区间赋值等差数列，区间求和即可。 :::: ::::success[HDU-6315] 看到区间加，区间求和，肯定想到线段树。

本题如果直接对 a 数组进行维护显然不太可行。注意到 b 是一个排列，所以对于询问，答案最多可能是 \lfloor \frac{n}{1} \rfloor+\lfloor \frac{n}{2} \rfloor+\cdots+\lfloor \frac{n}{n} \rfloor=n \log n（调和级数）。也就是说可以直接维护每一个数还要加多少次才能产生贡献，当区间内出现贡献 +1 的情况时直接暴力递归更新即可，时间复杂度 O(n \log^2 n)。 :::: ::::success[Luogu-P4587] 考虑当前已经有一个可以连续表示的区间 [1,x]，现在添加一个新的数 a。

如果 a>x+1，则这个区间不再连续，x+1 无法被表示。

反之，值域可以变为 [1,x+a]，继续扫描。

那么将这个思想运用到这道题里，可以用这个方法求每个询问的答案。

设 ans 初始为 1，每次查询 [l,r] 区间里 \le ans 的数的总和。

如果总和超过 ans，则一定有未被选上的数，其值 \le ans。这时直接令 ans=res+1。

否则 ans 就是其答案，结束循环。

维护区间内 \le ans 的值，可以使用主席树。时间复杂度 O(m \log n \log (\sum a_i)) :::: ::::success[Luogu-P5268] 单个询问要同时维护 l,r,x 不好维护，注意到式子有可减性，考虑前缀和，原式变形为：

\sum_{x=0}^\infty(\text{get}(1,r_1,x)-\text{get}(1,l_1,x)) \times (\text{get}(1,r_2,x)-\text{get}(1,l_2,x))

设 g(p,x)=\text{get}(1,p,x) 则

\sum_{x=0}^\infty(g(r_1,x)-g(l_1,x)) \times (g(r_2,x)-g(l_2,x))

这个可以用莫队进行求解，统计答案即可。注意莫队的加入删除和普通莫队不同，不要写错。时间复杂度 O(n \sqrt n)。 ::::

Day 3 数据结构 II

::::success[CF1208D] 首先最后一个数可以确定，设其为 x，则必定有 \frac{x(x-1)}{2}=a_n。

那么就可以考虑倒着做，发现答案具有单调性（如果一个数 b>x，那么它的 a_i 一定不小于当 b=x 时的 a_i；反之亦然）。所以考虑使用二分，使用树状数组动态维护前缀和 res，每次使用 \frac{x(x-1)}{2}-res 来判定大小即可。 :::: ::::success[CF1690G] 一节车厢是否会成为一节火车的车头取决于上一节车头的速度，也就是前面的车厢的状态不会被改变。当车厢 k 操作时，首先向后遍历车头 x，如果 a_x \ge a_k−d，那么 x 将不再是车头。然后比较新车厢和前一个车头 y，若 a_y>a_k−d，那么 k 将成为新车头。

容易发现上述过程可以使用 set 解决。初始时最多有 O(n) 个车头，每次操作最多增加一个车头，因此复杂度均摊是 O(n\log n)。 :::: ::::success[CF1913D] 设 f_{i,1/0} 表示前 i 个数，最后一个元素是否被删除的方案数。 x 表示 i 前第一个小于 a_i 的数，则有转移方程：

\left\{ \begin{aligned} f_{i,1} &= f_{x,1}+f_{x,0}\\ f_{i,0} &= f_{x,1}+\sum_{j=x}^{i-1} f_{j,0} \end{aligned} \right.

第一个式子表示当 i 被删除，则前面一定要有一个比他小的元素，x 被更小的删或不被删除皆可。

第二个式子表示当 i 没被删除，则 i 是当前删除区间的最小值，[x,i-1] 作为上一个区间的端点都可以，并且如果 x 被删除，那么在最后一个没有被删除的位置同样合法，加上 f_p。

统计答案时，显然最后一个可以被删或者不被删，答案是 f_{n,0}+f_{n,1}。 :::: ::::success[CF2000H] 题意可以转化为查找最小的值，使得它之后有一段长度至少为 k 的 0 串。那么很容易想到权值线段树，上面空的点是 0，在集合里的点进行对应赋值。为了方便实现可以赋成对应下标。值域较小所以不用离散化和动态开点。最后发现答案具有单调性，使用二分即可得到答案。时间复杂度 O(n \log^2 n)。 :::: ::::success[Luogu-P7706] 一看就很像大线段树题，考虑怎么用线段树进行维护。

其实就是要求 [l,r] 中 a_i+a_k-\min(b_j) 的最大值，一个简单的想法肯定是让 a_i 和 a_k 尽可能大，b_j 尽可能小。所以要分别维护最大值和最小值。

但是题目有要求 i<j<k，考虑线段树的节点合并。一种情况是左（右）节点提供全部答案，还可以左边提供 a_i，右边提供 -b_j+a_k(j<k)，或左边提供 a_i-b_j(i<j)，右边提供 a_k，也就是还要多维护 -b_j+a_i(j<i) 和 a_i-b_j(i<j) 的最大值。维护合并与答案同理。 :::: ::::success[CF1638E] 首先对于颜色 +x 操作，直接对于每个颜色维护一个 tag，查询时加上即可。

对于染色操作，可以直接对于每一个颜色相同的子区间，线段树递归进行暴力修改。

复杂度证明：每次染色操作，至多会增加 1 个颜色相同的子区间。我们假设第 i 次操作的区间中有 x_i 个颜色相同的子区间需要暴力修改，则必然在之前需要 x_i 次染色操作，从而有 \sum x_i\le q，因此需要操作的颜色相同的子区间数量为 q 个。那么在线段树上，每一个子区间又会被拆分成 \log 个线段树上的区间，所以整体复杂度是 O(q \log n) 的。

注意在修改颜色区间时，每个区间需要进行存值的变化以应对查询。设一个点原值为 x，原颜色为 u，现颜色为 v，则修改颜色时，本身值应变为 x+col_u-col_v（先将原来没加的加上再扣去现在要统一加的） :::: ::::success[Luogu-P6617] 考虑记最小的满足 j>i 且 a_i+a_j=w 的 j 为 nxt_i ，则询问的条件等价于：

\min_{i=l}^r nxt_i \le r

并且，由于必有 nxt_i>i，所以对于 i>r 恒有 nxt_i>r 成立，故条件等价于：

\min_{i=l}^n nxt_i \le r

可以发现这等价于取后缀最小值，所以对于 nxt_i 相同的所有 i，我们只需要统计最大的 i 的 nxt_i 即可。这样我们修改一个点就只影响了常数个位置的nxt_i。用线段树维护后缀最小值，set 维护前驱后继的查询，时间复杂度 O(n\log n)。 :::: ::::success[HDU-7436] 在某一时段加边再删除的题目，跟线段树分治的特征很像。

将每一条边以存在时间为下标加入到线段树中，对线段树进行 dfs，使用可撤销并查集维护 1 和 i 的连通性。现在的问题是如何给在 1 的连通块内的所有结点加上当前的 t。

我们考虑使用类似 tag 的做法。在合并时，将父亲节点的 tag 加上当前的 t，并在分裂时下放。这样当 dfs 全部完成时，所有边全部被撤销，tag 也就被下放到了每一个节点中。统计答案即可。注意并查集要使用按秩合并并且并不能路径压缩，时间复杂度 O(n \log n) :::: ::::success[CF702F] 首先肯定需要将物品排序。

按人选物品肯定会超时，所以换一种想法：按物品选人。

这样问题转化成：有 n 个数，每次将 \ge c_i 的部分减去 c_i，并且将这部分的答案 +1。

可以将这些数分成 3 类：

对于这一部分的数，我们可以将其一个一个暴力修改，并且加入 [0,c) 的数集中。因为 c_i 已经排序，所以每个数最多被暴力修改一次。这样分裂合并的操作考虑使用平衡树（非旋 Treap 最佳）维护，时间复杂度 O(n \log n) :::: ::::success[QOJ-6656] 观察到答案具有可差分性，可以变为 \sum_{i=1}^r a_i-\sum_{i=1}^{l-1} a_i

再发现每一次询问的本质就是将 x 插入并且将当前区间里最小的 a_i 扔出去。所以 q 次询问就是将 q 个 x 和 a_i 放在一起，扔出去前 q 小值。再运用前缀和将 r 和 l-1 的答案都求出来相减。对于 a_i 使用主席树，对于 x 使用权值线段树，放在一起跑查询即可。 ::::

Day 5 数据结构 III

::::success[CF459D] 观察到 i 和 j 之间无关联，分开计算即可。可以将每一个 f 都计算出来，然后直接二维偏序逆序对即可。 :::: ::::success[CF1849E] 考虑扫描线枚举右端点 r，容易发现 r 需要修改贡献的是一段区间。

考虑 r\to r+1 的造成的影响：

设 maxn_i 为 i 前第一个比 i 大的数，minn_i 为 i 前第一个比 i 小的数。

则如果 maxn_i<i-1，说明 l\in[maxn_i+1,i-1]，区间最大值都在 i，此时这部分一定可以做出贡献。

如果 minn_i<i-1，说明 l\in[maxn_i+1,i-1]，区间最小值都在 i，此时这部分一定不能做出贡献。

在没有被更改的位置，r 既不是最大值也不是最小值。对答案没有影响，维持原样取贡献。

所以只要用线段树维护，支持区间赋值 0/1，区间求和。 :::: ::::success[HDU-7284] 由于 x_j<x_{j+1}，若某次 1 操作时 a_i<x_j，则在之后的操作里 a_i 永远小于 x_j。所以类型的更改每个数最多进行一次，可以直接线段树进行暴力修改。

对于 a_i>x_j，直接进行朴素的区间减即可。

对于 a_i<x_j，观察一下发现，减第一次的时候 $ a_i-x_j =-(a_i-x_j)，第二次又变成 -(a_i-xj)-x{j+1} =a_i-xj+x{j+1}。所以每次加上当前 x_j$，并且将原值取反。与区间加减相似，维护一个取反 tag 即可。

::::success[Luogu-P3863] 首先想到扫描线扫描时间 t，维护序列情况。但是想想发现并不好进行维护，所以换一个角度，扫描线扫描序列 a，维护每个时间当前数的情况。

这样，对于每个操作 1，在 l 的位置给 [t,m] 加上 x，在 r+1 的位置给 [t,m] 减去 x。对于操作 2，是一个经典的分块问题。直接全部使用分块维护。 :::: ::::success[UOJ-637] 若 x 对一个区间对答案有 -1 的贡献，当且仅当区间内无 x - 1 且区间外无 x。

先预处理出每个数第一次、最后一次出现的位置 lst_x 和 fst_x。

设 f(l, r) 表示区间 [l, r] 的答案，扫描线从左往右扫 r，用树状数组维护对于每个 l，f(l, r) 的信息 ，考虑当 r \gets r + 1 时会如何变化。

如果 r = lst_{a_r}，那么 r 后面不再有和他相同的数，且区间内需要没有 a_r - 1，再记录每个数到现在最后一个出现的数 now_x。加入 a_r 在 [now_{a_r - 1} + 1, fst_{a_r}] 有 -1 的贡献。

如果 r \ge lst_{a_r + 1}，那么在原先计算 a_r + 1 的时候改变的答案会恢复。加入 a_r 在 [now_{a_r} + 1, fst_{a_r + 1}] 有 1 的贡献。 :::: ::::success[CF526F] 这题有个很好的性质，所有的棋都不同行列。

所以 k\times k 的棋盘里，有 k 个棋子的充要条件是 \max_{l\le i \le l+k-1}{y_i}-\min_{l\le i \le l+k-1}{y_i}=k 且 \max_{l\le i \le l+k-1}{x_k}-\min_{l\le i \le l+k-1}{x_k}=k。

考虑到两维比较难维护，先将 x 排序，这样第二个条件显然已经满足。现在只需要满足 \max_{l\le i \le l+k-1}{y_i}-\min_{l\le i \le l+k-1}{y_i}=k 即 \max_{l\le i \le l+k-1}{y_i}-\min_{l\le i \le l+k-1}{y_i}-k=0 再发现这个式子的值一定 \ge 0，所以只需要维护其最小值即可。

考虑扫描线扫 r，维护所有 l，使得 \max_{l\le i \le r}{y_i}-\min_{l\le i \le r}{y_i}-r+l-1=0 的出现次数。

然后可以把式子拆成 4 个小部分，对于 l，为一开始就固定的值，直接放进去。r，从 r\to r+1，式子上会 -1。对于 \max 和 \min，可以使用单调栈维护，进行区间修改，线段树维护。

最后累加每个 [1,x] 的最小值数量即可。 ::::

Day 6 字符串

::::success[CF176B] 首先观察到一个性质：如果一个字符串能变换，那么最多只会经过一次变换，且拆分的方案数是相同的。

于是设 dp_{i,0/1} 表示经过 i 次变换，是/不是目标状态的方案数。

于是有：

dp_{i,0}=cnt \times dp_{i-1,1} + (cnt-1) \times dp_{i-1,0} dp_{i,1}=(l-cnt) \times dp_{i-1,0}+(l-cnt-1) \times dp_{i-1,1}

其中 cnt 表示从任意字串变成目标串的拆分方案数，l 为串长。 :::: ::::success[Luogu-P4824] 题目反复找到字串并删除的操作，长得非常像栈的结构。

所以可以想到用一个栈，将串中字符一个个加入栈并进行匹配。如果匹配到完整串就全部弹出。这样每个字符最多进出栈一次，复杂度正确。匹配可以使用哈希或 KMP。 :::: ::::success[CF1721E] KMP自动机板题。

设 dp_{i,j} 表示在 s 上往前跳时，最大的 k 使得 s_{k+1}=j。

则在转移 \pi 的时候，有 \pi_i=dp_{\pi_{i-1},s_i}。

考虑如何维护 dp_{i,j}：

如果 s_{i+1}=j，那么 dp_{i,j} 显然等于 i。

否则，模拟 KMP 失配指针往前跳的过程，不断寻找 \pi_i 直到 s_{\pi_i+1}=j 作为答案。 :::: ::::success[CF898F] 因为是让我们放一个加号和等号，很明显，左边两个数的长度的最大值最小也只能是右边那个数的长度 −1。这样我们的枚举量就会大大减小。

所以只需要考虑字符串的处理。容易想到哈希，但因为没有哈希加法这种东西，所以我们可以把 base 调成 10。那么这样会很容易发生冲突（而且还是 CF 的题）。所以我们用双哈希，实测 19260817 和 10^9+7 可过。 :::: ::::warning[Luogu-P8131] 本题不会证明，请尽快学会！

先跑一个 Manacher，然后左边往里折，再右边往里折，最后答案是 \frac{r-l}{2}。 :::: ::::error[Luogu-P4696]

:::: ::::error[CF1310C]

:::: :::error[CF873F]

:::: ::::error[CF1202E]

::::

Day 7 dp I

::::success[CF1849D] 说是 dp 题，但其实能用贪心做。

注意到一段连续的 1/2 可以全部染色，并且如果区间内有 2，还可以染到区间左边或右边的一个 0。那么只需要从左到右扫一遍，对于有 2 的区间，如果其左边一个没有被染，就染左边。否则就染右边。可以证明这样是最优染法之一。 :::: ::::success[CF1458B] 首先观察到性质：如果有一杯水从 x 倒给 y，y 倒给 z，那么不如直接将 x 倒给 z，y 倒给 z。

所以题目变成：选 k 个杯子，将其他杯子里的水都倒入这 k 个里面，求最大水量。

设选出集合为 S，答案即为 \max(\sum_{i \in S} a_i,\sum_{i \in S} c_i+\sum_{i \notin S} \frac{c_i}{2})

那么其实就是选杯子的问题，可以用 0/1 背包解决。设 dp_{i,j,k} 表示前 i 个杯子，选 j 个，a_i 之和为 k 的 b_i 和最大值。

然后根据上面的公式统计答案即可。 :::: ::::success[CF1077F2] 定义 dp_{i,j} 表示前 i 个，选了 j 个且最后一个必须选的美观度最大总和。

则 dp_{i,j}=\max_{t=\max(i-k,0)}^{i-1} dp_{t,j-1}+a_i

观察到这个式子是求一段连续区间的最大值，很容易想到线段树或单调队列优化。优化后时间复杂度 O(n^2 \log n) 或 O(n^2)。 :::: ::::success[CF1874C] 这种从起点走到终点的概率题，一般都会选择倒推。因为终点只有一个。

那么对于考虑到的每一个节点，显然会贪心地优先选择往后走到的概率最大的节点

则设 dp_i 为从 i 走到 n 的概率，有

dp_u=\sum_{(u \to v) \in E}dp_v\times f_{u \to v}

考虑如何计算 f。

可以设 f_{i,j} 表示出度为 i 的节点，在第 j 个成功走出去的概率。显然 f_{i,1}=\frac{1}{i}，剩下需要分两种情况：

所以得出：

f_{i,j}=f_{i-2,j-1}\times \frac{i-j}{i}+f_{i-2,j-2}\times\frac{j-2}{i}

由于 u<v，所以可以不用拓扑排序，倒着循环即可。 :::: ::::error[QOJ-11110]

::::

Day 9 dp II

::::success[CF1324E] 由于是睡完整一天，所以可以看成没睡。

然后题目就变成：每次取数有一个范围 [l_i,r_i] 可以将贡献 +1，每次与上次间隔 a_i 或 a_i-1 取数（对 24 取模），求最大贡献。

设 dp_{i,j} 表示前 i 次取数，最后一次取数在 j 时刻，最大贡献。

则 dp_{i,j}=\max(dp_{i-1,j-a_i},dp_{i-1,j-a_i+1})+(l_i\le j\le r_i)

注意 j 只需要枚举到 24，注意负数取模。 :::: ::::success[CF2000F] 容易看出，染色的时候对于每一个矩形，哪一边短就先染哪一边直到染成正方形。对于正方形，只需要横竖交错地染就可以保证操作次数最少。

所以预处理出 s_{i,k} 表示每一个矩形得到 k 分的最少操作次数，然后设 dp_{i,j} 表示前 i 个矩形，得到 j 分的最少操作次数。可以很简单地写出转移：

dp_{i,j}=\max_{k=0}^{j}dp_{i-1,k}+s_{i,j-k}

答案即为 dp_{n,k}。 :::: ::::success[CF1557D] 设 dp_i 表示符合题意能保留的最多行数。设 S_i 为该行为 1 的位置的集合，则

dp_x=\max_{k=1}^{x-1}[S_k\cap S_x\not=\varnothing]dp_k

本质上其实就是查询每一段覆盖区间内最大的 dp 值。

所以可以想到线段树优化，将 dp_i 作为值塞入权值线段树内，每次分段查询并统计答案。最后求方案数可以在转移的时候和线段树内维护最大值的来源，直接指针往回跳。

时间复杂度 O(m \log n) :::: ::::success[CF980F] 观察到每段线路都是 2^i 的形式，与倍增相似。

考虑如何倍增，设 dp_{u,v,s,0/1} 表示从 u 到 v 有一条长度为 2^s 的路径，其起点为 0/1。

类似 Floyd 枚举中间点 k，那么 dp_{u,v,s,0/1}=dp_{u,k,s-1,0/1}\vee dp_{k,v,s-1,1/0}。

那么就可以贪心从高位到低位统计答案。由于每次拼接需要反转，所以需要一个 now 来存储当前位是 0/1 起点。 :::: ::::success[QOJ-9879] 观察到，由于每次都是走和撤回两种操作，所以最优路线一定是一棵树形结构。而又由于只有两个方向，所以二叉树是最优解之一。而又因为需要按顺序访问，所以每个子树一定是一个连续的区间。

这启示我们进行区间 dp。设 f_{l,r} 表示从 (0,0) 开始，走 [l,r] 的点的代价。这可以进行递归处理。每次合并的时候，将这两部分的贡献加起来并减去共同走的路径长度即可。由于只有向右和向上，共同走的路径最长只会是 \min_{i=l}^r x_i+\min_{i=l}^r y_i。 :::: ::::success[CF771D] 实际上，除了 \text{V} 和 \text{K}，其他所有字母都是等价的，直接视为 \text{Z} 即可。

因为 n 很小，所以考虑暴力 dp。设 dp_{i,j,k} 表示前 i+j+k 个字母中，已经填了 i 个 \text{Z}，j 个 \text{V}，k 个 \text{K}。又因为 j 和 K 不能连在一起，所以还需要一维 0/1/2，表示上一个字符是什么。

那么写出转移方程：

\left\{ \begin{aligned} dp_{i,j,k,t}+c(i+1,j,k)&=dp_{i+1,j,k,0}\\ dp_{i,j,k,t}+c(i,j+1,k)&=dp_{i,j+1,k,1}\\ dp_{i,j,k,t}+c(i,j,k+1)&=dp_{i,j,k+1,2}(t\not=1)\\ \end{aligned} \right.

所以现在只需要考虑如何求 c。

我们发现，原状态前 i 个 \text{Z}，j 个 \text{V}，k 个 \text{K} 排在该排的位置了。所以对于这一个，前面所有多余的字母都要挪到后面去。这可以直接暴力跑，复杂度 O(n^4)。 :::: ::::success[CF331C3] 首先观察到一个重要结论：每次减只会减当前 n 的最大数位。

所以我们考虑如何快速模拟这个过程：

设 f_{d,n}=(x,y) 表示当前能使用的最大数位为 d，把 n 变成非正整数所需要的最少操作次数为 x，n 最终变成 y。

那么对于每一个数位，只需要先用当前最大值给后面的数位删一次，再使用后面剩下的数位进行递归即可。因为使用状态的下标很大但是分散，用 map 记录状态。 :::: ::::success[CF1601D] 贪心神题。

以 \max(a_i,s_i) 为第一关键字， s_i 为第二关键字从小到大排序。

然后依次枚举，能选就选，就是最优答案。

证明：

:::: ::::success[CF311B] 首先可以将每只猫要被接到，饲养员出发的最晚时间 a_i 处理出来。这样就变成了区间分成 p 段的取数问题。很容易设计状态：dp_{i,j} 表示前 i 名饲养员，走了 j 只猫的最小等待时间。

则 dp_{i,j}=\min_{k=0}^{j-1} f_{i-1,k}+(j-k)\times a_j-s_j+s_k，其中 s_i=\sum_{i=1}^i a_i。

这个方程是 O(n^3) 的，考虑如何优化。为方便表述，接下来省略第一维。

现在 j 是枚举的，先将它看作已知量。将这个式子进行展开之后会得到 s_k+dp_k=k\times a_j+(dp_j+s_j-j\times a_j)。

发现这个式子符合 y=kx+b 的形式，故可以进行斜率优化。复杂度可以压到 O(n^2) ::::

Day 10 dp III

::::success[CF1096D] 首先其他的字母对答案没有任何影响，不用考虑。

然后设 dp_{1/2/3/4} 为删除 h,ha,har,hard 的最小代价。则有 dp_{s_i}=\min(dp_{s_i}+a_i,dp_{s_i-1})。

答案为 dp_4。 :::: ::::success[Luogu-P10156] 有一个结论：选配对时，对于 l'<l<r'<r，选 (l',r') 与 (l,r) 比 (l',r) 与 (l,r') 更优，很容易证明。选第二种方案显然会让 x|i-j| 的和增大。

所以对于每一个组可以设 dp_{i,j,0/1} 表示前 i 个人，j 个留下学信息，当前是否有待匹配的人。

然后对于全局，再跑一遍多重背包，f_{i,j} 表示前 i 个组，选了 j 个人。注意边界处理，我因为这个挂了好几次。 :::: ::::success[CF1336C] 可以往前/后进行扩展，十分像区间 dp。

设 f_{l,r} 表示匹配 T 的第 l 个到第 r 个字符的方案数。转移很好写。

值得注意，如果当前匹配的位置 >m，这时候可以直接转移，因为题目要求前缀。 :::: ::::success[Gym-104128B] 考虑没有修改的情况，是好写的。设 dp_i 表示建设 [1,i]，符合要求的最小总成本。则

dp_i=\min_{j=i-k}^{i-1} dp_j+a_i

使用单调队列优化即可做到 O(n)。

那么对于每次修改，由于是相对独立的。所以可以分别计算。但是这样需要重算 [p_i,n] 的 dp 值，复杂度过高。这里有一个办法：设 g_i 表示建设 [i+1,n] 所需要的最小总成本。这样统计一个点被修改的答案的时候只需要算 f_i+g_i 即可。而每次修改最多只会影响后面 k 位，这些位暴力 重算 dp，记录在 f_i，每次询问的答案即为 \min_{j=p_i}^{p_i+k} f_j+g_j。 :::: ::::success[CF1242C] 发现因为数字之和相同，和即为所有盒子的平均数是确定的。 所以每次扔出去一个数，总会有固定的数加入进来。这样考虑建边。显然合法情况需要成环且同一个环内的两个元素不在同一个盒子内。注意到 k \le 15，那么可以将每一个环经过的盒子状压出来，dp 即可。

状压的思路：可以枚举子集。发现如果子集和子集的补集都合法，那么这个集合一定合法。时间复杂度 O(3^k)。 :::: ::::success[CF559E] 玄学的 dp 设计方式。

设 dp_{i,j,0/1} 表示前 i 盏灯，最右边的是第 j 盏，方向朝左/右。

发现直接从 i\to i+1 是有后效性的，于是我们枚举 k 进行转移。

设 k 之前的灯，最右边的是 x，方向是 y，长度是 l，右端点是 mx，第 j 盏灯右端点是 r，方向是 t。当前灯的右端点位 R，则

dp_{k,x,y}\to dp_{k,x,y}+dp_{i,j,t}+\min(l,R-r)+mx-R

::::

Day 11 组合数学 I

::::success[CF1436C] 二分算法能找到 x 说明在二分比较过的每一个点，其大小关系都是相对于 x 确定的。

所以模拟二分算法，算出有 cnt1 个数小于 x，cnt2 个数大于 x。其他数可以随便放。

所以 ans=C_{x-1}^{cnt1}\times C_{n-x}^{cnt2} \times (n-cnt1-cnt2-1)! :::: ::::success[Luogu-P9306] 说是排列组合但更像贪心。

我们会发现，无论如何我们都会将 p 和 q 的最大值尽量放前面。所以一定只有 2 和 3 两种答案。

如果 \max_p 和 \max_q 在同一个位置，那么答案为 2，后面随意，答案为 (n-1)!。

否则，考虑 \max_p 在第一个的情况，设与 \max_p 绑定的 q 为 q'，需要维持答案则在 [1,pos_{\max_q}] 之间至多放 q'-1 个数。枚举有多少个，答案为 \sum_{i=0}^{q'-1}A_{q'-1}^{i}(n-i-2)!，\max_q 在第一个同理。 :::: ::::success[CF1696E] 手玩发现答案是杨辉三角的一部分，答案为 \sum_{i=0}^{n-1}\sum_{j=i}^{a_i+i} C_j^i。

朱世杰恒等式告诉我们 \sum_{i=0}^{m} C_{i}^{a} = C_{m+1}^{a+1}，发现式子满足前缀和，为 \sum_{i=0}^{n-1} C_{a_i+i+1}^{i+1}-C_{i}^{i+1} :::: ::::success[CF571A] 由于直接求出合法情况是困难的，所以可以用总方案数减去不合法的方案数。

总方案数好求，为 \sum_{i=0}^l C_{i+2}^2。

可以枚举最长边，枚举分给最长边的长度 i，判断是否合法。在不合法情况下设最长边为 c，则 c+i-a-b>=0。然后满足这个条件之后，剩下长度就可以随意分给剩余两条边，为 C_{x+2}^2，注意 x=\min(c+i-a-b,l-i)。 :::: ::::success[CF1929F] 我们知道：二叉搜索树满足在一个节点左子树内的数都严格小于当前数，右子树反之。

所以可以把二叉搜索树拍扁成一个序列，序列上的数一定是单调不降的。那么对于每一段没有数的区间可以应用插板法。相当于在这一段数里面，将头尾两端的数之差 x 个隔板插入其中，可以插空。是一个经典问题。设区间长度为 len，则贡献为 C_{len+x}^{len} :::: ::::success[CF1227F2] 需要观察到性质：高于原得分的方案数与低于的是相同的。

所以其实只要求出来与原得分相同的方案数即可，答案为全部情况减去方案数除以二。

发现另一个性质：如果 h_i=h_{i+1}，那么这个位置对答案造成不了任何影响。设这样的位置有 m 个。

那么其实就只有至多 \lfloor \frac{n-m}{2} \rfloor 个位置对能对答案造成影响，并且一一抵消。

枚举有多少个位置造成了 +1 的贡献，那么就有相应的位置造成 -1 的贡献。这样的个数一共是 C_{n-m}^i \times C_{n-m-i}^i。最后其他位置除了 h_i 和 h_{i+1} 随便乱选，所以是 (k-2)^{n-m-2i}。

所以方案数为 k^m \times C_{n-m}^i \times C_{n-m-i}^i \times (k-2)^{n-m-2i}。 :::: ::::success[Luogu-P7118] 首先我们知道，一棵 n 个节点的二叉树，其方案数为卡特兰数 H_n。

考虑枚举在 x 的子树产生贡献，设字数外的方案数为 res，每个点原子树大小为 siz_x。则可以分两种情况：

:::: ::::error[QOJ-10335]

:::: ::::error[QOJ-9479]

::::

Day 13 组合数学 II

::::success[CF1795D] 一个显然的性质：每个三元组都会被选出两条边。所以每个三元组都会染成两红一蓝或者两蓝一红。

那么只需要考虑每个三元组有多少种染色方法即可。显然权值最小的边要被舍弃，所以如果三个数都为最小值，有 3 种染色方案。如果两个和一个同理。

那么算完之后，只需要组合数求出哪些要被染成两红一蓝即可，为 C_{n/3}^{n/6}。 :::: ::::success[CF1207D] 直接正着算很难做，考虑反着容斥。也就是总方案减去第一个排序再减去第二个排序最后再加上都排序的方案。

对于单个排序也就是分成几个数字相同的段，每个段内数字可以任意排列，即为 A_{num}^{num}。对于两个都排序，先检验是否可行，如果可行将这两个一起进行分段，任意排列即可。 :::: ::::success[CodeChef - SEQGOODNESS] 因为为只求总和，所以可以对于每个数计算贡献。显然先按 S 排序。

显然 S_i=i 要求比 S_i 小的数要选出 i-1 个放在前面，即 C_{S_i-1}^{i-1}。其他比 S_i 大的可以自由选，即 2^{n-i}。乘起来计算即可。 :::: ::::error[CF1666F]

:::: ::::success[YukiCoder-2206] 首先对于每一位，考虑计算贡献。因为有可能选 1 至 m 中的任意个 1，所以贡献如下：

(1+2+4+\cdots+2^{n-1})(C_{n-1}^{0}+C_{n-1}^{1}+\cdots+C_{n-1}^{m})

前面的式子可以化简：

(2^n-1)(C_{n-1}^{0}+C_{n-1}^{1}+\cdots+C_{n-1}^{m})

令 \sum_{i=0}^m C_n^i=f(n,m) 则

(2^n-1)\times f(n-1,m)

那么问题转化成如何计算后半部分。

首先显然，

f(n,k+1)=f(n,k)+C_n^{k+1} f(n,k-1)=f(n,k)-C_n^k

我们注意到，\sum_{i=0}^k C_{n-1}^i+\sum_{i=0}^{k-1}C_{n-1}^i=f(n,k)（杨辉三角画图可以理解）

那么：

f(n-1,k)+f(n-1,k-1)=f(n,k) 2f(n-1,k)-C_{n-1}^{k}=f(n,k) f(n+1,k)=2f(n,k)-C_n^k

从而可以得到 f(n,k) 往四个方向的转移，从而可以用莫队。

\begin{aligned} f(n-1,k)&=\frac{f(n,k)+C_{n-1}^k}{2}\\ f(n+1,k)&=2f(n,k)-C_n^k\\ f(n,k+1)&=f(n,k)+C_n^{k+1}\\ f(n,k-1)&=f(n,k)-C_n^k\\ \end{aligned} \right.

:::: ::::success[CF1924D] 首先发现如果 \min(n,m)<k，无解。

然后考虑一个填完的情况：假设有 k 对匹配的括号，那么这个序列一定长成 )...)(...( 的样子。所以可以想到组合数 C_{n+m}^k，但是由于这样选出来的括号并不能确定它是否能匹配上，所以这个应该表示的是 \le k 对括号匹配的情况。

那么其实可以利用容斥。\le k 对匹配减去 \le k-1 对匹配的情况，刚好就是恰好 k 对匹配的情况。答案即为 C_{n+m}^k-C_{n+m}^{k-1}。 ::::

Day 14 图论 I

::::success[CF1255C] 这题甚至不太需要图论。我们发现，头尾两个数只会出现一次，第 2 和 n-1 个只会出现两次。而相邻两个三元组中，必定有两个数是重复出现的。

那么直接钦定任意一个为头，然后以那个三元组开始往后找。可以使用 map 维护出现次数。 :::: ::::success[Luogu-P9650] 正着做不太好决策哪些边应该被删掉，所以尝试倒着来。

有一个显然的贪心：每次一定是删掉 d 条到终点的距离最短的道路。而这个问题刚好和最短路相似。

于是思路就比较清晰：将所有终点放进去跑最短路，每经过一个点，如该点的 d>0，就说明这个点还可以封锁，就将转移过来的道路封锁掉。这样答案顺便也可以求出来，即为 dis_1。 :::: ::::success[Luogu-P5839] 首先拿到手的矩阵不一定是最优的，先跑一个 Floyd。

有一个很显然的 dp：设 dp_i 表示前 i 个，其中每段都 \ge k 的最小代价。则 dp_i=\min_{j=1}^{i-k} dp_j+c(j,i,c)。其中 c(j,i,c) 表示把 [j,i] 全部变成字符 c 的最小代价，可以前缀和预处理。

接下来优化 dp_i 的转移。把式子变成前缀和的形式发现 dp_i=\min_{j=1}^{i-k} dp_j+s_i-s_j，其实只要求出 \min dp_j-s_j。发现每次都只要加入 i-k 这一个决策点，可以用前缀 \min 进行优化。 :::: ::::success[Gym-104857J] 由于是拥堵系数最大的两条边，而最短路只支持求出一条边，所以可以想到枚举一条最大边，然后看起点到当前边和当前边到终点的最大边权情况来统计答案。这样需要正反跑两遍最短路。 :::: ::::success[Luogu-P2934] 首先一个结论：从一个点到其余点的最短路会构成一棵树。而且一个点到其余点的每条次短路会且只会经过一条非树边。我们发现一个点被更新的答案为 \min dis_x+w(x,y)+dis_y，所以直接将非树边按上式排序，然后第一次更新出来的 ans 就是答案。

而对于一条非树边，画图可以证明其影响范围最大只能达到两个端点 x,y 的 lca。我们只需要搞一个并查集，把处理好的部分直接连到父亲上缩点即可。每条边只会被连一次，复杂度正确。 :::: ::::success[Luogu-P6651] 没有删除的情况是好做的，直接把所有的起点扔到队列里面跑拓扑排序即可。求出每个点到其余点的方案数，记为 f_{i,j}。

那么要求删除之后剩下的，也就是求出删了多少条链。这里可以使用容斥。但是暴力容斥枚举删了哪些点是 2^k 的，无法接受。

但是我们并不关心删了哪些点，只关心算重的问题。可以按拓扑序排序，设 g_i 表示从 1 走到 c_i，不经过其他关键点的路径条数。有 g_i=\sum_{j=0}^{i-1} g_j \times f_{c_j,c_i}，ans=\sum_{i=1}^{k} g_i \times f_{c_i,t}

这样为什么是对的？g_i 的含义是 c_i 是我们选的第一个关键点，而后面的路径我们是不管的，也就是说这包括了后面的路径选和不选的所有情况。那么对于每一个点作为第一个选都考虑到了，所以不重不漏。 :::: ::::success[CF875C] 先考虑一种特殊的无解情况：如果后一个字符串是前一个的前缀，则必定无解。

定义一条边 x\to y 表示如果 x 满足为小/大写，则 y 必须满足给定条件。

找出相邻两个字符串第一个不同的位置 i，对于这个位置进行判断：（设 x,y 为大写，x',y' 为小写）

建边，Tarjan 跑 2-SAT 即可。 :::: ::::success[Luogu-P6062] 有一个贪心：显然每条木板如果能放就放到最长，否则显然是不优的。

可以将每一个木板看成一个点，每一个泥地看成一条边。每个泥地都能被横竖两条木板覆盖，所以在这两条木板之间连边。

横竖的木板并不相关，所以这是一张二分图。那么现在只需要求出最少的木板能够使所有边被染色。这是二分图最小点覆盖，也就是最大匹配。跑匈牙利即可。 :::: ::::error[HDU-7488]

:::: ::::error[CF818G] 是我最喜欢的网络流（然而我却做不出来）。

::::

Day 15 图论 II

::::success[CF1679D] 发现答案具有单调性，故可以进行二分答案。

对于每一个二分的值，禁用点权比其更大的点，如果图里面仍存在环那么一定可行。否则拓扑排序，如果能找到长度 >k 的链那么也是可行的。 :::: ::::success[CF1213F] 按题意模拟，将每一个 p_i\le p_{i+1} 的条件都作为边加入图中。如果发现有环，那么这个环内部的所有字母一定是一样的。那么就可以 Tarjan 缩点之后直接 DAG 跑拓扑排序即可。 :::: ::::success[CF2000G] 答案具有单调性，可以二分。

对于二分出来的每一个答案，进行 dijkstra 检验。

当到达一个路口的时候，要分以下几种情况：

缩完点之后其实整个图就变成了一棵树。钦定一个根节点，我们可以处理出来从根节点到各点的点、边权和 w1_i。这样查询就可以 O(1) 统计。

对于每次查询，只需要判断 w1_x+w1_y-2\times w1_{\operatorname{lca}(x,y)}+w_{\operatorname{lca}(x,y)}>0 即可。 :::: ::::success[Luogu-P11907] 首先这个三维空间没有一点用，可以直接 bfs 求出每个点的恐怖值，然后拍扁成一维的。

注意到两个点时，对答案的贡献是两点权值的较小值，所以用两点权值的较小值作为这条边的边权。

那么接下来其实就是一个最小瓶颈路，可以使用 Kruskal 重构树直接维护。每次查询的时候，求出两点之间的 lca，其权值就是答案。 :::: ::::warning[CF325C] 虽然写完了，但是仍然不是很明白。

::::

Day 17 树上问题 I

::::success[CF1336C] 考虑一个城市从旅游城市变成工业城市的情况：其子树内所有城市到它都会有 -1 的贡献，但是从它到根节点的路径上都会有 +1 的贡献。所以贪心地按照 dep_i-sz_i 进行排序，取前 k 大即可。 :::: ::::success[Luogu-P5536] 有一个比较显然的性质：第一个点一定选在直径中点最优。

那么对于其他的点，以直径中点为根，可以记 maxd_i 表示其能够到达子树内最远的点距离。然后从根节点开始进行 bfs，贪心地先解决 maxd_i 更大的节点，显然正确。取前 k 个，最后只需要输出剩余点中的 \max maxd_i 即可。 :::: ::::success[CF771C] 注意到单个可以使用 dp 求解，那么求多个根的答案可以想到换根 dp。

首先列出以固定点为根的 dp 转移方程：

设 dp_i 表示以 i 为根的子树内产生的贡献，用 h_{i,j} 表示以 i 为根的子树内，到 i\mod k=j 的点数，辅助转移。则

dp_i=\sum_{j\in son_i} dp_j+h_{j,0} h_{i,j}=\sum_{x\in son_i}h_{x,(j-1+k)\mod k}

即每次转移时 dp 是子树内 dp 贡献之和加上走到子树余数为 0 的点数（即再走一步就要多一次），同时因为到 i 多走一部，h 需要从 j 变为 j+1。

然后思考第二次转移：

设 dp2_x 为以 x 为根整棵树的贡献，h1_i 表示以当前节点为根整棵树到 i\mod k=j 的点数，辅助转移。

考虑从 dp2_x 转移到 dp2_y：y 补树内到 x 距离为 0 贡献 +1（即再从 x 到 y 要多一步）， y 子树到 y 距离为 0 贡献 -1（原来走到 x 的时候需要多一步但现在不用了）

对于h1 转移：

如何求补树部分？

h1_{补树部分}=h1_总-h1_{子树部分}

如何求子树部分?（此处 h1 表示 h1_x）

h1_{子树部分}=sum_{y,(j-1+k)\mod k}

记补树部分为 h2，

合并：h2_{i,j}=h1_{i,j}-h_{y,(j-1+k)\mod k}

则 h1 转移：

整理得 h1_{y,j}=h_{y,j}+h1_{x,(j-1+k)\mod k}-h_{y,(j-2+k)\mod k}

即为：

dp2_y=dp2_x+(h1_{x,0}-h_{y,k-1})-(h_{y,0}) h1_{y,j}=h_{y,j}+h1_{x,(j-1+k)\mod k}-h_{y,(j-2+k)\mod k}

:::: ::::success[CF2033G] 这题比较容易看错题。

其实就是往上走需要 1 的代价，往下走不用。

所以其实路径一定是先往上走到一个节点，然后往该点的另一个子树走下去。否则不优。可以记 maxd_i 表示从 i 这个节点往下走到的深度最大值，f_i 表示从 i 点先往上走到父亲 u 再往下走到的深度最大值。

那么有了这些，我们可以对于每一个点 O(k) 地求出答案。但是这样仍然太慢。

树上问题的常见优化就是倍增了。我们重新定义 f_{i,j} 表示从 i 往上走了 [1,2^j] 步能达到的最大距离。这样 f_{i,j}=\max(f_{i,j-1},f_{fa_{i,j-1},j-1}+2^{j-1})，其中 fa_{i,j} 表示 i 的第 2^j 级祖先。 :::: ::::success[Luogu-P4949] 这是一棵基环树，而这题的操作又非常像树剖。所以想到断掉环上的任意一条边，用树剖解决。每次查询分经过该断掉的边和不经过两种情况取 \min。然后就是树剖板子了。 :::: ::::success[CF1709E] 发现对于一个点，最多被替换一次。因为只要替换一次，就可以将其改成任何数，必定有一种办法能让它们的异或值不为 0。

然后异或还有一个性质：如果一个数 x 被异或了两次，那么这个值是抵消的。

所以对于一个经过子树根节点 x 的 u\to x\to v 的路径，等价于 d_u \oplus d_v \oplus a_x。其中 d_x 表示从根节点到 x 的路径异或和。

这个式子要等于 0，也就是 d_v=d_u \oplus a_x。那么全部塞进 map 里维护查询即可。

但是注意到最坏情况下复杂度 O(n^2)，可以使用树上启发式合并，优化到 O(n\log n)。 :::: ::::success[CF1794E] 对于一个根，注意到可以 Hash 进行求解。记距离根节点距离为 d_i 的节点有 cnt_{d_i} 个，则其目标 Hash 值为 \sum cnt_i \times base^i。

先设 f_x 表示 x 的子树内的 Hash 值，则 f_x=1+\sum f_y \times base。

那么对于换根来说也是很容易的，设 g_x 为以 x 为根的子树外 Hash 值。

则 g_y=f_x-f_y \times base +g_x。对于一个 x，其 Hash 即为 f_x+g_x。

因为有一个数位可以自己决定，所以只要这个 Hash 与目标状态差值满足 d\equiv base^i\pmod m 即可。

因为是 CF 的题，所以需要双 Hash。 :::: ::::error[CF914E]

:::: ::::success[CF1016F] 我们发现，从 1 到 n 的路径在树上是唯一的。那么可以把这条路径提出来，这样就会发现每一个点下面都挂着一棵子树。

对于这棵子树分两类讨论：

::::

Day 18 树上问题 II

::::success[Luogu-P8578] 满足条件的最优方案很显然是让一个节点的子树内编号连续。这很符合 dfs 序的特性，所以直接跑一遍 dfs，给所有节点都赋上 dfn 即可。 :::: ::::success[CF1244D] 你会发现，这个条件满足的充要条件是每个节点的入度 \le 3。换句话说，这是一条链。

那么对于一条链，直接暴力枚举前三个点的染色方案，6 种情况。然后暴力遍历求最小成本即可。 :::: ::::success[CF1790F] 这题有一个做法是，我们会发现第 k 次加点答案不超过 \lfloor \frac{n}{k}\rfloor，这是一个调和级数。所以每次暴力 bfs 出去即可。时间复杂度 O(n\log n)。

但是我并没有使用这种做法 （因为没想到） ，而是使用了点分治。

我们先设 pos_{c_i} 表示 c_i 出现的时刻，那么对于一个点 c_i 来说，在它加入时离它最近的点即为 [1,pos_{c_i}-1] 的最小值，这个可以使用树状数组维护。那么可以想到用点分治来做这件事情，对于每个点，将其子树到它的深度加入树状数组，然后对每个关键点 x，离最近的关键点距离的最小就是 dep_p+\operatorname{query}(pos_x-1)。这样时间复杂度为 O(n\log n)。

然后还要注意一件事情，因为这个最小值可以来自它左边的子树和右边的子树，而点分治是顺序的做下去的。所以需要在完成之后将边的遍历顺序反过来再跑一遍。最后 ans 记得要取前缀 \min。 :::: ::::success[Gym-102012G] 有一个显然的想法，统计有几条边经过每一个点 x，记为 cnt_x，答案为 \sum C_{cnt_x}^k。

但是这样是错的。因为我们发现可能有多个点都被同一条路径经过，这样会算重。而我们又发现在一条路径中会经过 n 个点和 n-1 条边，会有一条边不经过。于是我们再统计每个点到其父亲的那条边有多少条路径经过即可，记为 f_i。答案即为 \sum C_{cnt_x}^k-C_{f_x}^k。 :::: ::::success[CF1842F] 记 cnt_i 表示 i 的子树之内的黑点数量。则答案为：

\sum_{i\not=rt}|k-2cnt_i|

我们令所有的黑点组成一棵新树 T，树的重心为 rt，则当在根节点取的时候，必有 k\ge 2cnt_i。

所以绝对值可以直接拆掉，为

\sum_{i\not=rt}k-2cnt_i

化简，

(n-1)k-2\sum_{i\not=rt}cnt_i

显然前面的部分是确定的，所以只需要让后面的部分最小。每个黑色节点都会让从它到根节点的路径上产生 1 的贡献，那我们就应该贪心地选择深度最小的 k 个节点。则原式表示为：

(n-1)k-2\sum_{i=1}^k dep_i

然后就可以枚举每一个点当黑色点的重心，将答案求出来取 \max。 :::: ::::success[CF1149C] 首先一棵树的括号序列可以被画成折线的形式：

比如上图就是一个 ((())())(((()))()) 的折线表现形式。

那么可以发现，折现的最高点就是一棵子树的最深深度。所以根据两点间路径长度 dis_x+dis_y-2dis_{\operatorname{lca}(x,y)} 也就可以在这里表示成 h_x+h_y-\min_{i=x}^y h_i。

这个东西不好维护，但我们发现这个要取到最大值，那么 \min_{i=x}^y h_i 显然一定要取到最小值，否则无法造成贡献。所以其实就可以转化成 \max h_x+h_y-h_i(x\le i\le y)。而这个跟上文数据结构部分的 Luogu-P7706 很像。可以直接线段树维护。具体维护方式大致是维护区间 mx=\max h_x,mn=\min h_x，再维护 gl=\max h_x-h_y(y>x),gr=\max h_x-h_y(y<x)，最后 ans=\max(mx_{ls}+gr_{rs},mx_{rs}+gl_{ls})。注意最后还要跟从根节点到最远点的距离（即 \max h_x）取 \max。

对于修改操作，每将一个 ) 和 ( 交换相当于将这个区间内的线段向上平移了 2 个单位。将 ( 和 ) 则反之。需要线段树区间加减，全局取最大值。 ::::

Day 19 数论

::::success[CF947A] 如果 x_2 是由 p\times a 得到的，那么 x_2 一定小于 x_1+p-1。所以为了让 x_1 可能取到的值尽可能多（可能性更多），我们最优能取到 x_2 的最大质因子 p_0，那么 x_2-p+1\le x_1\le x_2。

然后可以直接枚举 x_1 的所有取值，对于 x_0 用相同的方法判断最小值即可。需要预处理出不包含原数的最大质因子。 :::: ::::success[CF1499D] 题目让我们求 c\times \operatorname{lcm}(a,b)-d\times \gcd(a,b)=x 的 (a,b) 数对数量。

直接来推式子：

c\times \frac{ab}{\gcd(a,b)}-d\times \gcd(a,b)=x

设 p=\frac{a}{\gcd(a,b)},q=\frac{a}{\gcd(a,b)} 则

c\times \frac{p\times \gcd(a,b)\times q \times \gcd(a,b)}{\gcd(a,b)}-d\times \gcd(a,b)=x (cpq-d)\times\gcd(a,b)=x \gcd(a,b)=\frac{x}{cpq-d}

所以我们需要保证 cpq-d|x

那么可以枚举 x 的因数 y，式子变成 cpq-d=y

pq=\frac{y+d}{c}

那么需要满足 c|y+d

因为 c,d 是已知的，所以只需要在 y 满足条件的时候将上式的质因子种类处理出来，根据定义，p,q 互质，每种质因子要么全给 p，要么全给 q，答案为 2^{cnt_\frac{y+d}{c}}。可以使用欧拉筛进行预处理。

:::: ::::success[Luogu-P12021] 题目的条件可以列出很简单的 dp 转移方程：dp_i 为选到第 i 个的方案数，则 dp_i=dp_{i-1}+dp_{i-2}（斐波那契数列）。

那么现在只需要求出有几个能够包含第 i 的数列就好。那么其实你会发现这就是能被 k^{i-1} 整除的数的个数，直接快速幂计算即可。最后由于是并列关系，所以答案为乘法关系。 :::: ::::success[Luogu-P12952] 题目其实就是让我们求：

a_i+xD\equiv a_{w-i+1}-yD\pmod n

求 (x+y)_{\min}

xD+yD\equiv |a_{w-i+1}-a_i|\pmod n D(x+y)\equiv |a_{w-i+1}-a_i|\pmod n D(x+y)+nk=|a_{w-i+1}-a_i|

设 x'=x+y 则

Dx'+nk=|a_{w-i+1}-a_i|

使用 exgcd 求最小正整数解

有绝对值，所以正反都要考虑，为 \min(x'\mod n,n-(x'\mod n)) :::: ::::success[Luogu-P6583] 显然只有分母约分后只含 2 和 5 的分数才能被表示为有限小数。

那么可以想到枚举分母有几个 2 和 5，再枚举分子和分母的 \gcd，答案即为

\sum_{i=0}^{\lfloor \log_2 n\rfloor}\sum_{j=0}^{\lfloor \log_5 n\rfloor}\sum_{k=1,2\nmid k,5\nmid k}^{\lfloor n/2^i5^j\rfloor}\lfloor \frac{n}{k}\rfloor

这个式子后面可以进行整除优化，对于每个段容斥一下被 2 和被 5 整除的有几个即可。时间复杂度 O(\sqrt n\log^2n)。

但是你会发现这样过不去。

但是可以换一下枚举顺序：先去枚举满足条件的 k，再在 \lfloor \frac{n}{k} \rfloor 的范围内枚举满足条件的 2^i5^j。这样依然可以整除分块，而且分块被调用的次数大大降低了，可以通过这道题。 :::: ::::error[CodeChef-LECOINS]

:::: ::::success[Luogu-P2150] 很显然地，可以设 dp_{i,s1,s2} 表示前 i 个寿司，甲拿的寿司含有质因子集合 s1，乙含有 s2 的合法方案数。则

dp_{i,s1|k,s2}=\sum dp_{i-1,s1,s2}(k \& s1==0) dp_{i,s1,s2|k}=\sum dp_{i-1,s1,s2}(k \& s2==0)

然而这样的复杂度是 O(n2^{2n})，无法接受。

然而我们注意到，对于 \le 500 的数，至多只有一个 \ge 23 的质因子。所以可以把这一部分单独存下来。对于每一个大质因子相同的数，我们设 f1_{i,s1,s2} 表示该大质因子让第一个人选的方案数，f2_{i,s1,s2} 表示大质因子让第二个人选的方案数，最后汇总到 dp 数组里。注意每次传值的时候要把 dp 数组先传给 f1 和 f2 便于统计，最后统计通过容斥减去一遍 dp_{i,s1,s2} 即可。 :::: ::::error[ABC335G]

:::: ::::error[CF645F]

:::: ::::error[CF1515G]

::::