2024.2 做题记录

我草要省选了．

Codeforces 1753D The Beach

发现一张床不会同时进行平移和旋转：若同时进行，则一开始就存在一个 $1 \times 2$ 的可用空间，答案是 $0$．

平移和旋转会恰好占去一个空位且释放一个位置，可看作空位在地图上的移动，转化成最短路模型，建图直接跑即可．

Codeforces 1750F Majority

容易发现一个不合法的局面一定在若干次操作后形成若干 $01$ 连续段，满足相邻的 $1$ 连续段长度之和小于其中间的 $0$ 连续段．

设 $f_{i, a}$ 表示长度为 $i$，两段均为 $1$，若干次操作后最后一个 $1$ 连续段的长度为 $a$ 的方案数．转移枚举除去最后一个 $0$ 连续段和 $1$ 连续段的子问题长度 $j$ 和除去的 $0$ 连续段的长度 $b$，有转移：

$$\begin{aligned} f_{i, a} &= \sum_{j < i} \sum_{a + b < i - j - a} f_{j, b} \\ f_{i, i} &= 2^{i - 2} - \sum_{a} f_{i, a} \end{aligned}$$

对限制稍加变换得到 $j + b < i - 2a$，可维护 $i + a = x$ 的所有 $f_{i, a}$ 的和的前缀和来加速转移．

Codeforces 1854D Michael and Hotel

首先我们注意到可以通过二分在 $\log n$ 次询问内问出一个节点的后继，全问一遍就做完了…吗？

注意到询问次数只有 $2000$，$n \log n$ 的询问次数不可接受．

显然题目中给的图是内向基环森林，能相遇 $\iff$ 在同一棵内向基环树上 $\iff$ 走 $\infty$ 步能走到同一个环上．我们只需要问出 $1$ 所在内向基环树的环即可．

注意到 $1$ 开始走足够多步一定能走到一个环上，故我们可以先弄出环上的一个点 $s$．然后就不会了．

题解是这样做的．先以 $k \log n$ 的代价弄出环上的 $k$ 个点，然后尝试倍增，设当前环上已知点的数目为 $c$，我们找出所有到已知点步数为 $c$ 的点，显然环上已知点的 $c$ 级前驱都在这些点内，我们成功倍增了环上的已知点数目．这一步可能加入一些不在环上的点，但是环上点的数目始终已知：完成第 $i$ 次倍增后，环上已知点的数目为 $k2^i$．若这一步找出的点数目小于当前环上已知点的数目，那么已经找到了环上所有点，直接退出．

询问次数为 $\log n + k \log n + O(n \log (n / k))$，取 $k = n / \log n$ 可得询问次数为 $O(n \log \log n)$．

Codeforces 1916F Group Division

考虑增量构造：初始令集合 $S = \{1\}$．记点集 $V$ 的导出子图为 $G[V]$．我们每次找到在 $G[V - S]$ 中，与 $S$ 间有边，且不是 $G[V - S]$ 的割点的某个点 $u$，然后将 $u$ 加入 $S$．

引理：我们总能选出这样的 $u$．

证明：若 $G[V - S]$ 没有割点，容易选出 $u$．否则我们总能找到一个割点 $x$，使得删除 $x$ 后的 $G[V - S]$ 存在一个没有割点的联通块 $T$．$T$ 中肯定存在一个点和 $S$ 相邻，不然删除 $x$ 后 $T$ 和 $S$ 在原图中不连通，与原图是点双联通图矛盾．

Codeforces 1218G Alpha planetary system

记 $s_u$ 表示 $u$ 所有邻边的边权和．

从三分图性质入手，我们将三部分的点分别赋权 $0, 1, 2$．设 $a_u$ 表示我们赋的权，若我们能构造边权使得 $s_u \equiv a_u \pmod 3$，我们就做完了．

考虑随便弄出一棵生成树，将所有非树边权值赋为 $3$，让其不对同余关系造成影响．随便定一个根 $r$，若与儿子相连的边的权值已知，那么我们就能通过调整父边权值来满足同余关系．问题出在我们选的 $r$：它没有父亲，无法调整 $s$ 使得根满足条件．

发现若原图中存在一个过 $r$ 的奇环，那么我们可以通过交替 $+1$ 和 $+2$ 调整奇环上的边权来构造 $s_r$ 的任意增量，同时不影响其他的 $s$．故若原图中存在奇环，那么直接选一个奇环上的点作为 $r$ 即可．

现在来考虑原图中不存在奇环的情况，此时原图是二分图，钦定 $1$ 节点颜色为 $0$ 染色，重新定义 $a_u$ 为此时的颜色，定根为 $1$ 然后同上述做法的前半部分．现在考虑何种情况需要调整，若 $s_1 \equiv 1 \pmod 3$，那么会造成冲突．我们希望令 $s_1$ 加 $2$ 来满足同余条件．若 $1$ 度数为 $1$，此时不需要调整：$n \ge 3$，$1$ 的邻居 $v$ 度数肯定大于 $1$，故 $s_v > s_u$．只需考虑度数 $\ge 2$ 的情况，随便选两条边各自加 $1$ 即可满足限制．

Codeforces 1437F Emotional Fishermen

若我们钦定了所有前缀最值的值，那么按照值从小到大，能放的位置依次减少，故考虑设 $f_i$ 表示当前最值为第 $i$ 大的数，所有能放的值（即两倍 $\le$ 前缀最值的值）都已放下的放置方案数．每次考虑新增的能放下的数的放置情况．设第 $i$ 大的值限制下能放的值有 $x$ 个，第 $j$ 大的值限制下能放的值有 $y$ 个，那么有转移

$$f_i \xleftarrow{+} f_j \binom{n - 2 - y}{x - y - 1} (x - y - 1)!$$

足以解决本题，也容易优化至 $O(n)$．

Codeforces 924F Minimal Subset Difference

先考虑如何计算一个数划分后两部分和的差的最小值，这玩意显然只能背包，而又由经典结论，这种背包值域只需要开到 $V(V - 1)$，在本题中等于 $72$．

那么直接一个暴搜糊上去，只会有 $12880$ 个不同背包数组．于是我们可以考虑建出自动机后大力套上 dp．

设 $f_{i, j, u}$ 表示限制为两部分差 $\le i$，还有 $j$ 位要填，当前在自动机上的 $u$ 节点，转移枚举下一位填 $c$，有：

$$f_{i, j, u} \xleftarrow{+} f_{i, j - 1, \delta(u, c)}$$

统计答案先差分，然后枚举 lcp 长度即可．

Codeforces 618F Double Knapsack

好难．

考虑将子集限制收紧到子段．我们对两个序列做前缀和，记得到的数组为 $\mathrm{sa}_i$ 和 $\mathrm{sb}_i$，区间对 $([l_1, r_1], [l_2, r_2])$ 合法的条件是 $\mathrm{sa}_{r_1} - \mathrm{sa}_{l_1 - 1} = \mathrm{sb}_{r_2} - \mathrm{sb}_{l_2 - 1} \iff \mathrm{sa}_{r_1} - \mathrm{sb}_{r_2} = \mathrm{sa}_{l_1 - 1} - \mathrm{sb}_{l_2 - 1}$．

现在来尝试找到这样的区间对．不妨令 $\mathrm{sa}_n \ge \mathrm{sb}_n$，我们对每个 $i$ 求出最大的 $j$，使得 $\mathrm{sb}_j \le \mathrm{sa}_i$，此时有 $\mathrm{sb}_{j + 1} > \mathrm{sa}_i$，那么整理可得 $0 \le \mathrm{sa}_i - \mathrm{sb}_{j} < n$，又我们可以有 $n + 1$ 对 $(i, j)$，根据鸽巢原理，一定能选出合法的区间对．

LOJ 3646 「2021 集训队互测」《关于因为与去年互测 zjk 撞题而不得不改题这回事》

考虑如何处理询问．众所周知最大化 and 和性质非常不好，故我们先考虑一个暴力．我们考虑贪心地从高位到低位确定答案，设当前确定到第 $i$ 位，维护一个当前能选的数的集合．若这个集合里前 $k$ 大的数第 $i$ 位均为 $1$，那么答案中该位可为 $1$，此时将集合中该位不为 $1$ 的数剔掉；否则该位不能为 $1$，将集合中的数的这一位全部置 $0$．

这样单组询问都做不了．但是我们考虑这个过程的每一步决策：若该位填 $1$，剔除操作不影响剩下数的顺序；若该位填 $0$，那么只会对 $O(k)$ 个数造成影响．若我们用堆来维护这个前 $k$ 大，那么我们一共只会有 $O(k \log V)$ 次更改操作，故整个过程只涉及链上前 $O(k \log V)$ 大的值．

这个时候就能直接上树了，我们弄个超级钢琴类似物弄链上前 $x$ 大即可．

AtCoder ARC148D mod M Game

由于总共有偶数个数，故最后一步是 Bob 操作．

Bob 要赢得比赛，关键是最后一步该如何走．最后一步前，若 Alice 取的数和为 $a$，Bob 取的数和为 $b$，剩下两个数分别为 $x$ 和 $y$，Bob 必胜当且仅当

$$\begin{cases} a + x \equiv b + y \pmod m a + y \equiv b + x \pmod m \end{cases}$$

解得 $2x \equiv 2y \pmod m$，那么我们将这样的 $x$ 和 $y$ 两两建边，若存在完美匹配那么 Bob 就能赢，否则 Alice 赢．

AtCoder ARC151E Keep Being Substring

若两串存在公共子串那么显然是先变到公共子串再变过去，关键是不存在公共子串的时候如何做．

观察到变换流程形如加一个字符再删一个字符，故将字符看作点，将一个字符和与他相邻的字符建边跑最短路，最短路即为变出某个字符的最小代价．

AtCoder AGC045C Range Set

考虑倒序操作，每次可将连续 $a$ 个 $0$ 或 $-1$ 变成 $-1$，或将连续 $b$ 个 $1$ 或 $-1$ 变成 $-1$．要求最后序列中全为 $-1$．

由于要求全为 $-1$，$0$ 和 $1$ 没有区别，可交换，故令 $a \le b$．发现我们只需要造出了 $b$ 个 $-1$ 就能通过端点扩展来覆盖整个序列．故一个序列合法的条件是存在一段长度 $\le b$ 的子串，满足其中不包含长度 $< a$ 的全 $0$ 子串．

那么直接设 $f_{i, j, 0 / 1}$ 表示当前长度为 $i$，长度为 $j$ 的后缀不包含长度 $< a$ 的全 $0$ 子串，最后一个值是 $0 / 1$ 的方案数，转移枚举下一段是啥．

观察到转移形如斜线和，对每个斜线前缀和一下即可 $O(n^2)$ 解决整个问题．

Codeforces 1923F Shrink-Reverse

传奇宗师 Linnyx 曾有言：位数小才是真的小．

故我们直接二分最后留下的区间的长度，钦定最后剩下的数就是这个长度．考虑如何检查一个区间合法，我们需要将区间外的 $1$ 全都通过 $1$ 次操作换到区间内，利用前缀和即可判定．

然后枚举所有合法区间，若还剩 $1$ 次操作，该区间只能是反转的，否则可以再通过一次 $2$ 操作转回来．将所有可能作为答案的区间扒出来，由于我们要最小化值，又长度一定了，故等价于最小化字典序．我们从区间外面换进来的 $1$ 肯定是从最终串的后部往前替换 $0$，稍微分类讨论即可知比较换完串的字典序就是比较原串字典序．具体地，考虑两个串 $s$ 和 $t$，若 $s < t$ 但替换后 $s > t$，考虑替换后 $s$ 和 $t$ 第一个不同位置，一定有 $s$ 这一位是 $1$ 而 $t$ 这一位是 $0$，故替换影响到了 $s$ 的这一位，故 $s$ 这一位后全是 $1$，而 $t$ 中 $1$ 的个数和 $s$ 中 $1$ 的个数一致，故 $t$ 这一位后也全是 $1$，矛盾．

比较字典序可用后缀数组或二分 hash．