做题笔记 2024.1 省选训练题单
约定：题目标题后会用一个 0.0 到 1.0 间的实数表示本题有多少部分由自己解决。0.0 表示完全根据题解完成，1.0 表示完全由自己完成，其余实数则表示部分参考题解。
CF513E2 Subarray Cuts (0.4)
由于是要最大化一些绝对值的和，我们可以直接将绝对值去掉，因为错误指定绝对值开出来的符号只会使答案变劣。现在我们的式子变为了 $\pm(s_1-s_2)\pm(s_2-s_3)\pm(s_4-s_5)\dots$，展开后会发现 $s_1$ 和 $s_k$ 的系数为 $\pm 1$，$s_{2\dots k-1}$ 的系数为 $\pm 2$ 或 $0$，并且所有非零系数一定正负交替。
接下来可以基于此进行 dp，记录当前正在选取的段是什么符号即可，注意开头和结尾可以有一段不选，另外不难证明所选的段必然连续，如果两段之间有数不选，将这些数和左边或右边的段合并至少有一种方式是不劣的。于是设 $f_{i,j,0/1,0/1}$ 表示已经考虑了前 $i$ 个数，正在选取第 $j$ 段，上一个系数非零的段的符号是 $+/-$，第 $j$ 段系数是否为 $0$ 时原式的最大值，转移时考虑继续扩展当前段或新开一段即可，注意特殊处理第一段和最后一段的系数。
Insights. 最优化目标和限制一致时可以将限制去掉。
CF578D LCS Again (1.0)
$\operatorname{LCS}(S,T)=|S|-1$ 感觉上是一个很强的限制，这意味着我们可以这样从 $S$ 得到 $T$：从 $S$ 中删去第 $p$ 个字符 $S_p$，然后在任意地方插入任意字符，但不能再在 $S_p$ 所在的极长同字符连续段内插入相同字符。显然对于一个连续段而言删哪个字符都一样，所以我们对每个连续段只计算一次。但是这样还是会有重复。观察一些较短的字符串，我们只需解决这三种情况即可：
-
在一个连续段内插入和该段相同的字符只能计算一次。
（即，如果向 $\texttt{aaaa}$ 中插入 $\texttt{a}$，无论插入在什么位置都等价。）
-
形如交换两个连续段分界处字符的方案会被恰好多计算一次。
（即，若 $S$ 为 $\texttt{aaaabbbb}$，则一种合法的 $T$ $\texttt{aaababbb}$ 既可以通过「删 $\texttt{b}$ 插 $\texttt{b}$」也可以通过「删 $\texttt{a}$ 插 $\texttt{a}$」得到。）
-
形如 $\texttt{ababab}\to\texttt{bababa}$ 的方案会被恰好多计算一次（奇偶长度均如此）。
当然，可以认为第二种情况是第三种情况的特例。可以证明以上已经考虑了所有算重的情况（根据删除和插入字符的距离，若间隔为 $1$ 则是第二种情况，间隔更长则可以证明只有第三种情况）。
CF757F Team Rocket Rises Again (1.0)
跑最短路后将所有满足 $d_v=d_u+w$ 的边 $(u,v,w)$ 拿出来建生成子图，这是一张 DAG。不难发现如果删去一个点 $x$，最短路会发生改变的点 $u$ 满足从 $s$ 到 $u$ 的最短路必须经过 $x$，换言之，在最短路图上 $x$ 支配 $u$。所以我们跑 DAG 支配树即可。
CF248E Piglet's Birthday (1.0)
数据范围很小。注意到每个货架上未品尝过的蜜罐个数总是不超过最开始的 $a_i$，因为从别的货架转移过来的蜜罐一定是已品尝过的。我们在线维护每个货架未品尝的蜜罐个数为 $0\sim a_i$ 的概率，每次操作枚举货架上有多少个蜜罐未品尝、选取了多少个未品尝的蜜罐，乘上组合数就可以维护出新的概率。
CF464D World of Darkraft - 2 (0.0)
以前做的题，大体思路是由于题目允许 $10^{-9}$ 级别的误差，经过计算发现一件装备升至 $10^3$ 级的概率已经小到可以在精度限制下忽略不计，所以我们只需要考虑 $10^3$ 以下的级别。
装备之间相互独立且等价，我们对一件装备计算获得金币的期望即可。设 $f_{i,j}$ 表示还剩 $i$ 次操作，当前等级为 $j$，进行剩余操作可以获得的金币的期望个数。这里是倒序转移，若顺序转移则需要再记录概率。
CF906D Power Tower (0.8)
扩展欧拉定理。
CF113D Museum (1.0)
我们有一个比较抽象的做法。考虑到本题允许精度误差，我们直接设 $f_{i,a,b}$ 表示走了 $i$ 步后一个人在 $a$，另一个人在 $b$ 的概率，这样不断进行转移，在足够的步数之后就可以得到精度可以接受的答案。
我使用了矩乘加速转移，总复杂度为 $O(n^6(-\log\epsilon))$。当然这个矩乘没啥必要，直接暴力做也可以。
另外的解法有：
- 枚举终点 $x$，设 $f_{a,b}$ 表示一个人在 $a$，另一个人在 $b$，最后在 $x$ 相遇的概率，高斯消元求解即可。复杂度 $O(n^7)$。
- 设 $f_{a,b}$ 表示到达「一个人在 $a$，另一个人在 $b$」这一状态的期望次数，直接高斯消元求解即可。复杂度 $O(n^6)$。使用期望次数是因为本题中同一状态可以多次到达。
CF1363F Rotating Substrings (0.9)
开始做了半天不会，看到题解开头发现题看错了。
题目中的操作等价于将一个字符向前移动。考虑如果我们知道 $s$ 中每个字符最后移动到了什么位置，我们断言一个字符需要被移动当且仅当存在一个原来在它前面的字符最后出现在了它之后，这可以通过构造证明。
我们考虑 dp，从前往后对 $s$ 中的字符匹配一个 $t$ 与之相同的字符。根据上面判断一个字符是否需要移动的条件，在考虑 $s_i$ 时，我们需要知道 $s_{1\dots i-1}$ 在 $t$ 中匹配的最靠后的字符在什么位置。于是设 $f_{i,j}$ 表示已经考虑了前 $i$ 个字符，在 $t$ 中匹配的最靠后的字符是 $t_j$，对于 $s_{i+1}$，我们考虑它匹配的字符在 $t_j$ 之前还是之后，可以证明若在 $t_j$ 之后，匹配第一个和 $s_{i+1}$ 相同的字符总是不劣的，基于此进行转移即可。总复杂度 $O(n^2)$。
这种做法其实最后得到的 dp 和题解做法一模一样，不过我觉得这种思路更加直观一些。
CF603E Pastoral Oddities (0.0)
很炫酷的一道题。
我们发现有解当且仅当图中所有连通块大小均为偶数。
由于最终选取的边集满足每个点度数为奇数，每条边会为连通块的度数和贡献 $2$，连通块度数和总是偶数，所以连通块内点数为偶数，原图的连通块是该生成子图中若干连通块的并，大小也为偶数。（必要性）
另一方面，若连通块大小为偶数，我们任取一棵生成树，从下往上考虑每个点，若该点当前度数为偶数，则连上其与父亲间的边，这样可以使所有非根节点满足条件，而由于总度数为偶数，除根外的点度和为奇数，所以根节点的度数也为奇数。（充分性）
如果是解决单次查询，为了使最大边权最小，我们可以将边从小到大插入，直到某个时刻所有连通块大小均为偶数。
现在有加边操作，首先我们可以使用 LCT 动态维护首次满足条件时的最小生成森林，复杂度 $O(m\log n)$。同时还有一种从后往前边计算答案边插入边的半在线线段树分治做法。
除此之外，我们考虑整体二分。我们需要判断 $[l,r]$ 中哪些位置的答案 $\le w$，首先 $l$ 左侧，边权 $\le w$ 一定需要加入，然后我们从 $l$ 到 $r$ 扫一遍，碰到 $\le w$ 的边就加入，看什么时候能够满足所有连通块大小均为偶数，那么这之前部分的答案 $>w$，当前及之后的位置答案 $\le w$。
为了保证整体二分的复杂度，我们需要避免大量重复的加边操作。若当前正在考虑区间 $[l,r]$，答案区间为 $[vl,vr]$，我们试着保证 $l$ 左侧，边权 $<vl$ 的边已经全部被加入，这是可以做到的。在当前区间，令 $mid\gets \lfloor(vl+vr)/2\rfloor$，我们需要加入所有 $l$ 左侧，边权在 $[vl,mid]$ 间的边，以及所有 $[l,r]$ 之间，边权 $\le mid$ 的边。整体二分的每一层中 $[l,r]$ 与 $[vl,vr]$ 均不交，所以复杂度可以得到保障。
需要使用可撤销并查集，总复杂度 $O(m\log V\log n)$。
CF600F Edge coloring of bipartite graph (0.2)
一个结论是，无向简单图边染色所需的最少颜色数为 $d$ 或 $d+1$，其中 $d$ 为图中点的最大度数。
特别的，在二分图中，所需最少颜色数为 $d$。
我们按某个顺序给边染色。设当前考虑到边 $(u,v)$，若 $[1,d]$ 中存在 $u,v$ 均未使用过的颜色，则直接将 $(u,v)$ 染上该颜色。否则由于 $u,v$ 都存在未使用过的颜色，一定有 $c_1,c_2$，其中 $c_1$ 未被 $u$ 使用过而被 $v$ 使用过，$c_2$ 则反之。考虑将 $(u,v)$ 染成 $c_1$，此时产生了冲突，我们考虑将与 $v$ 相邻的被染成 $c_1$ 的边的颜色改为 $c_2$，此时还可能产生新的冲突，我们不断进行修改即可。这条 $c_1,c_2$ 的交替路径总会终止，因为这条路径不可能走回到已经走过的点上，这一点结合原图是二分图的性质很容易证明。
使用上述算法染色即可，总复杂度为 $O(m(a+b))$。
CF809E Surprise me! (1.0)
由于本题值域较小，时限较宽松，我们可以有一些对数学没啥要求，比较暴力的做法。
考虑点分治，处理所有跨过分治中心的路径。
现在我们需要计算 $i$ 对路径权值和的贡献。考虑 $\varphi(a_i\cdot a_j)\operatorname{dis}(i,j)$，由于已经做了点分治，式子可以化为 $\varphi(a_i\cdot a_j)(dep_i+dep_j)$，这里关于 $i$ 的项不方便完全提取出来，我们先将其化为 $\varphi(a_i)\cdot dep_i\cdot\frac{\varphi(a_i\cdot a_j)}{\varphi(a_i)}$。注意 $\frac{\varphi(a_i\cdot a_j)}{\varphi(a_i)}$ 并不等于 $\varphi(a_j)$，但是我们知道两式之间不一样的因式取决于 $a_i$ 和 $a_j$ 的公共质因子。具体来说，如果 $a_i$ 和 $a_j$ 有公共质因子 $p$，则 $\frac{\varphi(a_i\cdot a_j)}{\varphi(a_i)}$ 会将 $\varphi(a_j)$ 中 $(1-\frac1p)$ 的因式去掉，因为这个因式已经在 $\varphi(a_i)$ 中算过了。
注意 $1\le a_i\le 2\times 10^5$，这意味着 $a_i$ 的质因子个数不超过 $6$ 个，我们直接枚举 $a_i$ 和 $a_j$ 有哪些公共质因子。如果当前枚举的公共质因子的乘积为 $p_0$，我们查询满足 $p_0\mid a_j$ 的 $\varphi(a_j)$ 之和，这里只能做到确定 $a_i$ 和 $a_j$ 的公共质因子包含现在枚举的这些数，所以还需要使用 FMT 进行一步容斥。接下来我们就知道了满足 $a_i$ 与 $a_j$ 的所有公共质因子恰好是某个集合的 $\varphi(a_j)$ 之和，从中除去对应的 $(1-\frac1p)$ 然后贡献到答案中即可。
总复杂度为 $O(n\log n\cdot \omega(n)2^{\omega(n)})$，其中用 $\omega(n)$ 表示 $\le n$ 的正整数最多有多少个质因子，本题中 $\omega(n)=6$。瓶颈在 FMT，不知道有没有办法去掉。
CF814E An unavoidable detour for home (0.3)
由于 $1\rightsquigarrow i$ 的最短路唯一，所以满足条件的无向图一定形如一棵最短路树，加上若干同层点之间的额外边。同时由于最短路长度随 $i$ 增加单调不减，每层点的编号一定连续，并且下层编号大于上层编号。
从前往后考虑每个点，由于每个点（除 $1$ 外）都要向上层的点连一条边，所以考虑过程中每个点的剩余度数只可能是 $1$ 或者 $2$。我们有一个直观的 $O(n^5)$ dp，设 $f(i,la,lb,ca,cb)$ 表示已经考虑了前 $i$ 个点，上一层还有 $la$ 个一度点、$lb$ 个二度点，当前层还有 $ca$ 个一度点、$cb$ 个二度点。转移比较简单，注意特殊处理第一层。
这种做法复杂度高主要在与上层点可能连向一个或两个下层点，从上往下考虑时我们需要分别记录一度点和二度点的个数，而如果从下往上考虑则避免了这个问题，因为每个下层点会连向恰好一个上层点，这样我们只需要记录点数即可。这也符合树上 dp 要从下往上进行的经验。
我们设新的 dp $f(i,j)$ 表示现在已经考虑了 $i\sim n$，最后选取的一层由 $i\sim j$ 构成，转移则枚举当前层取哪些点。预处理 $g(a,b,k)$ 表示上层有 $a$ 个一度点，$b$ 个二度点，下层有 $k$ 个点的连边方案数。$f,g$ 都可以在 $O(n^3)$ 的时间复杂度内计算出来。$g$ 的转移比较复杂，方案很容易算重，这里我们钦定先考虑二度点，再考虑一度点，并且每次总是考虑编号最小的点的连边情况。具体转移可以参考代码。总复杂度 $O(n^3)$。
CF198D Cube Snake (0.5)
为了满足题目条件，我们希望让最终的立方体满足对于每个 $i < n$ 都存在一个 $i\times i \times (i + 1)$ 的长方体，使得其中两个 $i\times i\times i$ 的部分编号都连续，换言之，我们应当先走完底层，然后走中间的部分，然后再走顶层。
考虑递归构建满足条件的 $k\times k\times (k+1)$ 的长方体，对于原题，只要构建出规模为 $n$ 的长方体然后削掉顶层即可。
递归构建需要我们在长方体上留出「接口」。我们约定接口在底层的右下角和顶层的右上角。
对于 $k\times k\times (k+1)$ 的长方体，我们从右下角开始经过一个 $k\times k$ 的矩形到达左下角，然后接入一个 $(k-1)\times k\times(k-1)$ 的长方体（经过了旋转），移动到底层右上角的上方，经过一个 $k\times (k-1)$ 的矩形到达顶层右下角，然后再经过一个 $k\times k$ 的矩形到达顶层右上角。
上面除递归外一共描述了三个移动过程，可以证明总是存在一种合法的移动方案，构造也不复杂。
代码实现各显神通，我的有点麻烦。
CF198E Gripping Story (0.7)
考虑搜索找出所有可达的机械臂。将机械臂按照 $(d,m)$ 放在二维平面上，其中 $d$ 为到船的距离，$m$ 为质量，每个机械臂能抓到的区域是一个左下角的 2-side 矩形。2 维偏序做起来相当麻烦，用 KDT 可以做到根号，运行效率并不理想。但是注意搜索的特性是一个机械臂被标记为可达之后就不必再考虑这个机械臂了，适用均摊分析，我们只要能在合理的时间内找到任意一个当前机械臂能抓到的、还没有访问过的机械臂即可。
可以使用线段树。一维作为线段树下标，然后维护另一维的最小值，每次相当于在区间内找一个 $\le x$ 的数，如果当前结点的最小值比 $x$ 大则退出当前结点，否则向两个儿子递归，到达叶子后返回叶子上最小值对应的机械臂，并将最小值更新即可。
找到一个机械臂的复杂度是 $O(\log n)$，总复杂度 $O(n\log n)$。
Submission #240447302 (KDT, TLE)
CF446D DZY Loves Games (1.0)
题目看起来并不困难，我们只要求出从起点和每个陷阱房出发，下一次到达每个陷阱房的概率，这样就得到了一个转移矩阵，做快速幂即可。
问题在于前面那个步骤，陷阱房最多有 $t:=101$ 个，求从某处出发到每个陷阱房的概率需要做 $O(n^3)$ 的高斯消元，总复杂度 $O(tn^3)$，无法接受。但是我们发现这 $t$ 次高斯消元非常相似，事实上，系数矩阵没有发生任何变化，只是最后增广的那一列发生了改变。由于消元过程取决于系数矩形，所以每次消元做的初等行变换也没有变，于是我们将消元过程中的 $O(n^2)$ 次初等行变换记录下来，对于每个不同的常数列，只需要在这一列上执行记录的操作就可以求出结果，总复杂度 $O(tn^2)$。
CF494E Sharti (0.1)
这种棋盘翻转游戏看起来非常麻烦，因为难以拆分子游戏，但是实际上我们可以证明每个白格子都可以视为一个独立的子游戏。
为了证明这一点，我们考虑构造这样一个游戏：原游戏中的白格子视作是格子上放了一颗棋子，而黑格子则为空，我们将原游戏中的正方形反色改为拿掉右下角的棋子，并在正方形的其余位置添加一颗棋子。这个游戏和原游戏的性质相同。我们自然的会猜想，奇数颗棋子应该等价于白格子，偶数颗则等价于黑格子，事实上也的确如此，必胜方只需要在对手操作偶数颗棋子的格子时进行相同的操作、其余时候执行原游戏的必胜策略即可。而在修改后的游戏中，很显然每一颗棋子都是独立的，所以整个游戏的 $SG$ 值就等于每颗棋子 $SG$ 值的异或和，于是原游戏的 $SG$ 值也可以用这种方式计算。
每个格子对应的 $SG$ 值可以递推计算出来，枚举选取的正方形的边长即可，但是这样做的复杂度不能接受。
直接给出结论，$(i,j)$ 处对应的 $SG$ 值为 $\min\{\operatorname{lowbit}(i),\operatorname{lowbit}(j),\operatorname{highbit}(k)\}$。Froggy 的题解里给出了这个结论证明的链接，我只大概理解了一下证明的思路。
有了结论后，我们枚举 $2^i$，用扫描线求 $SG\ge 2^i$ 的位置数量，然后就可以计算整个游戏的 $SG$ 了。
CF273E Dima and Game (1.0)
这个游戏显然可以使用 $SG$ 函数，同时注意我们只关心区间长度，求 $SG$ 值可以直接关于长度递推。但是 $p$ 很大，没法直接做，不过又没大到完全没法处理的地步。如果我们将所有长度的 $SG$ 值打出来会发现其中大段都是连续相同的值（基于递推式这也是显然的推断），所以我们可以将每个连续段压起来打表。
显然一个区间的 $SG$ 值不会超过 $2$，整个游戏的 $SG$ 值不会超过 $3$。解决本题只需要再套一个背包即可。
CF736D Permutations (0.0)
这个题需要一些数学前置知识，没有的话就是做不了。
完美匹配计数实际上是做积和式，所谓积和式就是将行列式计算时的正负号去掉。积和式的计算是 #P 完全的，但是本题中我们只关心值的奇偶性，此时正负号无所谓，所以计算积和式和行列式的结果相同。
这样，题目就变成了，在 $\mathbb F_2$ 上给一个行列式为 $1$ 的方形矩阵，问将矩阵中的哪些 $1$ 改为 $0$，矩阵的行列式仍为 $1$。将一个 $1$ 改为 $0$ 实际上等价于从原本的行列式计算中去掉了选取这个 $1$ 的方案，所以题目等价于在问，对于矩阵中的哪些 $1$，所有选取它的方案的值之和为 $0$，或者说，去掉对应行列，剩余部分的行列式为 $0$。这样去掉一行一列得到的行列式也被称作余子式。
由于要对于每个 $1$ 计算余子式，我们显然不能暴力做。
代数余子式定义为余子式乘上 $(-1)^{i+j}$，其中 $i,j$ 为删除的行和列的编号，在 $\mathbb F_2$ 上这个系数不重要。我们称每个位置对应的代数余子式的值构成的矩阵的转置为伴随矩阵，若将方形矩阵 $A$ 的伴随矩阵记作 $\operatorname{adj}(A)$，我们有 $A\operatorname{adj}(A)=\det(A)I$，这个自证不难。本题中 $\det(A)=1$，若想得到 $\operatorname{adj}(A)$，只需计算 $A^{-1}$ 即可。
最后，我们对每个 $1$，检查其在 $\operatorname{adj}(A)$ 中对应位置的值即可。
参考：伴随矩阵 - 维基百科
CF625E Frog Fights (0.3)
用一个优先队列维护每只青蛙撞上下一只青蛙的时间，每次取出最早的碰撞事件，修改该青蛙的信息、删除下一只青蛙并更新前面一只青蛙的碰撞时间即可，需要思考一下实现细节，复杂度 $O(n\log n)$。
这里代码实现上有一些技巧，考虑如何计算一只青蛙经过一段时间后的位置，我的实现是记录最后一次更新该青蛙信息的时间和位置，从而接下来的查询都从这个时间戳开始计算，另一种方法则是基于更新后的速度前移青蛙的初始位置，将前面时间多走的路程直接算进初始位置里，后者要简洁很多，也不用特殊处理同一时刻多次碰撞的情况。
本作品采用 知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议 进行许可。
