NOI 2019 游记

### NOI 2019 游记 #### Day -1 乘车 3 小时，$\mathrm{nn}\rightarrow \mathrm{gz}$。 车上大码一波网络流 24 题，以达成 NOI 前 AC 400 题的远大目标——实际上也没能写多少题嘛。 这回的饭菜虽然不是随便打了，但是其实量也不错嘛。 晚上和 wzj 神犇聊天，他详述了他的竞赛经历，果然神犇就是不一样，从小学就开始学 OI，三进 NOI，长期专注停课学习——总之我没法比就是了。还有 zty 神犇，赛前就已在广州二中训练了很长时间，和其他省的神犇很熟悉，刚刚还跑去和 HN 神犇打麻将——总之我还是没法比就是了。 遂颓。看到群里有一份比赛题，在洛谷上举行，于是赶去参加。浏览完题目，都是经典思维题——原题大作战？遂速码 T1 代码，欲码 T2，然而时间已到。隔壁 cultry 和 1k 已经把三题代码都写好了。用小号提交，居然成绩还不错……不过有个地方因为随手一个 int 少了不少分。NOI 前还犯这种错误，真是可怕。 很晚的时候突然听说明天开幕式限定穿蓝色款比赛服…… #### Day 0 一早赴开幕式。原定 8:45 的合影却因教师大巴晚点而推迟，我们 sz 的教练和选手都没来齐，尬.jpg 开幕式上锅满满，原定的喊口号也没能进行——“全国赛场，高手云集；广西选手，无所畏惧”。 下午练习赛兼笔试。没想到笔试监考这么随便，座位随便坐，我坐在 1k 旁边。开考后比较熟练地写完了 50 题，检查了一遍，便想要提交。没想到提交后分数全部是 0……当时真是吓坏了，仔细看才发现未评测。好吧，我虚了，再打开检查两遍——好像真没什么可检查的了。遂最终提交。 这里记录一些笔试经验：是可以试验的！所以其实有些东西实在不记得也可以当场尝试，就是那个“虚拟控制台”比较危险，一定要记得，按 `Ctrl + Alt + F7` 返回桌面环境。 笔试结束，顺利拿到 100 分。其实笔试差一分也不是很关键，重要的是稳住心态吧。 试机题目——优秀的拆分、随机立方体、I 君的商店——这回必有交互题！糟糕了，WC 的时候 I 君的商店这题我可是爆零的……呃好像 THUSC 的交互题我拿了点分？那也算是有经验了吧。 和 1k 口胡了一下随机立方体的骗分——我遗憾地发现自己只能骗 10 分暴力枚举。随机打表法有一个缺点，要化成模 $998244353$ 意义下的分数，分子分母可能需要微调……这可怎么做啊。 看着瘟疫公司，“毒瘤出题人统治了世界”。再随便写了写优秀的拆分的 95 分哈希水法，用 Arbiter 测了大样例——过了（大样例）就是过了（此题）！行吧，回去了。 晚上是 IOI 国家队选手见面会，越听越觉得，我不能和强省选手比较，他们的模式和我完全不同。国家队选手提供的题目分享？我基本不太懂呢。不过我使了坏，把题目发到新高一群里——他们都在努力用已经学的知识来解。 回宿舍继续努力实现 400 题的目标——结果卡在一道网络流题上了，眼看着还剩八九题，时间却不多了，遂决定，刷红题！秒红题秒到了 399 题，最后在舍友决定关灯后摸黑调网络流——最后发现建图有问题，改正建图后仍 WA 一个点，魔改居然过了……太玄学了。欣喜就寝。 #### Day 1 享受了蒜蓉排骨、蟹黄烧麦、炒粉炒饭后，发现好多模板还没有写过……于是只好在赛场外看代码强记了。听过 Euphoria 和 01 社社歌，走进赛场，熟悉了厕所的位置，回到座位准备比赛开始。 开场浏览一遍题目，嗯，T1 很像去年的归程，T2 T3 应该可以随便骗分，再将题面修改说明同步到纸质试题上，就开始打快读模板！似乎偌大的赛场中都在响着我的键盘声，顿时自信心爆棚——这应该给了旁边选手相当的心理压力吧？（笑） 打完模板，认真想 T1。暴力按时间拆点跑最短路应该是容易想到的方法，怎么感觉每个点还要拆成入点和出点，某些地方还不能直接连边……糟了，越想越复杂了？ 试着提取一下“状态”吧。设 $f[i]$ 为到第 $i$ 趟车的出发时刻，且恰在第 $i$ 趟车的始发站的最小代价；然后用第 $i$ 趟车转移……似乎不错啊。可能需要调整一下状态，改成“第 $i$ 趟车的到达时刻”？ 这个思路可以！于是写了一发暴力 dp，过了大样例，而且最大规模的样例居然能 0.3 s 跑完？这是不是意味着这个做法就可以过了？还是不放心，考虑优化一下吧。 这个是二次函数对称轴右半的函数，似乎有点“单调性”之类的，可能可以像诗人小 G 那题那样用二分单调队列优化？思考了半天，磨细节也磨了好久，终于写完了！ 前 4 个样例都过了，怎么第 5 个样例就爆出负数了呢？爆负……是不是爆 int 了？把所有 int 改成 long long，仍然爆负。遂用一发 `assert` 断言查错法，结果在第 3 个样例处中间结果就爆负了！仔细思考，打印了不少中间结果，终于明白——元素入队时机不对！得再开一个堆，按时间入队。又改了好一会，静态看了代码，应该没问题了吧？然而在第 3 个样例处仍然断言失败。把断言条件从 $>0$ 改成了 $\geq 0$，过了！再看后两个样例，也没问题。可是这个函数值似乎不应该为 0 啊……我灵机一动，如果暴力 dp 的程序也为 0，那就没问题了。用暴力 diff 一下，通过！再 `vim route3.in`，发现这个样例 $A=B=C=0$…… 这时已经过了 $2.5\mathrm{\ h}$，把 T2 T3 的暴力都写了，还剩 $1.5\mathrm{\ h}$。随便挑一题肝一下吧！我想着“T2 放在前面，可能可做一些”，遂肝 T2，结果一点性质都想不出来，根本没有突破口。决定肝 T3。看下一档分是 $n=30$，想着“大力剪枝应该能过”，于是认真写了一发剪枝，花了不少时间，结果连样例都过不去……大力查错，终于发现，此题我的暴力用的是 $0$ 下标，而我习惯用 $1$ 下标，这样就出了错。改正，造数据，却发现 $n=22$ 时就死了。 时间还剩 $20$ 分钟，难道我这最后 $1.5\mathrm{\ h}$ 的努力都白费了吗？极限思考一波——其实可以 dp 啊！简单弄了一个 $\mathrm{O}(n^4)$ 的暴力 dp，还剩 $15$ 分钟，强行冷静，暴码 dp 一枚——居然段错误？仔细看，下标爆负了——好说好说，直接加个 if 判断——过样例！随手造组数据测测吧，改了一下 `test.sh` 的内容，`./test.sh`，`档案 bf.out 和 dp.out 相同`。是否还要按数据分治呢？算了算了，分治的话还要时间整合，而且搞不好一整合就 MLE，现在时间只剩几分钟，还不如检查一下我的 T1 呢。 “比赛结束！”收拾一发，走出赛场，出场看到志愿者在发竞赛快报，都没心情接——因为太热了！把白色外套披在身上遮阳，一路听着神犇讨论“这是 XXX 多项式”，真是慌呢。到食堂就遇到了 HDM 和 HZM，正想汇报比赛情况，wzj 凑了过来，我也不好在神犇面前说什么……总之先吃饭吧。