ICPC 2024 成都区域赛（Nanjing Regional）部分题解

注意

题解写得可能非常抽象。

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

比赛链接：UCup、Codeforces Gym

A. Arrow a Row

题意

定义一个箭头串为 >-...->>>（- 有一个或多个）。一个初始串长为 $n$，全为 *；一次操作可以将一个子串覆盖为一个箭头串。在 $n$ 次操作内把初始串变为给定串，或无解。$n\leq 10^5$。

题解

目标串一定是开头若干个 >、中间包含一些 - 和 >，结尾至少三个 >>>。先处理结尾的连续 >，每次覆盖 $[1,n]$、$[1,n-1]$、……、$[1,k]$。接着 $[2,k-3]$ 的部分全是 -、通过覆盖 $[i,k]$，可以把 $i$ 单独这个位置的 - 覆盖为 >。

B. Athlete Welcome Ceremony

题意

有一个 abc 构成的串，部分位置未知。多次询问，每次给定 $a,b,c$，问往未知部分填进不超过 $a$ 个 a、不超过 $b$ 个 b、不超过 $c$ 个 c，且满足相邻两个字符不相同的方案数。$n\leq 300$。

题解

先 $n^3$ DP 前 $i$ 个字符用 $j$ 个 a、$k$ 个 b、结尾字符是 $l$ 的方案数。DP 完后求三维前缀和即可 $O(1)$ 查询。

D. Closest Derangement

题意

给定排列 $p$，定义排列 $q$ 是好的当且仅当 $q$ 是 $p$ 的一个错排且 $\sum \left\vert p_i-q_i \right\vert$ 取到最小值。求所有好的排列中字典序第 $k$ 小的排列。$n\leq 2\times 10^5$。

题解

首先考虑 $q$ 长成什么样。$n$ 为偶数时，最优解为 $p_i=1$ 对应 $q_i=2$、$2$ 对应 $1$、$3$ 对应 $4$、$4$ 对应 $3$，且是唯一的最优解。

$n$ 为奇数时，我们无法做到每个差都为一，但最优解中只会有恰好一个 $m$ 指向 $m+1$、$m+1$ 指向 $m+2$、$m+2$ 指向 $m$ 的情况（或者反着指），因此 $q$ 只有 $n$ 个左右。特别地，若我们强制要求 $q_i=j$，简单讨论可以发现满足这一点的 $m$ 一定是一个区间（反着指会另外需要记录一个区间）。因此我们从头开始依次枚举 $q$ 的每个数是多少，通过判断【两个双区间求交的大小】可以判断出每个数。

K. Magical Set

题意

有 $n$ 个正整数，构成一个集合。一次操作可以把一个正整数变为它的一个非本身的因数，维持所有数互不相同。问至多能做多少次操作。$n\leq 300,a_i\leq 10^9$。

题解

首先，问题可以转化为给每个原正整数选一个约数，约数互不相同，使得约数的质因数个数之和尽量小；因为我们可以将一个数每次去掉一个质因数达到选定的约数，如果集合里有其他数阻挡，可以把阻挡的数连通当前正在想操作的数一同去掉一个质因数，其等价于把原本要操作的数穿过那些阻挡的数到达目标约数。

然后怎么最大流或者最优匹配一下即可，但 CF 上数据加强过，不知道怎么过。