NOI2026 游记

yangjinhua · 2026-07-24 11:27:14 · 生活·游记

反正我没进省队，NOI 随便打。

试机是 WC2026 的题，花费 30 min 获得比赛时分数还多的分数，深刻感觉到自己 WC 的优秀发挥。笔试满分。

猜到了存在交互。Day 1 打开题，发现 pudding 看起来和 cake 是同一个出题人。segment 应该是 dp ，观察到区间结构后直接做就是 O(nmk) 的，空间滚动一下就过了。teleport 50 是简单的，然后观察到决策点的变化至多为 1 ，点分树可以 1log ，2.5h 过了。然后就是这个 pudding ，难以理解。经过 2.5h 的奋斗，仍然不会第二档，44pts 离场。后来评测下取整变成 43pts 了。

Day 2 三个传统题。median 经过短暂的思考后，只会 O(nk\log n) ，感觉要贪，写了几个 fake 了。所以在 1.5h 时决定要换题。kapok 感觉不困难，但是没想到那个 s 的变化可以刻画出来，只会模拟之类的东西，看起来那个值域较小的分可以过掉，思考后发现自己不会不带 log 的做法。感觉没办法了，写了带 log 的，果然只能过 10 ，3000 完全跑不动。彻底感觉自己没救了。写了一下数据随机，没有对。开始做 rainbow ，明显要 dp ，这种东西我至少要会一个多项式做法吧？经过 1h 思考未成功。只能去做 median ，观察到 k>5 这种神秘的分数，提示要提出和 k>5 有关的做法，然后就写了个贪对了。没剩多少时间，去写 rainbow 暴力。我怎么不会 n\le 16 ？不知道自己在干些什么。之前打过一场比赛面对一个 ds 进行了长时间的思考，失败后打暴力发现自己连平方都不会。能不能以后长点脑子，先看看自己能会什么而不是需要会什么？写了 n\le8 ，然后看到链只有 4pts ，肯定简单。尝试推，不会。转向打表，发现 a_n=4a_{n-1}-C_{n-1} ，C_i 是卡特兰数。我不知道为什么，反正对了。然后就结束了。后来评测数据随机过了一个点。

100+100+100+43+100+40+12=495pts ，D 类 Ag。再见。