ICPC 2024 香港区域赛（Hong Kong Regional）部分题解

注意

题解写得可能非常抽象。

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

倒闭了，开场看错 K，给 F 想了两个假做法，给 E 想了一个假做法，感觉至少浪费了两个小时的机时。

~~等上 UCup 再写题解吧（？）。~~

有 $n$ 个敌人，每个敌人有一个血量 $a_i$ 和盾牌 $b_i$ 。给定序列 $c_{1\dots k}$ 。你一个回合可以选一个 $1\leq i\leq k$ ，花费 $c_i$ 的代价，对所有敌人造成 $i$ 的伤害。一个敌人被攻击时，如果其盾牌为正，则其盾牌减少 $i$ （可能变为负），否则其血量减少 $i$ 。求最少花费多少代价消灭所有敌人（血量小于等于 $0$ ）。 $m\leq 5\times 10^5,m\leq 10^4, k\leq 100$ 。3 s。

题解

首先注意到，总的伤害一定比 $\max a_i+b_i$ 大不到 $k$ 。DP，设 $f[i,j]$ 表示现在已经给了 $i$ 的攻击，目前知道需要的总攻击比 $\max a_i+b_i$ 大 $j$ 。一开始 $j$ 为 $0$ 。而当我们在 $i$ 的时候做出 $k$ 的攻击，会导致有的攻击被浪费（把盾牌扣到负数）、它对应的敌人需要的总攻击就会比 $a_x+b_x$ 大，这时 $j$ 需要对这个敌人需要的总攻击取 $\max$ 。当 $i$ 追上了 $\max a_x+b_x+j$ 时，所有敌人都被杀死了。

C. The Story of Emperor Bie

题意

你要搭建出一个给定的正整数序列。你可以初始选定一个正整数，序列一开始只有这个数。然后你一次操作可以选择左/右，在序列的这一端添加一个数，满足其不大于序列另一端的数。问，要搭建出给定的这个序列，有哪些数可能作为初始的数。 $n\leq 5\times 10^5$

题解

充要条件是这个位置是最大值。充分性考虑逆序做这些操作、总能反复删掉两端较小的一个；必要性考虑每次加的数一定小于等于初始值。

E. Concave Hull

（是的我对哈尔滨那场的计算几何过拟合了套了一个错误结论占了一万小时的机时）

（没有题解）

F. Money Game 2

（是的这题一开始榜被带歪了，我们想了两个假做法）

题意

$n$ 个人坐成一圈，第 $i$ 个人初始有 $a_i$ 块钱。依次操作，一个人可以把他的钱的一半的下取整给旁边的一个人，每个人至多操作一次。现在对于每个人求：他最后最多能得到多少钱。 $n\leq 5\times 10^5, a_i\leq 10^9$ 。4 s。

题解

首先注意到一个人的贡献并非只能传播给 $\log a_i$ 以内的人。因为 $1$ 的变动足以让除以二下取整的结果也加 $1$ 。进位也不能用简单的判断就解决。

首先，最优答案一定是划定一个分界，分界一侧的人往一个方向依次传、另一侧的人往另一个方向依次传，最后传到收钱的人。

我们不妨先假设收钱的人是 $0$ 、只考虑从右边往左传给 $0$ 的。 $0$ 收到的钱是 $\left\lfloor \sum_{i=1}^{m} \frac{a_i}{2^i} \right\rfloor$ 。注意到 $m$ 增长时，前 $\log V$ 次这个结果可能增加；而 $\log V$ 次之后，这个求和因为是收敛的，结果至多增加 $1$ 。我们认为当 $m$ 从 $m-1$ 变到 $m$ 时，如果这个求和增加了，这个增加是由 $m$ 造成的贡献。那总的贡献对只有 $O(n\log V)$ 对。

现在反过来，考虑贡献的来源，我们可以从它出发、向左向右枚举，从而求出它对每个位置的贡献；当贡献变成 $0$ 就停止枚举，从而求出所有的贡献对。贡献对只有 $O(n\log V)$ 对，所以这样枚举的总复杂度是 $O(n\log V)$ 的。

接下来，我们若固定分界点，没有跨过分界点的贡献对（注意到我们枚举贡献对的时候，是知道顺逆时针方向的）都是真的有贡献，每个位置的答案就是以它为贡献目标的贡献对的权值之和。我们枚举分界点，每次增删受影响的贡献对，以及更新受影响的位置的答案，总复杂度是 $O(n\log V)$ 的。

G. Yelkrab

题意

给定字符串 $s_1, \dots, s_n$ ，对于所有 $1\leq i\leq n$ 求 $\bigoplus_{j=1}^i f(i,j)$ 。其中 $f(i,j)$ 表示：将前 $i$ 个字符串分出若干大小为 $j$ 的组（可能有字符串不在组内），每个组求 LCP，对所有组求 LCP 之和，的最大值。 $n\leq 5 \times 10^5, \sum |s_i|\leq 10^6$ 。

题解

首先考虑给定 $i,j$ 后怎么求。我们建出字典树，从下往上贪心，能凑出 $j$ 个串求凑一组。转化一下，可以变成，对于每个节点求 $\lfloor \mathit{size}_x / j \rfloor$ 求和（其中 $\mathit{size}_x$ 是以 $x$ 子树下的字符串数）。

接着我们一个串一个串加入，加入一个串时，会改变一些节点的 $\mathit{size}_x$ ，从而某些 $j$ 的 $\lfloor \mathit{size}_x / j \rfloor$ 求和会加一。我们异或掉它们的旧答案、异或上新答案。由于数的约数个数和不大，时间复杂度没问题。

H. Mah-jong

（好像不是我做的）

K. LRString

（是的我们签到题读错题了）

题意

给定字符串 $S$ ，字符集为 $\{\texttt{L},\texttt{R}\}$ 。你一次操作可以选择一个字符，然后删去它相邻的、L 就是左侧、R 就是右侧的字符。多次给出 $T$ ，询问 $S$ 能不能操作成 $T$ 。 $|S|, \sum |T|\leq 10^6$ 。

题解

充要条件是： $T$ 是 $S$ 的子序列； $S$ 如果以 L 开头，那么 $T$ 以 L 开头； $S$ 如果以 R 结尾，那么 $T$ 以 R 结尾。

L. Flipping Paths

（是的我们想到了一个麻烦的做法于是没有写出来）

题意

有一 $n\times m$ 的网格，每个格子初始为黑/白。你可以选多条 $(1,1)$ 到 $(n,m)$ 、只向右或向下的路径，每条路径会让其经过的格子颜色翻转。构造不超过 400 条路径，使得所有格子同色，或者判断无解。 $n,m\leq 200$ 。

题解

从左下开始，依次考虑所有左上-右下的对角线（除去上边、右边的部分）。

a.....
a.....
aa....
baa...
.baa..
..baa.
...baa

例如我们考虑上图中的 b 组成的对角线，注意到我们沿着路径 a 一路走、在需要翻转 b 的时候走 b，其他时候走 a，可以独立控制每个 b 是否翻转。以这个方式可以把除了第一行、最后一列的所有格子变成指定颜色，最后再考虑第一行、最后一列的这条路径即可。外层还要枚举一下最终的颜色。