跳至主要內容

ICPC 2022 南京区域赛(Nanjing Regional)部分题解

Wallbreaker5th大约 5 分钟OI×ICPCOI×ICPCOI×ICPC - 题解OI×ICPC - 二位前缀和OI×ICPC - 前缀和OI×ICPC - 二分OI×ICPC - 图论 - DFSOI×ICPC - 计数OI×ICPC - 计算几何

注意

题解写得可能非常抽象。

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

比赛链接:UCupopen in new windowCodeforces Gymopen in new window

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

题意

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

题解

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

B. 索道 / Ropeway

题意

山上要修建一条索道,起点在 00,终点在 n+1n+1,每个整点可以修柱子,代价为 aia_i;有的整点强制修柱子,相邻两个柱子的距离不能超过 dd。多次询问:如果把 aia_i 临时改为 jj,最小代价是多少。n5×105,d3000,q3000n\leq 5\times 10^5,d\leq 3000,q\leq 3000

题解

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

D. 聊天程序 / Chat Program

题意

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

题解

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

I. 完美回文 / Perfect Palindrome

题意

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

题解

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

J. 完美匹配 / Perfect Matching

题意

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

题解

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

K. 堆里的 NaN / NaN in a Heap

题意

一个小根堆(所有「自己小于父亲」为 false),包含 11n1n-1 和一个 NaN,求可能形态数除以 n!n!n109,T103n\leq 10^9,T\leq 10^3

题解

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

M. 清空水箱 / Drain the Water Tank

题意

有一个竖立的多边形水箱,装满了水;开尽可能少的孔,使得水箱内的水全部流出。n2000n\leq 2000。逆时针输入点,不保证没有三点共线。

题解

一个位置需要开孔意味着这里是一个局部最低点,有两种可能:

  • 一条边严格向下,下一条边严格向上,上方是多边形内部(用叉乘判断);
  • 一条边严格向下,之后若干条边 Δy=0\Delta y=0,然后一条边严格向上,上方是多边形内部(用水平的边的方向(向右)判断)。