命题:人民大学
难度:CBH / DI / FJ / AKL / EGM
牌线:CDH / B / F+

https://rl.algoux.cn/collection/official?rankId=hbcpc7th

IDDiffDescriptionSolutionCodeReview
BHardNN 长非负序列 AA,MM 次操作:对每个数用正整数 XiX_{i} 更新 mex / gcd / 任选其一。判断能否使 AA 全相等。(1) 枚举所有可能,把所有可能情况存起来。实时去重。
(2) 复杂度分析:(a) 若没有经历 mex,gcd 后 ∣A∣≤D=max⁡(d(x))=1344\lvert A \rvert\leq D = \max(d(x)) = 1344,最多存在 1 个 ∣A∣=O(D)\lvert A \rvert = \mathcal{O}(D);
(b) 若经历过 mex,最后一次 mex 后 ∣A∣≤3\lvert A \rvert\le 3,继续 gcd 使 0 成为 gcd,不同后缀 gcd 的取值个数为 O(log⁡V)\mathcal{O}(\log V),最多存在 O(log⁡V)\mathcal{O}(\log V) 个 ∣A∣=O(1)\lvert A \rvert = \mathcal{O}(1)。
© 去重有个 log⁡\log,总复杂度近似为 O(Nlog⁡N+M(Dlog⁡D+log⁡V))\mathcal{O}(N \log N + M (D \log D + \log V))。
(3) 优化:若有超过两个任选,安排先 gcd 再 mex 即可,这样需要枚举的只有一个操作。
AC
CEasy按杀戮尖塔规则。第 ii 回合摸 AiA_i 张攻击和 5−Ai5 - A_i 张防御,最多打出 3 张。判断能否获胜。贪心。先判断尽可能打出攻击能否获胜,否则计算需要的防御数,在保证存活的前提下尽可能多地攻击。AC
DHard设 n=Nn=N。博弈。轮流:先手选择 0≤x<n0 \le x < n,令 n←n+xn \gets n + x;后手选择素因子 p∣np \mid n,令 n←n/pn \gets n / p。n=1n = 1 时游戏结束。先手最大化游戏总轮数,后手最小化游戏总轮数。如果选 n+x5n+x_{5} 有 p≥5p\geq 5 的素因子,与 n+x2=2kn+x_{2}=2^{k} 相比,n+x5p<2np<n2≤n+x22\frac{n+x_{5}}{p} < \frac{2n}{p} < \frac{n}{2} \leq \frac{n+x_{2}}{2},f(n+x5p)≤f(n+x22)f(\frac{n+x_{5}}{p}) \leq f(\frac{n+x_{2}}{2}),不优。因此 p=2,3p = 2, 3,枚举所有 m=2k3tm=2^{k}3^{t} 模拟。AC
FMediumNN 个奖品,第 ii 次重抽花费 C+iKC + i K 元,获得最后一次抽得奖品的价值。设资金无限,求最佳策略的收益期望。f(x)f(x):重抽期望收益为 xx 时,当前的最佳决策收益,即若 Ai>xA_{i}>x 选择停止,否则重抽。若 K=0K=0,解方程 −C+f(x)=x-C+f(x) = x。若 K>0K>0,倒序迭代模拟 x←−(C+iK)+f(x)x \gets -(C+iK)+f(x)。AC经典 long double 模拟过不去 hack。
WA:不判断 K=0K=0。
WA:二分下界应取 −C-C。
HMediumN×MN \times M 矩形。QQ 次垂直或水平切割。求所有小矩形的最大面积。答案即为 xx 轴最大线段长度与 yy 轴最大线段长度的乘积。用 set 维护切割点与 gap。AC
IMedium【润两次】First 根据给定的树,多次 flip 点权,Second 得到每次操作后所有边端点的异或值之和,并还原这棵树。AC
J按杀戮尖塔的毒药规则,允许在某时刻增加毒药总计至多 KK 层,求最大可能伤害。AC