Travel「NOIP 2025 游记」
denominator · · 生活·游记
upd on 12.12：打错一个数字。
Day -28~0
自 CSP 获得
如果我当时 T3 使用两个 hash，是不是也不至于在样例 3 挂掉，甚至也不至于因此将原本正确的做法改错？
如果我当时孤注一掷地决定开难度并不是很大的 T4 而不畏惧，是不是可能会逆天改命？
想到今年 T3，鏖战 ~2h，获得
冷知识：你谷网校里有过一道 ACAM 的题。
今年 NOIP 是我最后一次以活跃的 OIer 的身份参与了，明年我可能还会来，只不过那种拼劲已经不存在了。
不安，惶恐，NOIP 的前夕总是那么难熬……
好了编不下去了，明天再见！到了故事的终点再见！
其他冷知识：
- 模拟赛里有好多需要用到高维前缀和的东西！这时才发现它和 FMT 不是一个东西（不知道曾经咋想的，可能被这题带偏了）。
- 兄弟你的笑话好像不怎么好笑。（luogu.me 好像不支持高亮行，凑合看看吧，有能力的人也可以做一些众所周知的行为）
Day 1
蚌埠住了，策略完全失误。心情很差，懒得放码长。
首先 T1 是签，15min 签掉。
比赛里面最为蚌埠住的是 T2，带大家体验一下我的心路历程。假做法，不想看可以跳过。
:::info[心路历程]
-
15min：显然是全部剪减掉不合法的。感觉是一个
\mathcal O(n^2) 的 dp，列 dp 数组先。将a 数组从大到小排序。设\mathrm{dp}_{i,j} 表示确定了前i 个是 1/2，贪心策略搞定之后还剩j 块钱的无解方案数。马上被自己笑得不行。 -
30min：算出 std 好像不太现实。考虑到 std 和贪心针对 1/2 都是选择（从大到小排序后的）一个前缀，而且不需要计算出 std 的正确答案，所以考虑贪心中以一换二是否更优。也就是说，将一个价值为 2 的物品换成两个价值为 1 的物品，代价可能更少。
那有没有可能出现以一换二不优，以二换四更有一点的做法呢？这是不可能的。假设以一换二是不优的。
那么就有
x_{i+1}+x_{i+2}\leq y_i 。但是我们有
x 和y 递减的性质，所以x_{i+3}+x_{i+4}\leq x_{i+1}+x_{i+2} ，且y_i\leq y_{i-1} ，所以x_{i+3}+x_{i+4}\leq y_{i-1} ，加在一起就是x_{i+1}+x_{i+2}+x_{i+3}+x_{i+4}\leq y_i+y_{i-1} 。这说明，以四换二也是不优的，证毕！
获得了这个性质的我非常开心，因为这里没背包了，看起来很可做！
-
1h：好吧我还是不会 dp，写个
\mathcal O(n2^n) 暴力看看性质对不对先。先修修修，补补补，样例 2 死活过不去，基本上每个都是错的。调试的时候发现一些盲点：- 可能是价值为 1 的物品的选择阻碍了价值为 2 的物品的选择，可能还需要考虑以二换一；
- 继上一条，可能以贪心策略选择下来还有一元剩着，这时直接考虑以一换一，是一个更松的界，判断掉一些漏判的。
加上这些之后还是过不掉样例 2。写了个背包辅助判断答案。
幽默的是，写背包时
\mathcal O(n2^n) 代码丢了，于是重写了一个，略调了一下，就通过了样例 2 和 3…… -
1.5h：我觉得心里舒坦多了，上了个厕所，然后把条件写一下：以下两者之一满足即可（注意这个「之一」，等下会考）：
-
- 贪心做法没有花完所有钱，并且
x_i<y_{j+1} ； - 或者
x_{i-1}+x_i<y_{j+1} ； -
-
然后就来到我的高光时刻啦，那就是我在草稿纸上写下：若一个可行的方案中，贪心方法同时买了价值为 1 和 2 的商品，并且花完钱，那么：
（已极力还原考场草稿）
矛盾！
看到上面的警示的，应该已经发现哪里错了。
-
-
2h：化为两种情况：
- 贪心算法把所有代价为 1 的选走。附加一些价值为 2 的，但是钱没花完；
- 贪心算法选走的都是代价为 1 的。
于是画图。
（
i,j,(k) 之间是有限制的，我不想吃💩再列一遍了）以上两部分列柿子各 30min，脑子完全不在线好吧。
吭哧吭哧写完了。
-
2.5h：然后开始调试大样例，诶样例 2 第一个是对的，厉害啊！
比较一下：哦我幽默了。
此时最怕的就是输出比答案大，这说明我少分类了，彻底白给。
还好没有。此时心理：我就算 T3T4 爆蛋也得把你这 T2 爆了！
调调调，过了一组，再测！看错 out 和 ans 了，以为还是我比答案小，还能再调！
扒下一组，我比答案大？对着暴力搞出
9 个不可行的，代码跑出来只有4 个不可行的。剩下
5 个里面：-
\bm{1} 个不属于上述两类里面的任意一个。
结论错了结论错了结论错了结论错了结论错了结论错了结论错了结论错了结论错了结论错了结论错了结论错了结论错了结论错了结论错了结论错了结论错了结论错了结论错了结论错了！！！！！！！！！！！！！！！！！！！！
cnm，cnm，cnm，cnm，cnm，cnm，cnm，cnm，cnm，cnm，cnm，cnm，cnm，cnm，cnm，cnm，cnm，cnm，cnm，cnm！！！！！！！！！！！！！！！！！！！！
复核证明时，愤怒地画下：
:::
-
还有 1h，于是去写了 T4 的
诶我好像没看过跑大样例的正确性！！！警觉查看，发现全错了！！！原来是上界没和
还好还好，挽回一劫。
还有 30min，T3 没有分！！！状压，启动！！！诶我怎么只会
就是没有时间默写追忆，写退役感言了，明年提醒我在代码里补上。
最后得分
我对不起自己。
Failure of dream: NOIP @ Nov. 29, 2025。
你可能会说，这次比赛不是 NOI Plus 吗？何必那么难受？反正你也是业余的。但是究极困难的试卷使得几分的答案差距被无限地放大，在随机挂分的加持下能不能 1= 都成问题。更况且机房人均一人一道题（主要是 T2）的中高分暴力（
如果我 T2 不在那里磕，是不是也没有那么危险？
此后再也和 OI 无缘。此后，我再也不会称自己为一个合格的 OIer。
回首来时的路，我的 OI 生涯到底经历了什么？
- 21 年初生牛犊的
5 分，22 年几近 1= 的200 ； - 23 年幸运的
240 ，以及在 NOIP、THUWC 和 NOIWC 的被吊打经历； - 24 年幸运地参加省选，又被吊打；
- 25 年 CSP 和 NOIP 的双重坠机。
是的，我又失败了。
我多希望这是一场梦，希望我没有进入 OI，希望我不会失败，没有「啊？他怎么那么快就想到解法了？」的叹言。
没有更多想说的了。再见吧。下面时间交给 whk。
Day 3
与同学交流 T2 想法，发现基本对了！！！
复仇 sale 第一天（每天只有 10min 时间写代码！）。
Day 4
复仇 sale 第二天。
Day 5
复仇 sale 第三天。
然后出成绩了。