10月杂题

还是得写写杂题，初三赛季说明这对我是 buff 啊。

这次 CSP-S 再次检验王者是超级 debuff！！！

1. P7830 [CCO2021] Through Another Maze Darkly

感受一下，每次从根开始绕一圈回去，这个圈会越来越大，直到大小变成 \(n-1\) 。

考虑求出每个边在最后一个圈内入和出的时间（就是欧拉序），你会发现每次走的一圈是这个序列的子序列。那对于一次询问，先二分这是哪一圈走的；然后离线下来，则要支持插入和查 k 小。这是容易的。

2.P7949 [✗✓OI R1] 左方之地

考虑求出 \(popcount(x)=k\) 的数形成的线性基。不妨令 \(a_0=0\) ，则每个 \(a_i\) 都是要选出线性基的一个子集。这些子集要互不相同。这就转化成了 \(k=1\) 的问题。

3.ARC129E Yet Another Minimization

主要是怎么刻画这个权值，对于每对 \((i,j)\) ，考虑把 \(|a_{i,x}-a_{j,y}|\) 拆成数轴上的若干段，就是把 \(a_{i,k}\) 和 \(a_{j,k}\) 这些当成关键点之后，考虑两个相邻的关键点。

设第 \(i\) 个位置取的 \(a_{i,j}\) 是第 \(c_i\) 小的。则我们能把权值写成： 若 \(c_i<x,c_j>y\) ，则会出现 \(z\) 的代价。还有一些\(c_i=x\) 时，会出现 \(z\) 的代价。这个就是切糕了。

4.AGC044D Guess the Password

编辑距离这个东西很抽象，尝试用它做一些简单的事情。

首先用全 a 串就能得到 S 中 a 的个数，其他字符同理。

并且我们可以判断一个串是否是 \(S\) 的子序列。就是看编辑距离是不是 \(|S|-|T|\) 。

看到 850 这个限制，感受到它是 nlogn 状物，于是我们尝试分治。

就是说先想一下 ab 串怎么做，设 \(b\) 的个数为 \(n_b\) ，我们在 a 后面接 \(n_b\) 个 b ，如果这个是 S 子序列，说明 S 第一个位置是 a ，否则是 b 。

现在有多个串了，其实就可以分治做，令 \(sol(l,r)\) 为， \([l,r]\) 内的字符拼成的串，从下往上，用上面的 ab 串方法拼就好了。

5.CF1870G MEXanization

先想怎么算答案，考虑二分。我们最后要凑出 \(p\) ，那最后一步一定包含 \(0\) 到 \(p-1\) 。而如果中间某个数 \(a\) 不存在，则要求 \([0,a-1]\) 至少有 \(2\) 个。所以有这样一个算法，先把 \(\geq p\) 的都变成 \(0\) ，然后从 \(p-1\) 到 \(0\) 扫一遍，维护 \(x\) 表示后面的数都需要至少 \(x\) 个。考虑此时扫到的数出现次数为 \(c\) 。如果 \(c<x\) ，则 \(x\) 增大 \(x-c\) ；否则的话我们把多余的 \(c-x\) 个数都变成 \(0\) 。

发现如果 \(p\) 合法，那 \(x\) 只会增大 \(O(\sqrt{n})\) 次，因为 \(x>\sqrt{n}\) 后，如果位置也 \(>\sqrt{n}\) 就凑不够了。

并且随着数的加入，\(p\) 只会越来越大，我们就只需要 \(O(n)\) 次 check 。每次 check 用线段树二分加速这个过程，即找到第一个 \(c<x\) 的位置。同时要更新 \(0\) 的个数。这里线段树二分写成自下往上的话，能证明总复杂度为 \(O(n\sqrt{n})\) 。

6.CF1870H Standard Graph Problem

跑一遍最小树形图，我们其实建了一张新图，形如一棵树，就是每次缩环时我们建了一个新点来表示这个环，它的儿子就是环上的点。

发现最后的点集中如果含有 \(x\) ，那 \(x\) 到根的边都不用选。这就成了一个小清新　ds 了。

7.AT_joisc2016_h 回転寿司

先考虑 \(l=1,r=n\) ，用堆维护 \(a\) 中的数即可。所以我们考虑分块，对每个块维护一个堆。那一次操作中，处理整块很容易，但处理散块时，我们就需要得到：这个块之前做了若干整块操作后每个点的值是多少。发现这是和原问题对称的，就做完了。

8.AGC025E Walking on a Tree

考虑对每条路径连一条 \((u,v)\) 的边，如果每个点度数都是偶数，那直接跑一遍欧拉回路显然是对的。现在我们尝试调整，就是通过加树边，把度数调整成上面的形式。这样跑出来回路后，考虑对于一组树边 \((a,b)\) ，能影响它的新增边只有 \((a,b)\) 本身，所以去掉新增边后一定合法。

10.ARC142E Pairing Wizards

先把题中的限制化简一下。不妨令 \(b_x\le b_y\) ，则 \(a_x,a_y\geq b_x\) ，且 \(a_x\geq b_y\) 或 \(a_y\geq b_y\) 。处理第一个限制就是调整一下 \(A\) 。看到第二个限制，一开始想直接像切糕那样做，但最小割的局限性使得它只能做 \(a_x\geq c,a_y\le d\) 这样的限制。但这个题特殊点在于它有一个 \(a_y\geq b_y\) 。我们能把点分成两类：当前 \(A_i\geq b_i\) 的为第一类，否则为第二类。显然对每个限制，\(x\) 一定是第一类，\(y\) 可能是第二类。

对于第一类点 \(i\)，我们建点 \((i,j)\) ，如果它与 \(S\) 联通就代表最终 \(a_i-A_i\geq j\) 。为了表示出这个效果，需要连边 \(((i,j),T,1),((i,j+1),(i,j),\infty)\) 。

对于第二类点 \(y\)，我们这样处理限制：建立新点 \(P\) ，连边 \((S,P,b_y-A_y),(P,(x,b_y-A_x),\infty)\) ，代表要么我自己提升，解决限制，要么丢给所有相连的 \(x\) 解决限制。

跑最小割即可。

11.P4785 [BalticOI 2016 Day2] 交换

分类讨论根的情况，发现有一种情况不能直接处理，就是 \(1,2,3\) 中的最小值在 \(3\) 上。则操作后，我们无法确定另外两个数 \(x,y\) 该放 \(2,3\) 还是 \(3,2\) 。怎么办呢，令 \(x<y\) ，考虑 \(x\) 放在哪边，能使最后 \(x\) 处在的位置更小。发现这样就能比对了。就是要计算一个 \(f(x,a)\) 表示当前 \(x\) 权值为 \(a\) ，操作子树 \(x\) ，\(a\) 最后的位置，还是利用上面的讨论来算。发现可能的状态只有 \(O(n\log n)\) 个，因为这里一定存在祖孙关系。就做完了。

12.AGC022F Checkers

以前一直看不懂这个题的题解，想来想去想不清楚，今天重看，发现自己思路一气呵成啊。首先翻译一下题意，就是有一个 \(2n-1\) 个结点的二叉树，其中有 \(n\) 个叶子结点代表 \(X^1,X^2,\ldots,X^n\) 。我们设 \(x-lson\) 的边权值为 \(-1\) ，\(x-rson\) 的边权值为 \(2\) 。那两个树不同，当且仅当存在某个叶子结点，使得它到根的边权之积不同。

每个这样的积都能表示成 \(x2^c\) 的形式。其中 \(x\in \{-1,1\}\) 。考虑怎么计数，我们先指定每个叶子的权值，然后尝试 check 能否构造出一棵树。一次合并其实就是把 \(x2^c\) 和 \(-x2^{c+1}\) 合并成 \(-x2^c\) 。那 check 就是按 \(c\) 从大往小贪心地合并，因为最大的 \(c\) 无法再改变。

这样按 \(c\) 从大往小，就有一个 dp :记 \(f_{x,i,j}\) 表示我到当前层，其中 \(x=-1\) 的有 \(i\) 个点，\(x=1\) 有 \(j\) 个点。考虑转移，就是枚举下一层 \(-1\) 和 \(1\) 的个数 \(a,b\)。 假设 \(i<j\) ，那转移合法的充要条件是： \(a\geq j-i\) ，\(b\) 不做限制。先说必要，因为当前层的 \(j\) 个 \(1\) 只能使 \(a\) 至多增加 \(i\) (把下一层的 \(-1\) 变成 \(1\)) 。再说充要，就是我们每次取出当前层的一个 \(+1\) 和一个 \(-1\) ，再取出下一层的一个 \(-1\) ，先合并 \(+1\) 再合并 \(-1\) 即可。下一层这个点仍然是 \(-1\) ，但它消灭了当前层的两个点！再对剩下的做操作就行了。发现下一层最后的状态也是固定的。

再观察一下上面的形式，发现 dp 只需要记 \(j-i\) 就行了，于是复杂度优化到了 \(O(n^4)\) 。

最后答案为 \(dp_{n-1,0}+dp_{n-1,1}\) ，因为最上面一层只能有 \(1\) 个点，而且需要最后符号是正的。这样就做完了！

13.P6700 [PA 2015 Final] Edycja

14.P4786 [BalkanOI2018] Election

考虑 \(O(nq)\) 的贪心：令 S 为 1，T 为 -1，从左往右扫，如果前缀和为负就把 T 删了。再倒着扫，后缀和为负就把 T 删了。

设 \(a_i\) 为前缀和，\(b_i\) 为后缀和。则第一轮我们操作次数为 \(-\min a_i\) ，考虑第二轮中 \(b_i\) 的改变，有 \(b'_i=b_i+\min\limits_{j<i} a_j-\min a_i\) 。第二轮操作次数为 \(-\min b'_i\) 。加起来，发现它就是 \(-\min\limits_{j<i} a_j+b_i\) 。就是最大子段和，用线段树维护即可。

15.P9447 [ICPC2021 WF] Spider Walk

直接 dp ，每次要交换 \(dp_x,dp_y\) 并对值进行更新。更新形如 \(dp_i+dis(i,j)->dp_j\) 。

考虑此时很多转移都是没必要的，\(i\) 和 \(j\) 中一定有一个为 \(x\) 或 \(y\) 。对于 \(i\) 为 \(x\) 或 \(y\) ，用线段树维护即可；对于 \(j\) 为 \(x\) 或 \(y\) ，发现只需要用 \(x-1\) 和 \(x+1\) 更新 \(x\) 即可，因为其他位置的转移都可以拆成两段：\(u->x-1/x+1->x\) ，而第一段已经在之前转移过了。\(y\) 同理。

16.P9341 [JOISC 2023 Day4] Security Guard

首先有结论：树的答案为 \(\min a_i-\sum a_i+\sum\limits_{T\in(u,v)}a_u+a_v\) 。那 \(Q=0\) 就是最小生成树。在这个基础上调整，就是每次找到一条边 \((u,v)\) 断掉，假设 \(1\) 与 \(u\) 联通，就找到 \(v\) 一段的最小点 \(x\) 并连边 \((1,x)\) 。现在考虑怎么优化，正做是困难的，因为它在删边。考虑倒着做，就是 \(Q=n-1\) 时一定是以 \(1\) 为根的菊花，在这个基础上加树边，我们要找到对答案贡献最好的边：当前一条边的权值是，\(a_u+a_v-(\min\limits_{x\in S_u} a_{x}+a_1)\) ，\(S_u\) 是 \(u\) 所在联通块的点集。这个就容易了，用 set 维护这些边，每次加边时会合并两个联通块，合并之后需找出这个联通块对外的最小边，可并堆即可。

17.P8553 醒来

18.P5659 [CSP-S2019] 树上的数

发现我们每指定一个权值要从 \(u\) 换到 \(v\) ，就会产生一些限制：考虑 \(u\) 到 \(v\) 的路径，这上面的第一条边必须是与 \(u\) 相邻的边中第一个被删的；最后一条边必须是与 \(v\) 相邻的边中最后一个被删的；对于中间的点，删完前一个边后必须立马删后一条边。

确定了每个点与之相邻的边的删边顺序后，是一定存在一组合法方案的（肯定连不出环）。用链表维护这些限制，每次枚举 \(p_x\) 查看是否合法即可。复杂度 \(O(n^2)\) 。

19.ABC234Ex Enumerate Pairs

有点神奇的，就是说把整个图划分成若干 \(k * k\) 的块，那可能的点对只会在一个块内/两个相邻的块。下面我们说明，直接枚举上面两种情况，复杂度正确。对于一个块内，如果存在 \(x\) 个点，那一定有 \(O(x^2)\) 个点对，原因是对这个块能划分成 \(4\) 个 \(\frac{k}{2} * \frac{k}{2}\) 的小块，存在至少一个小块有 \(\frac{x}{4}\) 个点，而这些点距离不超过 \(\frac{\sqrt{2}}{2}k\) ，一定合法。再考虑相邻的块，设两个块的点个数为 \(a\le b\) ，我们需要枚举 \(ab\) 次。考虑 \(\sum ab\le \sum b^2\) ，发现每个 \(x^2\) 带的常数 \(\le 4\) 。这样就做完了，复杂度 \(400000C\) ，\(C\) 是不大的常数。

20.P4218 [CTSC2010] 珠宝商

处理路径，我们尝试点分治，每段路径都由两段拼起来。对于第一段，我们处理出它在文本串中的哪些位置出现了，对每个匹配的位置 \([l,r]\)，让 \(t_r\) 加上 \(1\) ，第二段同理计算 \(g_l\) ，最后统计 \(\sum t_ig_{i+1}\) 即可。现在就是要加速计算这两个东西。考虑“第一段”的这些串是怎么构成的，其实就是 dfs 一遍，当前的串 \(S_x\) 是由 \(S_{fa_x}\) 前面添加一个字符形成的。如果是在后面加就做完了：建 SAM 来匹配这个串，匹配到每个点时都在 fail 树上做一个子树加，由于只用最后查一遍，复杂度是 \(O(n+|T|)\) 的。现在是前面加，我们怎么搞呢。需要用另一种方式来找到当前匹配到的节点：其实这个时候就是走到后缀树上的儿子，要理解好 SAM 呀。

此时总复杂度是 \(O(n\log n+n|T|)\) ，寄掉了，考虑优化：如果当前大小已经 \(\le B\) 了，我们直接枚举每一个点为路径的一个端点， dfs 并计算答案即可，这个是 \(O(B^2)\) 的。对 \(>B\) 的还是像上面做，复杂度就是 \(O(n\log n+|T|\frac{n}{B}+nB)\) 的，取 \(B=sqrt{n}\) 即可做到 \(O(n\sqrt{n})\) 。

21.P9062 [Ynoi2002] Adaptive Hsearch&Lsearch

考虑把平面分成 \(2^k*2^k\) 的网格，然后有结论：对每个点我们只需要找与它在相同网格 or 在相邻网格的编号相邻的 \(O(1)\) 个点即可。于是找出点对后二维偏序即可，复杂度 \(O(n\log^2n)\) 。

22.P8885 「JEOI-R1」子序列

先考虑对给定的序列计算子序列个数，我们设 \(f_{0/1}\) 为以 \(0/1\) 结尾的子序列个数，\(g\) 为当前子序列总个数，则转移是 \(f_c'=g,g'=g+f_c\) ，那在模 \(2\) 意义下就是交换 \(g\) 和 \(f_c\)。初始状态是 \(\{0,0,1\}\) ，那我们只需要记 \(1\) 的位置即可。

考虑对给定的串怎么计算合法的子段个数。与 CSP-S T2 类似的，考虑一个子段 $[l,r] $合法，当且仅当跑完 \([1,l)\) 后 \(1\) 的位置与 \([1,r]\) 相同。那我们把这个串跑一遍，统计 \(t_i\) 表示有多少个前缀使得 \([1,x]\) 跑完后 \(1\) 的位置在 \(i\) ，则合法子段有 \(\sum \tbinom{t_i}{2}\) 个。由于只关心这个式子的奇偶性，我们记下来 \(t_i\) 模 \(4\) 的余数即可。

计数就是把上面的 \(t_i\) 压成状态捏。记录当前 \(1\) 的位置是没必要的，我们可以直接说 \(t_i\) 是有多少个 \([j,r]\) 满足最后 \(1\) 位置在 \(i\) ，则每次是交换 \(t_c,t_2\) 并让 \(t_2\) 加 \(1\) 。但是还能优化：由于长度固定时 \(\sum t_i\) 是固定的，只需记录 \(t_1,t_2\) ；然后，我们也不需要记录模 \(4\) 的余数，记模 \(2\) 的余数并在记一个 \(A\) 表示当前的答案。这样状态就是 \(8\) 了。算子段答案就是用猫树，先算左边，再算右边，拼起来即可。注意这里有细节：需要枚举 \(mid-l\) 的奇偶，不然就不好整了。

23.AGC044E Random Pawn

我们能断环为链：找到最大的 \(a_p\) ，在 \(p\) 处断开即可，因为走到 \(p\) 一定要停下。现在有 dp 方程：\(dp_i=\max(\frac{dp_{i-1}+dp_{i+1}}{2}-b_i,a_i)\) 其中 \(dp_0=dp_n=a_n\) 。

感受一下，这个式子和凸有些相关。如果 \(b_i\) 全是 \(0\) ，那把 \((i,a_i)\) 的上凸包求出来即可。现在考虑转化一下式子，即我们设 \(f_i=dp_i+c_i\) ，那有 \(f_i=\max(\frac{f_{i-1}+f_{i+1}+c_{i-1}+c_{i+1}}{2}-b_i+c_i,a_i+c_i)\) 。那就是让 \(\frac{c_{i-1}+c_{i+1}}{2}-b_i+c_i=0\) 即可满足上面的式子。\(c_0\) 和 \(c_n\) 都是能任意取的，那 \(c_1\) 也是任意取的，然后递推后面的 \(c\) 即可，这个题就做完了。

24.AGC011E Increasing Numbers

主要就是这个形式的数能拆成若干 \(\frac{10^p-1}{9}\) 的和捏。那把原来的 \(n\) 乘上 \(9\) ，再枚举用 \(x\) 个数凑。那就是 \(pop(n+x)+x\) 。从小到大枚举 \(x\) ，动态维护 \(n+x\) 即可。