Sweetlemon 的博客

Sweetlemon 的博客

NOI 2019 游记

posted on 2019-07-23 05:53:32 | under 游记 |

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 凑了过来,我也不好在神犇面前说什么……总之先吃饭吧。