NOIP 2025 游记

· · 生活·游记

省流：蓟县

前序

Day -4

赛前：NOIP 周周一的模拟赛，好好发挥！

赛后：T1：挂分。T3：想到了没打完。T4：没打部分分。挂分 155pts。

Day -3

赛前：NOIP 周周二的模拟赛，好好发挥！

赛后：T1：莫名挂分。T2：被卡常。T4：被卡常。挂分 120pts。

Day -2

赛前：NOIP 周周三的模拟赛，好好发挥！

赛后：T2：少讨论。T3：被卡常。挂分 45pts。

Day -1

赛前：NOIP 周周四的模拟赛，好好发挥！

赛后：T2：交错代码？？？挂分 60pts。

正片

Day 0

赛前：NOIP 周周五的模拟赛，好好发...诶？没有模拟赛了。

根据这几天天天挂分，我有强烈的不安感，信心赛直接给我打破防了。

如此状态，如何NOIP?

于是我仔细反思了一系列问题。考场上，决不能犯！打了点板子就睡觉了，这次居然并没有睡不着。

Day 0.5

早早起床来到机房，依然是大部分都来的比我早。坐回座位，打了个卡，放空大脑，等进场。

还有 25min 开考，临走时我问自己：

最近状态不太好，NOIP，会赢吗？

会赢的。

真正的正片

Day 1

T1

显然是比去年简单多了，20min 速通，100pts get~ 感觉自信又回来了！

T2

显然是又失去自信了......

一开始看错题了，结果就整了个 O(n) 做法给我整无语了。

啊啊啊啊，T2 怎么就这么难，我还有救吗？难道我还不如去年吗？难道我退化了吗？不，不能退化，让我仔细想想。

他的贪心策略为什么会错？思考了很久，发现也就只有两种情况：

  1. 剩两块，买了个一块的，还剩一块无处花，但其实可以撤销上一步买个两块的。
  2. 剩两块，买两个一块的，但还不如买某个两块的。

不妨对此计数，先把原价降序排序后把它的价格序列写成一个 12 串，相当于是对形如 12 或 121 且到 1 时恰好剩两块的方案计数，太好了，我们有救了！

先不考虑优化，先暴力 O(n^3)，Nice！样例过了，***怎么第二个样例不过！啊啊啊啊！

$2h$ 后：怎么还不过！烦死了啊！哪错了啊！ $2.5h$ 后：时间仅有 $1h$ 多了，难道我要放弃 T2 了么？ 缓解了一下红温的状态，仔细想了想到底哪里漏算了。稍微思考了一会，合着 12221 也可能不合法啊，所以我刚刚盯着个特殊情况想了 $2.5h$？不是我到底在干嘛？**我真t，我真t，我真t。** 写完过了小数据，惊喜地发现 $O(n^3)$ 可以用范德蒙德卷积优化到 $O(n^2)$，皇天不负有心人啊！QwQ ### T3 只有 $40min$，还有机会吗？ 有的兄弟有的，光速看题，打完 $8pts$ 部分分直接跳。 ### T4 $O(qn^3)$ 一分没有？开什么国际玩笑。被迫用单调队列优化到了 $O(qn^2)$，没想到还能挤出 $25pts$，不过感觉 T4 好像不太难，是错觉么？ **upd：不是我眼瞎没看到B性质啊！！！老天保佑少爷机 $2s$ 跑过 $8\times 10^8$。** # 大结局 总分：$100+100+8+25=233pts

目前不知道会不会挂分。

问了一下周边人，好像不是很多人过 T2，还好还好。

胜利！蓟县！