ICPC2025 成都区域赛题解
A
记 l_i = 10\max(a_i-1,0)+5，r_i=10a_i+5，L=\sum l_i，R=\sum r_i。
那么 L > 1000 或 R \le 1000 时无解。
令 \sum a_i 为 10^9，先令 \text{ans}_i=10^6l_i，接下来只需在保证 \text{ans}_i < 10^6r_i 的情况下，将 \sum \text{ans}_i 调整为 10^9 即可。
B
首先容易想到一个状压 DP：记 f_{i,S} 表示前 i 轮，最后一轮使用过技能的集合为 S 的答案。
令 w(T,S) 表示从集合 T 变为集合 S 能打出的伤害（若 AP 溢出则为 -\infty），那么就有 f_{i,S} = \max\left\{f_{i-1,T}+w(T,S)\right\}
由于 (\max,+) 满足矩阵乘法的结合律，因此我们预处理出 w 矩阵，矩阵快速幂计算出 w^R 即可得到答案。
时间复杂度 \Theta((2^n)^3 \log R)。
C
好题。
正着做要考虑船到岸的时候人是否到岸，比较复杂。
考虑倒着做。二分答案，此时只需 check 每个人是否能在他的到达时间之前将其送回对岸，由于倒着做时每个人都已经到达，无需等待，所以直接贪心即可。
时间复杂度 \Theta(n \log A)，A 为答案的值域大小。
D
记 f_{i,j} 表示在进入第 3 步前得了 i 分，用了 j 个红球且红球后击打彩球均成功的方案。总共只有 121 \times 15 个状态，显然可以直接 dfs 预处理求出。
容易发现，一局游戏的得分一定可以由若干个 1/ + A 的 f + B 的 f + 最后在第 3 步的若干个彩球还原。
我们考虑暴力枚举开头 A 和 B 分别用了多少个 1/，以及最后若干个彩球的击打情况，此时我们可以得到 A、B 还需要的分数 s_A,s_B 以及剩余可用的红球数 R。
我们再枚举 i \in [0,R]，判断 f_{s_A,i} 与 f_{s_B,R-i} 是否
均可行即可得到方案。注意特判最后能否将当前玩家 p 调整为正确状态。
时间复杂度 \Theta(T \cdot 15^32^6)。
E（待补）
F（待补）
G
优先使用 m 次修改，每次修改均将一个数改为 k。
剩余的部分假设还有 k,2k,3k,\dots,tk，那么显然还能进行如下的 1+\lfloor\frac{t-1}{2}\rfloor 次操作：
- \left\{k\right\}；
- \left\{2k,3k\right\}；
- \left\{4k,5k\right\}；
- ……
注意实现细节。
H（待补）
I（待补）
J
直接判断每篇论文是否已经通过，若未通过经过申诉后的得分是否可以通过即可。
K（待补）
L
先不考虑树，我们直接考虑如何判断两个序列 a,b 是否同构。
记 \text{cnta}_i 表示 a 中 i 的出现次数，\text{cntb}_i 表示 b 中 i 的出现次数。
那么若 \text{cnta}_0 \ge \displaystyle\sum_{i=1}^n[\text{cnta}_i < \text{cntb}_i](\text{cntb}_i-\text{cnta}_i) （记为 \text{sum}_-）且 \text{cntb}_0 \ge \displaystyle\sum_{i=1}^n[\text{cntb}_i < \text{cnta}_i](\text{cnta}_i-\text{cntb}_i) （记为 \text{sum}_+），则 a,b 同构。
现在回到树上，我们用线段树维护子树的 \text{cnta},\text{cntb}，以及 \text{sum}_- 和 \text{sum}_+，合并子树时线段树合并即可。
时间复杂度 \Theta(n \log n)。