「SHOI 2019」游记

Day 0

清明节放假。上午打了点没用的板子,觉得一些偏的算法比如 Miller-Rabin 应该不会考,就没复习(Flag)。下午颓颓颓,晚上赶到旅馆,准备考试。

考前有点紧张,感觉 SH 最近 OI 人才辈出,他们都进步很快,我这个小菜鸡就显得有些落后了。不过还是尽自己最大的努力去考吧,没准运气好就进省队了?

睡的很早,并且几乎一躺下去就睡着了。

Day 1

考试日。早上吃了很多东西,所以没带零食进考场。

开题。先花 $30 \text{min}$ 大概看了一下三题。$\text{T}1$ 咋 $k$ 这么小?难道是超级钢琴?$\text{T}2$ 好像 $30$ 分暴力比较 Easy 啊?$\text{T}3$ 是「消失的题面」?出题人毒瘤!

按照自己定的策略,先打了三题的暴力。$\text{T}1$ $60$,$\text{T}2$ $30$。$\text{T}3$ 怎么才算是暴力呢?把 1 开头的点都看了一下,1?+1wa_998244353 的第二个点好难啊不会做,于是水了 $25$ 分走人了。

打完暴力后,考试时间已经过半。看 $\text{T}1$,想了 $2 \text{min}$ 后发现这就是个超级钢琴 + 可持久化 Trie 啊!赶紧码码码,过了 $1\text{h}$ 后写完调完,和暴力拍了几组数据,觉得很稳。$\text{T}2$ 想了 $10 \text{min}$,看了一下部分分:SA + 线段树优化建图有 $80$ 分???考试只剩一个多小时了,有点不敢写,于是就扔了。

最后的 $1\text{h}$ 检查 + 玩 $\text{T}3$,用 gedit 打开 $\text{T}3$ 8.out 的时候,gedit 因为文件太大崩溃了。我可是用 gedit 写代码的啊!尝试手动 kill 掉 gedit 无果,于是重新启动了机器。之后 $\text{T}3$ 的 .out 文件都是用 Guide 打开的。2_p, 2_u, 2_g 都是啥啊?盯着 2_p 看了好久,把相邻两个 p 位置的差列了出来,诶为啥都是偶数啊?这个序列有啥规律啊?为啥越到后面越稀疏啊?想了好久,才发现这个序列是代表每个数是不是素数的…… woc 我没复习 Miller-Rabin 啊!于是打了线性筛水了 $4$ 分走人了。

再看看 2_p,woc p 原来是 prime 啊?好端端的 OI 题咋变成首字母填空了啊?于是想 ug 分别代表什么,考试结束也没想出来。

估分 $100 + 30 + 29 = 159$,感觉要被其他选手虐爆了。

我们是在华二考的,老师告诉我们下午要去科艺听讲题?这都是什么安排啊……

中午吃了吉野家,下午赶过去听讲题。

和邻座同学讨论了一下。同学:$\text{T}2$ 暴力有 $60$ 啊。我:???不是只有 $30$ 吗?感觉自己已经输了。

出榜了,现在只有高中生榜。zjc 大爷 $\text{T}2$ 写的 $80$ 挂成 $50$ 了。zjc:我第三个大样例没过还有 $50$ 啊?有个同学(hwy 巨佬)跟我说他三个大样例都过了啊?我看看他几分啊(翻榜)。诶他怎么挂成 $0$ 分了啊?

讲题。$\text{T}1$ 我写的是标算。$\text{T}2$ $80$ 分就是 SA + 线段树优化建图,并且我似乎能多拿 $10$ 分暴力分?$\text{T}3$ 大大大毒瘤,u 是 $\mu$,g 是原根,标算是部分打表。感觉再这样下去以后都能出强制在线题答了 233。

讲完题后看初中榜。$100 + 40 + 29 = 169$,一分没挂,舒服。

好像所有写了 $\text{T}2$ 的人都挂分了?QAQ 为他们默哀。

晚上回去修整,睡得不晚。

Day 2

凌晨醒了。精神状态不是很好,感觉要翻车了。喝了一碗白粥就去考试了。

开题。$\text{T}1$ 叫皮配?$\text{T}2$, $\text{T}3$ 都是流浪地球系列?$\text{T}1$, $\text{T}3$ 暴力分超少?不算 $\text{T}2$ 只有 $20 + 8$ 的暴力?

先打了 $20 + 45 + 8$ 的暴力分。写到一半发现电脑死机了?我还没存啊?于是叫来监考,重启了一下电脑。写完后考试时间过半,开始想 $\text{T}1$。过了 $10 \text{min}$ 左右推出了 $50$ 分的 dp 式子,就开始写。写到一半的时候又死机了???这是啥破电脑啊?于是监考老师同意给我加时 $5 \text{min}$(才加 $5 \text{min}$ 有啥用啊 QAQ)。重启了电脑重新写,调完后尝试卡常来得到 $80$ 分,但是发现第 $3$ 个样例跑了 $4s$。$5 \times 4(s) = 20s = 10 \times 2(s)$,这是铁定过不了啊。于是 $50$ 分弃疗了。

$\text{T}2$ 想了一下,做了链的部分分,准备做 $n^2$ 的树形 dp。看了下时间发现只剩不到 $1\text{h}$ 了?这个树形 dp 可真难写啊,于是又扔了。最后肉眼检查了好久,到最后没发现一个错误,感觉好虚啊。

最终估分 $50 + 60 + 8 = 118$,被其他选手踩爆了。

出来后和同学聊天。同学:$\text{T}2$ 开几十个线段树就过了啊。我:???[惊恐]。看来自己的知识水平还是不够啊。

中午还是吃完吉野家去听讲课。和 jtl dalao 一起坐。jtl 给我口胡了 $\text{T}2$ std,发现并不是开几十个线段树,而是用一个堆 + 启发式合并的方法。个人感觉这个解法非常妙。我:您是怎么想到的啊?jtl:这个解法很自然啊!我:???jtl:我觉得 SH 应该有两位数的 AC 吧。目瞪口呆,自闭了。

看高中榜。$\text{T}2$ 只有 $2$ 个人做出来,zbw julao 怒 A $\text{T}1$,zjc $\text{T}1$ $90$,$\text{T}3$ $36$ 爆踩了我。zjc:我 $\text{T}3$ 为啥 $52$ 挂成 $36$ 了啊?

听讲题。$\text{T}1$ $50$,$\text{T}2$ $60$ 都是 PPT 里的标准解法。zbw 光荣上台讲 $\text{T}1$,jtl 光荣上台讲 $\text{T}2$,zjc 光荣上台讲 $\text{T}3$,我在台下光荣自闭。

看自己的分数,$50 + 60 + 8 = 118$,一分没挂。

然后就这样挤进队了?只能说自己运气很好吧。

小黄鸭和管神仙也进队了,恭喜恭喜。

zjc 爷 NOIP, Day 1, Day 2 都是 SH $\text{rk} 1$,完虐其他所有选手。

听说 hwy julao $\text{D}1\text{T}2$, $\text{D}2\text{T}2$ 都是正解,但是都写挂了一个小地方,所以被卡了没进队。太惨了 QAQ。

回家的路上分析这次考试。先是觉得没肝 $\text{D}1\text{T}2$, $\text{D}2\text{T}2$ 血亏,但是仔细想想发现求稳的策略其实是最优的。这次省选整体来说还是挺顺利的。

Day 3

滚回学校复习期中考试了 QAQ。