ICPC 南京 2023 做题记录

A. Cool, It’s Yesterday Four Times More

唐．注意到 $nm \le 10^3$，可以一遍 bfs 预处理出袋鼠 $(a, b)$ 能不能踢掉袋鼠 $(c, d)$，然后暴力枚举袋鼠对判断．

! B. Intersection over Union

不会几何．

C. Primitive Root

有 $g = (kP + 1) \oplus (P - 1)$，暴力枚举 $k$ 显然不行，但是 $k$ 的取值肯定形如一段很长的连续段接很短的一段散块，计算连续段大致的端点后暴力统计散块即可．

* D. Red Black Tree

特技 DP 题．

设 $f_{u, i}$ 表示以 $u$ 为根的子树是好的，且 $u$ 到子树中的任意叶子都有 $i$ 个黑色节点的最小代价．若令 $g_{u, 0 / 1}$ 为将 $u$ 节点变成红 / 黑的代价，那么有转移：

$$f_{u, i} = \min_{0 \le j \le 1} \{g_{u, j} + \sum_v f_{v, i - j}\}$$

注意到转移是一个 $(\min, +)$ 卷积，而我们知道，两个凸序列的 $(\min, +)$ 卷积一定还是凸序列，而 $g_u$ 肯定是一个凸序列，故对于所有 $u$，$f_u$ 都是凸序列．而两个凸序列的 $(\min, +)$ 卷积可以通过将两个序列的差分归并排序得到．证明可以考虑 Minkowski 和合并凸包，但是还有更简单的证法！$(\min, +)$ 卷积的本质是对每个 $i$，在两个序列的差分中各选一个前缀，使得元素数为 $i$，且和最小．由于凸序列的差分单调，直接贪心选前 $i$ 小即可．

那么拿个 std::set 或 std::priority_queue 即可维护出 DP 数组的差分．由于 $f_{u, i}$ 中，$i$ 的取值范围只有 $u$ 子树中最浅的节点到 $u$ 的距离，类似长剖可以分析出总状态数 $O(n)$．

* E. Extending Distance

神仙东西，完全不会．

考虑网格图的对偶图，原图最短路对应对偶图最小割．问题转化为选某些边增加容量，使得最大流大小增加 $k$．

这不是我们最小费用可行流问题吗！显然可以费用流求解，但是原图最大流可能很大，伪多项式复杂度的 SSP 直接寄了．注意到大部分流量都是由费用为 $0$ 的边贡献的，费用为 $1$ 的边只会贡献 $k$ 的流量，故可以先跑 Dinic 将 $0$ 边贡献的流量流完，然后再在残量网络上跑费用流．时间复杂度 $O(n^2 m^2 k)$．

F. Equivalent Rewriting

首先，若相邻均不能交换，那么其他元素也不能交换，一定不存在方案．若存在一对相邻元素可以交换，那么直接交换即可．故我们会进行的操作只有交换相邻元素，只需考虑如何快速检查相邻元素是否可以交换即可．

由于后面的操作会覆盖掉前面的操作，故倒序扫描，考虑如何检查 $i - 1$ 和 $i$ 是否能交换．$i$ 后的操作会导致某些位置被覆盖，这些位置不会影响 $i - 1$ 和 $i$ 的交换，直接丢掉．然后两者能交换就等价于保留未被丢掉的位置后，两个操作的覆盖位置没有交集．直接做即可．

* G. Knapsack

注意到若 $a$ 被零元购，$b$ 被买走，那么必然有 $w_a \ge w_b$．故若将所有物品按照 $w$ 升序排序，存在一个分界点 $i$，使得 $i$ 前的物品是付费拿走的，$i$ 后的物品是免费拿走的．枚举 $i$，对前缀做 01 背包，后缀贪心选前 $k$ 大即可．

! H. Puzzle: Question Mark

不会构造．

I. Counter

按题意模拟即可．

! J. Suffix Structure

太困难！！！

! K. Grand Finale

还没补．

* L. Elevator

首先，若直接将重量为 $2$ 的包裹拆成两个重量为 $1$ 的包裹，这个问题就变成为了经典问题．做法是将所有包裹按 $f$ 降序排序，然后顺着每 $k$ 个分一组．新问题的最优解显然是原问题的一个下界，接下来我们证明存在构造可以达到这个下界．

考虑一个类似的贪心：将所有包裹按照 $f$ 降序排序，然后顺着选直到当前包装满，再装下一包．由于 $k$ 是偶数，这个构造和新问题的构造每个包内最多只会有 $1$ 的位移，又由于有位移的包开头一定是 $2$，故位移不会影响答案．

* M. Trapping Rain Water

注意到 $\min\{f_i, g_i\} = f_i + g_i - \max_i a_i$，故只需想办法维护 $f$ 和 $g$ 的和即可．

由于高度只增，故直接使用 std::set 维护不同的前缀最大值即可．

事实上如果高度会降也可以用单侧递归线段树的技巧维护．