NOIp 2025 邮寄

· · 生活·游记

Day -25

发现自己 DP 能力没有一点长进。

神秘机房电脑一天死机两位数次，hyw。

Day -24

生日，好耶。

模拟赛吃上史了，图计数下放 NOIP 说是。

Day -？

CSP-S:100+100+100+12=312,赢。

Day -13

打了一周模拟赛，分挂完了，就当积攒 RP 了。

Day -12

中大奖了，970->980，RP掉完了。

Day -5

激战 Hydra 8h 拿下 0-0-1。RP 回归。

Day -1

激战魔法手杖无果，遂去复习 Trick。

晚上吃了某华姓三字品牌汉堡，这样明天拉肚子 NOIP 就没事了。

Day 0

早上在床上肚子痛，不想起床。

CQ-0042.

NOIP RP++.

晚上和 @tkdqmx、@thtntht、@GoldSpade，玩了一晚上桌游，被狠狠制裁。

Day 1

I believe myself.

八点到了一中，在机房门口楼梯徘徊讨论要不要跳一个砸死拔树的竞争对手。

进考场排到一个逆天位置。

8:27 解压成功。

发现 T1 是简单贪心，遂速写了一个假做法，然后改掉。8:50 左右过所有样例。

然后看 T2，终于感觉自己集训期间的计数没白做，花了半个小时构造出充要条件并糊了一个 O(n^4) 的做法，然后去看了一眼 T3，T4，发现了树的遍历与擂台游戏，遂回来看 T2。

上手写 T2 发现后缀和优化统计答案加背包就是 O(n^3)，于是先写上，差不多 10:30 过了所有大样例，只是 sale11 跑了 522s。

然后想优化，从前往后枚举瓶颈就只剩一个地方了，背包 DP 式很有特色，于是考虑从这里入手，自己推了半天没看出来式子是范德蒙德卷积，想了很久，最后打表出来发现是杨辉三角 /ll/ll。

然后发现自己代码里有：

for(int k=m-1;k>=0;k--)  dp[i]=(dp[i-1]+dp[i-2])%mod;

没爆 RE！！！

太神人了，但还好不用这个 DP 数组了。

之后把二分改成双指针，变成 O(n^2) 跑得飞快，顺带又改掉一个访问负下标的问题，不得不感叹自己的幸运。

11:44 通过 T2 大样例，这个时候已经急成啥了。

看 T3，发现一点思路没有，然后想了个状压，以为能骗 n\le 18，结果是 O(n4^n) 的，优化是个类子集卷积的东西，遂放弃。

看 T4，没有任何思路，过了一会想到可以对每个数单独处理，用单调队列可以 O(n) 求定长的答案，但这样就是 O(n^2q) 的，空间也是 O(n^2) 的，甚至过不了 4 和 5。但不打就是 200 出头了，一点希望没有，硬着头皮打吧。

于 12:49 拿下 T4 15pts。

不对这个特殊性质 B 是不是套上去可以 O(nR_{max}q)！！！

于 12:53 拿下 T4 30pts。

不对这个特殊性质 A 是不是只记录有用的长度套上去可以 O(nq)！！！

于 12:57 拿下 T4 40pts。

燃尽了。

出来发现 T1 有 m<S 的 conner case，发现因为自己直接在之前写的假做法上改的于是规避掉了，运气太好了。

一问同学发现一堆 100+eps，还有 300+INF 的p话哥。

一边走路一边想 T2 代码，看群里说 sale2 有很多 conner case，但自己只用这个测了三次方代码，担心自己会出问题。

下午出去玩了一下午。

晚上回家重写了 T2 代码，交到洛谷上只有 76 吓哭了，找到大样例，一测，挂了，发现有个地方没取模，改了就 A 了，悬着的心总算放下了。

估分：100+100+16+40=256，省一确定，但在 CQ 进队机会渺茫啊。

可我终究还是不如梦想中那样的自己，惟余叹息而已。