NOIP 2025 ▇▇▇▇ 记

· · 生活·游记

标题是因为被崩铁 3.7 剧情刀了（

前作：NOIP2024 翻盘（？）记

接前作：省选被追忆单杀了，写了一场正解但是块长写错了，紧急转神秘 O(n^2)（能过）不知为何交上去了一份历史代码，直接坠机。

然后 APIO 爽写一场 A 因为没认真调块长喜提 75\to 74 从 Ag 挂到 Cu（C 写了一个随机操作，因为本题结论很强所以能过 43pts），这也是我这个金钩的来历。

CSP 游记

AT 也是早就上了 1 dan，虽然反复掉下去就是了。

主要训练方法是和 @Phrvth 打 duel，我写 *2500 让他十分钟写 *1500 和 *2000。

@Phrvth 经过一年的游玩，已经成为了蝶风大佬和社区对线大佬，而我还是 01 白坐牢玩家（准备补 2 白）。

考前稍微攒了两三天 RP，发了个工单，不知道有生之年能不能处理。

会赢吗.jpg

正文

又没睡好，到底是什么神人在使用这种开关（酒店某个灯关不上）。

考场不给带水进去，忍俊不禁。

进去发现我那个椅子晃得厉害，感觉如果我想就可以让它当场散架。

开局看 T1，五分钟秒了。

看 T2，开始严肃分析。

一开始分析出了将 1 换成 2 的神人东西，写写写发现假了。

然后发现其实是两个 1 换成一个 2 不优，枚举前面的 1 和 2 于是有式子 \sum\limits_{i=1}^n\sum\limits_{j=i+1}^n\left([a_i\not=a_j]+\sum\limits_{k}2^k[a_j+a_k \ge a_i]\right)\left(\sum\limits_{x}\binom{i-1}{x}\binom{j-i-1}{m-1-x-i}\right)，其中 x 表示 [1,i) 内选了多少个 2，也就是选 i 之前选了多少个 2，当然要求 2a_j\gt a_i。

第一个式子是简单的，但是我不会范德蒙德卷积所以第二个式子只会 n^3 还贼难调，调系数和范围到了 12：15，好在实测能过 n=1000，因为大概有几十分之一的常数。

期间我破防了一次前往 T4 试图注意力上线看出正解，但是没看出特别简单的做法，拼了个 n^2+nq\sqrt n 的 35pts 和 nq 的 L_i=R_i，写完 T3 暴力后会了 L_i\ge \frac{n}{4} 但是时间不够了。

然后我注意到 T3 关键性质，枚举每个点贡献的祖先（儿子贡献的深度小于父亲），实测随便跑 n=13 但跑不了 n=40，自测跑不了 n=18，其实这个很容易改 DP 做到 O(n^3)。

原地退役了（？

分数大概是 100+92+16+45=253，也确实是 100+92+16+45=253。

关于补二命白厄：

然后当天晚上点了发十连：