4月杂题

1.AGC066D A Independent Set

先把 \(T\) 串看成是 \(AB\) 和 \(B\) 的拼接，把 \(T\) 变成 \(S\) 的过程看成是 \(A\) 在移动。

考虑 \(T\) 中一段极长的 \(AB\) 连续段，你发现最左边的 \(A\) 一定会往右移，否则可以让这个连续段左边的 \(B\) 与 最左边的 \(AB\) 交换，这是不劣的。最右边同理，于是我们发现这个连续段中 \(A\) 的移动只会在内部进行，不会移到外面去！

于是考虑 dp。我们设 \(dp_i\) 是让 \(S[1,i]\) 和 \(T[1,i]\) 相同的最小代价，则一种转移是在后面接 \(B\) ，即 \(S_i=B\) 时有 \(dp_{i-1}\rightarrow dp_{i}\) 。还有一种是接 \(AB\) 连续段，我们设 \(s_i\) 表示把 \(A\) 看成 \(1\) ，\(B\) 看成 \(-1\) 时 \(S\) 的前缀和，则 \(s_j=s_i\) 时可以有 \(dp_j+val(j,i)\rightarrow dp_i\) 。可以观察到对于这第二类转移，我们只需要找 \(j<i\) 且 \(s_j=s_i\) 的 \(j\) 中最大进行转移即可，因为中间若隔了一个 \(k\) 满足 \(s_j=s_k=s_i\) ，那显然 \((j,k],(k,i]\) 两段的交换互相独立，\(j\rightarrow i\) 就是不需要的了。那刨去这种情况后，对于 \(j<k<i\) ，要么 \(s_k\) 全部 \(>s_i\) ，要么全部 \(<s_i\) ，也就是说 A 是全部向左/右移的。所以权值是很容易利用前缀和计算的，复杂度 \(O(n)\) 。

2.gym104053D Digits

直接从左往右 dp 是无法处理回文串的，我们一定是左右交替的添加段，并不断的从两端消去字符。考虑设 \(f_{i,j,s}\) 表示： 划分 \([i,j]\) 能得到多少个串拼上 \(s\) 后是回文的，\(g_{i,j,s}\) 就是 \(s\) 接在前面的方案数。转移以 \(f_{i,j,s}\) 为例，我们枚举第一段 \([i,k]\) ，让 \([i,k]\) 得到的串 \(t\) 和 \(s\) 进行消除，如果两个串都没有消完就寄了；否则根据哪个串非空，用 \(f_{k+1,j,s'}\) 或者 \(g_{k+1,j,t'}\) 转移即可。

分析一下这样做的复杂度，可以总状态数是 \(n^3\log V\) 种的：还是以 \(f_{i,j,s}\) 为例，\(s\) 一定是某个 \([j+1,k]\) 形成的串的某个前缀。于是复杂度为 \(O(n^4\log^2V)\) ，看似不能通过，但因为状态根本卡不满，利用 unordered_map 是能轻松通过的。

还是想想怎么优化吧。还是以计算 \(f\) 为例，我们把转移分成两种：\(s'\) 为空， \(t'\) 为空。

对于 \(t'\) 为空的情况，相当于 \(t\) 是 \(s\) 某个后缀 reverse 后的结果。计算 \(f'_{i,j,s}\) 表示 \(\sum\limits_{k=i}^{j+1} f_{k,j,s}\) ，然后枚举 \(s\) 的这个后缀，可以发现我们需要的 \(k\) 一定构成一个区间 \([l,r]\)，于是用 \(f'_{l,j,s'}-f'_{r+1,j,s'}\) 即可计算。

对于 \(s'\) 为空的情况，我们不要直接枚举 \(s\) 。枚举 \(i,j,k\) ，我们可以得到 \(t\) 。发现能被转移的 \(s\) 只能是 \(t\) 一个前缀 reverse 后的结果，用 \(g_{k+1,j,t'}\) 转移给 \(f_{i,j,s}\) 即可。

复杂度 \(O(n^3\log V(\log n+\log V))\) 。

3.gym104076I Shortest Path

题意：给你一个带权无向图，令 \(ans_i\) 为：从 \(1\) 出发走恰好 \(i\) 条边到 \(n\) ，边权和的最小值，若不存在则为 \(0\) 。给定 \(x\) ，求 \(\sum\limits_{i=1}^x ans_i\) 对 \(998244353\) 取模的结果。

\(n\le 2000,m\le 5000,x\le 10^9\) 。

做法：

边数 \(\le4n\) 时直接暴力解决。

边数 \(>4n\) 时，可以感受到我们会通过少量的边到达一条关键边，往返若干次后再通过少量的边走到终点，因为此时边数是多余的，我们想在更小的边上”刷掉“这些边数。

有结论：

可一定存在一条最优路径满足：可以从 \(1\) 出发，先通过不超过 \(2n\) 条边走到 \(u\) ，在 \((u,v)\) 间往返若干次，再从 \(v\) 通过不超过 \(2n\) 条边走到 \(1\) 。

为什么呢？考虑一条不满足上述条件的路径并取出其中权值最小的边 \((u,v,w)\) ，把图上权值 \(<w\) 的边全部删去并把剩下的边权值全部减 \(w\) 。那如果从 \(v\) 到 \(n\) 的边数超过 \(2n\) 条 ，那我们可以把它替换成 \(v\) 到 \(n\) 边数同奇偶的最短路（边数一定不超过 \(2n\) 条）拼上若干次 \((u,v)\) 间的往返，这显然是不劣的。于是发现所有路径都能调整成上述的形式。

接下来考虑计算，先算出 \(A_{i,j},B_{i,j}(j\le2n)\) 分别表示 \(1\) 到 \(i\) 经过 \(j\) 条边的最短路，\(n\) 到 \(i\) 经过 \(j\) 条边的最短路。枚举这个关键边 \((u,v,w)\) ，计算出 \(X_i=\min\limits_{j\mod 2=i} A_{u,j}-jw,Y_i=\min\limits_{j\bmod 2=i} B_{v,j}-jw\) ，那么边数为 \(x\) 的答案即为 \(\min\limits_{i<2}(X_i+Y_{(T-1-i)\bmod 2})+xw\) 。

把 \(x\) 按奇偶分开后，实际上我们就能把 \(ans_x\) 写成 \(\min k_ix+b_i\) 的形式。

于是问题转化成，计算 \(\sum\limits_{x=L}^R \min\limits_{i} k_ix+b_i\) 。求出 \((k_i,b_i)\) 的凸包即容易计算。复杂度是 \(O(nm+m\log m)\) 。

4.gym103964I Mahjong

题意：给定 \(n,m\) ，其中 \(m\bmod 3=2\) 。 定义一个麻将牌集合是胡的，当且仅当：

1. 集合大小为 \(m\)

2. 可以划分成一个对子（即 \(i,i\)）和 \(\frac{m-2}{3}\) 个面子（即 \(i,i+1,i+2\) 或 \(i,i,i\)）。

现在有 \(4n\) 块麻将，其中大小为 \(i(1\le i\le n)\) 的麻将有 4 个。（同样大小的麻将被看做相同）问能从这些麻将中选出多少胡的麻将牌集合，对 \(10^9+7\) 取模。

\(n\le 100,m\le 200\) ，多测，\(T\le 100\) 。

做法：

先思考怎么判定一个麻将牌集合是胡的，可以考虑 dp：令 \(f_{i,z,x,k,l}\) 表示：已经确定了大小为 \(1\) 到 \(i\) 的牌的拆法， \([1,i]\) 中共有 \(z\) 张牌，有了 \(x\) 个对子，从 \(i-1\) 开始的顺子有 \(k\) 个，从 \(i\) 开始的顺子有 \(l\) 个的状态是不是能取到的。

可以看见 \(k,l\) 一定 \(\le 2\) ，因为一处选三个 \((i,i+1,i+2)\) 不如拆成 \((i,i,i)\) ， \((i+1,i+1,i+1)\) ，\((i+2,i+2,i+2)\) 。

回到原问题，我们就考虑 ddp，把 \(f_{x,k,l}(x<2,k\le 2,l\le 2)\) 这 18 个数以及 \(z\) 一起压成一个状态， 令 \(dp_{i,j}\) 表示考虑了大小为 \([1,i]\) 的牌，形成状态为 \(j\) 的方案数。这样看似难以通过，因为看上去压成的状态数量是 \(2^{18}m\) 级别的。

但可以发现能到达的状态是很少的！首先确定 \(z\) 后，\(z+k+2l-2x\) 不为 \(3\) 的倍数的话，就一定取不到了，所以状态数是 \(2^6m\) 级别的。经过程序检验可以发现，可以到达的状态只有约 \(4500\) 种，符合我们的估计。

预处理出这些会到达的状态以及往后接一个数后到达的状态，这个题就做完了，复杂度 \(O(2^6Tnm)\) 。

5.AGC052E

处理三染色问题的套路：构造权值 \(a_i\) 使得有边相邻的两点权值差 \(\le 1\) ，且模 \(3\) 与其颜色同余。

对于这个题，我们就可以用上述方法表示出原串 \(a\) 和目标串 \(b\)，我们要调整原串的 \(a_1\) ，使得操作步数最小。根据题目，每次肯定是让某个位置 +2/-2 ，所以最小代价一定不少于 \(\frac{1}{2}\sum |a_i-b_i|\) ，且需让 \(a_i,b_i\) 奇偶性相同。这也是可以达到的，不妨设存在位置满足 \(a_i>b_i\) ，找到其中最大的 \(a_p\) ，那一定有 \(a_{p-1}=a_{p+1}=a_i-1\) ，否则可以发现与最大性矛盾了。

就变成一个简单的解方程问题 (调整 \(a_1\)) ，容易完成。

6.AGC059E

和上面一题相同的套路：可以发现对于合法的三染色方案我们一定能构造出相应的矩阵。于是我们先算出边框的权值，若已矛盾显然无解；否则找点必要条件，首先 \(|a_{x,y}-a{z,w}|\le |x-z|+|y-w|\) ，但可以发现其中有一些限制是被其它限制包含的，具体的只需要判断 \(|a_{i,1}-a_{i,n}|\le n-1,|a_{1,i}-a_{n,i}|\le n-1\) 。

然后发现这就充分了！原因是我们可以构造 \(a_{x,y}=\max(a_{1,y}+(x-1),a_{n,y}+(n-x),a_{x,1}+(y-1),a_{x,n}+(n-y))\) 。

可以发现相邻两个差是恰好等于 \(1\) 的（可以先说明奇偶性不同，再说明差 \(\le 1\)）满足题目限制。

7.P9040 [PA2021] Desant 2

可以转化成 \(k*(n/k)\) 网格上只能往下/往右走，多次询问从 \(s_i\) 到 \(t_i\) 的最长路。

分治解决，每次把网格长边劈一半。每次需要特殊处理一行末尾到下一行开头的情况。

8.P7908 [Ynoi2005] qwq

对偶之后转化成 \(\sum a_ib_i\) 的最大值，其中 \(\sum\limits_{i=l}^{l+m-1}b_i\le 1\) 。经典猜测： \(b_i\in \{-1,0,1\}\) 。

忽略 \(0\) ，我们需要相邻两个 \(1\) 距离大于等于 \(\geq k\) 。我们在这些相邻 \(1\) 之间劈一刀，可以发现得到每一段的答案其实都是和 \(m=n\) 的答案相同的(因为没有相邻 \(1\)) 。

于是问题转化成，取出若干不交子段，使每个子段 \([l,r]\) 的 \(a_l+\sum\limits_{l<i\le r}\max(a_i-a_{i-1},0)\) 之和最大，且两个相邻子段距离 \(\geq m\) 。为了让权值最大，第一个子段肯定会包含 \(1\) ，最后一个子段肯定会包含 \(n\) ，而相邻子段距离肯定 \(=m\) 。于是可以转化成在 \([m+1,n]\) 中取一些数使得 \(a_i-\sum\limits_{j=0}^{m-1}\max(a_{i-j}-a_{i-j-1},0)\) 之和最大，且相邻两个差 \(\geq m\)。

问题转化的差不多了。再考虑区间询问。实际上就和上面那个题没有差别了。

9.LOJ4139 「PA 2024」Kraniki

相当于，对每个板子算有多少个水龙头的水会流到它头上。怎么算呢，从这个板子出发低往高看，维护一个区间 \([l,r]\) ，初始是这个板子代表的区间。然后如果遇到一个板子包含它，再往上的水就流不到了，停止过程；否则若有交，则答案 +1 且区间变成和这个板子的并。

仔细思考一下，难点在于找让你停止的板子，找到后即可倍增处理。怎么找呢，你发现这其实就是求支配树。复杂度 \(O(n\log n)\) 。

10.LOJ4134 「PA 2024」Desant 3

考虑这样一个 dp，就是状态 \(S\) 表示一些位置的数是确定值，一些在 0/1 间任选，然后我们想算 \(dp_{S,i}\) 表示所有填法中经过操作 \(i+1\) 到 \(q\) ，成为合法态的方案个数。那你发现对于下一次操作，如果两边都是 0/1 ，我们充分利用模 2 ，发现 01 和 10 的填法会两两抵消，于是把两个位置填上 00/11 的方案数加起来；如果两边都确定就直接模拟；如果有一边是 0/1，可以发现最后的状态是唯一的。复杂度是什么呢，注意到这个搜索树只会出现 \(O(2^{n/2})\) 个分枝的地方，于是复杂度 \(O(2^{n/2}m)\) 。

11.LOJ4130 「PA 2024」Splatanie ciągów

先分析一下 \(f(a,b)\) 的计算方式，不妨设 \(|a|=n>|b|=m\) ，\(c_i=[a_i>a_{i+1}]\) ，令 \(s_i\) 是 \(c\) 每个连续段的长度，那 \(f(a,b)\le x\) 等价于 \(\sum [(s_i-1)/x]\le m\) 。

现在要算 \(a,b\) 各取一个子段的 \(f\) 之和，不妨只考虑 \(a\) 中取的子段大于 \(b\) 取的子段的情况。计算出 \(a\) 这整个序列对应的 \(s\) 。

然后分治计算答案，对于每个 \(x\) 统计出 \(L_i\) ，表示有多少对 \((a,b)\) 满足 \(l\le a\le mid,b\le s_a,[(b-1)/x]+\sum\limits_{i>a} [(s_i-1)/x]=i\) 。随着 \(a\) 的减少，\(b\) 的增加，对应的 \(i\) 会不断增加，只需要在每次变化时正确的计算即可。于是这里复杂度是 \(O(\sum\limits_{x}\sum s_i/x=s_i\log s_i)\) 。\(R_i\) 同理可以计算出，最后计算 \(\sum L_iR_jF(i+j)\) 即可。其中 \(F(x)\) 是 \(b\) 中有多少子段长度 \(<x\) ，这是个分段一次函数，于是计算时枚举 \(i\) 并处理 \(R_i,R_ii\) 的前缀和即可快速计算。总复杂度大概是 \(O(n\log^2n)\) 。

12.LOJ4127 「PA 2024」Grupa permutacji

首先算出能造出的排列个数都是困难的，只能拆开计算，即对于 \(i<j\) 算出最后 \(p^{-1}_i>p^{-1}_j\) 的概率。对于每一个排列我们能在 \((i,j),(p_i,p_j)\) 间连边。最后对于每一个联通块，若其中 \(i<j\) 的点个数为 \(a\)，\(i>j\) 的为 \(b\) ，则答案加上 \(\frac{ab}{a+b}\) 。

问题是直接做复杂度是 \(O(n^2k)\) 的。怎么办呢，猜测可以随机化，但静心构造可以让 \(k\) 个排列都有用，于是考虑这样的随机化：每次任取排列的一个子集，算出把它们乘到一起得到的排列，用这个排列来连边。可以证明这样做 \(O(\log n)\) 次正确率就非常高了。不会证。

复杂度 \(O(n^2\log n)\) 。

13.CF1761F2 Anti-median (Hard Version)

通过观察长度为 \(3,5\) 的连续段可以得到合法排列的形式： \(a_{2i-1}<a_{2i}>a_{2i+1}\) ，且只看奇数位置呈单谷，看偶数位置呈单峰；也可以对称的把所有限制反过来。

只考虑第一种情况的方案数。我们把这些位置重排一下，即 \(1,3,5,...,...,6,4,2\) 这样排。把 \(1\) 到 \(n\) 依次填进这些位置，且把位置无限复制后，可以发现填了的值一定形成了一段区间，且需要满足 \(2\le l+r\le n+1\) ，但不包括终止位置。

后面就是比较平凡的计数了。

14.P10103 [GDKOI2023 提高组] 错排

计算 \(f(n,m)\) 为长度为 \(n\) 的排列其中对于 \(i\le m\) 有 \(p_i\neq i\) 。根据不同的枚举方式我们可以得到 \((n,m),(n+1,m)\) 推 \((n+1,m+1)\) ，\((n,m),(n,m+1)\) 推 \((n+1,m+1)\) ,\((n,m),(n,m+1)\) 推 \((n+1,m+2)\) 的方式。

于是通过这三种方式，我们维护 \((n,m),(n+1,m+1)\) ，每次 n/m +1/-1 时都能快速更新两个值，于是用莫队即可做到 \(O(n\sqrt{n})\) 。

15.万欧小复习

其实就是处理这类问题，随着 \(x\) 增大， \([(ax+b)/c]\) 变大时乘上矩阵 \(U\) ，\([x]\) 变大时乘上矩阵 \(R\) ，计算最后得到的矩阵。怎么做呢，考虑 \(f(a,b,c,n,U,R)\) 表示 \(x\) 从 \(0\) 增大到 \(n\) ，得到的结果。

怎么计算呢。先判掉 \(n=0\) ，此时等于单位矩阵 \(I\) 。分类讨论，\(a\geq c\) 时它等于 \(f(a\bmod c,b,c,n,U,U^{[a/c]}R)\) ；否则你考虑把这个 \(y=(ax+b)/c\) 中的 \(x,y\) 交换一下。

16.P10107 [GDKOI2023 提高组] 树

其实还是挺自然的，就一开始你会想定义一个 \(f(x,i)\) 表示 \(x\) 子树内 \(d_y-d_x<2^i\) 的点的 \(v_y\oplus(d_y-d_x)\) 之和，但这就需要我们得到子树内所有满足 \(d_y=d_x+2^{i-1}\) 的 \(f\) 之和。这里就需要做一个前缀和。

于是不妨改一下，设 \(f(x,i)\) 为 \(dfn_y<dfn_x+sz\) 且 \(d_x\le d_y<d_x+2^i\) 的点的 \(v_y\oplus (d_y-d_x)\) 之和。你发现这个时候 \(f\) 就非常好算了。用类似的方法多处理点东西，就容易进行询问了。

17.P10104 [GDKOI2023 提高组] 异或图

经典互不相等容斥。到最后是要算这么一个东西：就是容斥后的“生效集合”为 \(S\) 的方案数。先把这些数按 \(a\) 排序，然后考虑 \(f(S,T)\) 表示当前已经确定了 \(S\) 内的容斥方案，其中生效集合为 \(T\) ，直接转移是 \(O(4^n)\) 的，但你发现实际出现的状态是不多的，因为我们每次会让联通块包含第一个不在 \(S\) 里的集合。那么 \(T\) 不仅是 \(S\) 的子集，而且取出 \(S\) 的第一个 \(0\) 后，\(T\) 中的 \(1\) 都在这个 \(0\) 前面。也就是可以改写成 \(f(S',i)\) 表示 \(S\) 中第一个 \(0\) 在 \(i\) ，\(i\) 后 \(S\) 的状态和 \(i\) 前 \(T\) 的状态拼起来的结果。这样状态就是 \(O(2^nn)\) 的，总复杂度 \(O(3^nn)\) 。

18.P9052 [PA2021] Areny

类似于支配树，可以发现我们可以把图在不改变答案的情况下简化成一个内向基环森林。每次会加入一个点 \(u\) 的所有出边，这之前 \(u\) 一定是某个树的根，若它这些出点皆在一个联通块内，则我们找到这些点的 lca 为 \(f\) ，并连边 \((u,f)\) 。注意此时如果是 \(u\) 所在的联通块，则此树会变成基环树，需要处理一下。每次两个联通块合并后，可以发现会有一些新的点的出点在一个联通块内，这些新点能通过启发式合并/线段树合并快速找到，把它们丢到队列里并依次做上面的操作即可。

现在具体的思考一下应该怎么维护。由于这个题没有 cut 和 makeroot 操作，用 LCT 是非常清新的。每次连边 \(u,f\) 时答案会加上 \(f\) 到根的权值和，乘上 \(u\) 子树的 siz，我们只需要根的 siz 所以只需要在 LCT 上维护链的权值和。

变成基环树时我们直接暴力扫一遍计算答案的改变量，并修改上面的点的权值：把 \(u\) 的权值修改为环长，把环上其他点改为 \(0\) ，原来的树的形态是不需要改变的。

查 lca(u,v)，就是先 access(u)，再在 access(v) 时顺便记下跳到根所在实链时到达的点即可。总时间复杂度 \(O(m\log n)\)。