ICPC 2022 南京区域赛（Nanjing Regional）部分题解

注意

题解写得可能非常抽象。

「如果一个题解你看不懂，那是题解垃圾而不是你垃圾。」

比赛链接：UCupopen in new window、Codeforces Gymopen in new window

A. 停停，昨日请不要再重现 / Stop, Yesterday Please No More

题意

一个 $n\times m$ 的网格，其中一个格子是坑（位置未知），其他格子初始各自有一只袋鼠。另输入一个字符串，字符为 LRUD，代表每只袋鼠同时向某个方向跳一格。跳出网格或者跳到坑里的袋鼠会消失。已知最后剩下的袋鼠数量，求有多少格子可能是坑。 $n,m\leq 10^3$ 。

题解

首先不考虑坑，那么最后留下的袋鼠对应原网格的一个矩形区域。只考虑坑，坑会坑掉一条路径（从坑的位置出发，与移动路径相反）上的袋鼠（一个格子多次经过只统计一次）。最后留下的袋鼠就是初始在矩形区域内、不被坑覆盖的格子的袋鼠。先处理出路径覆盖格子的二位前缀和（如果路径超出 $\pm n\times \pm$ 的范围，剩余袋鼠为 $0$ ），然后枚举坑的位置，统计多少袋鼠剩余，累加至答案。

B. 索道 / Ropeway

题意

山上要修建一条索道，起点在 $0$ ，终点在 $n+1$ ，每个整点可以修柱子，代价为 $a_i$ ；有的整点强制修柱子，相邻两个柱子的距离不能超过 $d$ 。多次询问：如果把 $a_i$ 临时改为 $j$ ，最小代价是多少。 $n\leq 5\times 10^5,d\leq 3000,q\leq 3000$ 。

强制修柱子的限制可以通过设 $-\infty$ 或者 DP 时精细处理解决。设 $f[i]$ 表示前 $i$ 个坐标， $i$ 上修柱子的最小代价， $g[i]$ 同理但针对后缀，二者都可以单调队列求出。对于询问，分两种情况：若选 $i$ ，从 $i$ 向前、后分别枚举 $d$ 个柱子，找到最小的 $f/g$ ；若不选 $i$ ，提出前后 $d$ 个柱子，再做单调队列。复杂度 $O(n+dq)$ 。

D. 聊天程序 / Chat Program

题意

有一个序列，给定 $m,c,d,k$ ，你可以选取一个长为 $m$ 的区间，使其依次加上一个首项为 $c$ ，公差为 $d$ 的等差数列。求第 $k$ 大数的最大值。 $n\leq 2\times 10^5$ 。

题解

二分。随后对于每个数，可以求出它在等差数列的位置在哪个区间，可以使其大于等于 $\mathrm{mid}$ ，从而求出等差数列的开始位置在哪个区间可以使其大于等于 $\mathrm{mid}$ ；记差分做前缀和，可以知道等差数列在每个位置时，可以使多少数大于等于 $\mathrm{mid}$ ，若达到 $k$ 个则 check 为 true。

I. 完美回文 / Perfect Palindrome

题意

给定一个字符串，一次操作可以修改一个字符，求最少操作次数使其所有的循环移位都是回文串。 $n\leq 10^6$ 。

题解

回文要求首尾字符相同，循环移位下即为相邻两个字符相同，所以所有字符相同即可。

J. 完美匹配 / Perfect Matching

题意

给定一个无向图，点有点权 $a_i$ ，两个点有边当且仅当 $|a_i-a_j| = |i-j|$ 。求一个完美匹配。 $n\leq 10^5$ 。

题解

首先求出 $a_i+i,a_i-i$ ，则两个点如果 $a_i+i$ 相同或者 $a_i-i$ 相同则有边。考虑另建一二分图，所有 $a_i+i$ 建一点、所有 $a_i-i$ 建一点，原图中的点对应边，现希望把所有边（按照有相邻点）两两匹配。在二分图上 DFS，拆成一个（包含所有边的）搜索树，在树上将所有边两两匹配，贪心即可。

K. 堆里的 NaN / NaN in a Heap

题意

一个小根堆（所有「自己小于父亲」为 false），包含 $1$ 到 $n-1$ 和一个 NaN，求可能形态数除以 $n!$ 。 $n\leq 10^9,T\leq 10^3$ 。

题解

对于一个没有 NaN 的堆，其形态数为 $\frac{n!}{\prod_i s_i}$ ，其中 $i$ 为子树大小。对于有 NaN 的堆，考虑 NaN 的位置，然后要把三块的形态数相乘，再乘以 $\binom{n-1}{s_l, s_r, n-1-s_l-s_r}$ 。经过一番化简，发现阶乘搞好都被消掉，重点在于三块的 $\prod_i s_i$ 。左右子树的 $\prod_i s_i$ 可以提前 DP 求出，对于父亲所在的那一块，在向下搜索的时候，从全树的 $\prod_i s_i$ 开始，每次除掉 $s_i$ ，到达当前点再除掉 $\prod_i s_i$ ，乘回到根链的 $s_j-s_i$ 。实现上可以按照「从根到当前点每个点的 $s_i$ 接起来为 vector」为 key 记忆化搜索。

一条边严格向下，下一条边严格向上，上方是多边形内部（用叉乘判断）；
一条边严格向下，之后若干条边 $\Delta y=0$ ，然后一条边严格向上，上方是多边形内部（用水平的边的方向（向右）判断）。