记WC2021

· · 个人记录

本来是报了个名然后想划水来着,因为原定期末考试时间与WC冲突。(这样的话whk和OI就都有爆零的理由了

结果期末考试提前,本来经常停课的我轻松阿克了。

然后就得回家认真听WC的课,复习了很久whk,打字都有些生疏了。轻松跟着WC进度听一下,第一课堂能听就听,听不了就去第二课堂。最后两天觉得要练习一下,于是开始切题。(其实是觉得IOI、形式化证明什么的我大抵用不到

临考前晚上忽然开始紧张,(其实完全不用紧张,反正也没戏 开始回看各种板子,总觉得明天会用到,一直到很晚才睡。

第二天一早赶到考场,试机的十几分钟打了tarjan、LCT这几个我最近没写过的板子,然后安心等待开题。

密码很简单,很快解压了题目,然后发现题面也极其简洁简单,(以致于感觉今年WC画风比CSP还友好 读懂了T1,看了数据范围极限,滚去看T2;发现T2有表达式,于是去看T3;T3与数论略有关,最近MO讲了点数论,我跃跃欲试,于是先开T3。

T3的20pts一眼就是送的,但是后来觉得循环节有可能达到m^2,于是陷入沉思。推导一下,构建起题目与原斐波那契数列的关系,列出来一个同余方程,可以用exgcd搞一下。然后卡在这里不会了。先把暴力打了再说,虽然复杂度不确定。

T1想了想,发现n=4的时候爆搜稳过。n=8的话要考虑重复经过之类的策略,因为没有节制的爆搜会TLE掉。后面的m=n-1以为是树,于是先打前32pts的dfs。于是光调dfs就用了很久,中途去厕所冷静一下。(上厕所还要排队 回来之后继续各种输出,找到nt错误改过来了。(回溯做反了,淦 关于后面,仔细一想,发现自己nt了,图不一定连通。然后我居然又去推T3,然后否定自己的各种小推论……

时间不觉过半,我又去上了个厕所,开了T2这道题。我先花了一段时间处理表达式,建树。建完之后发现'?'操作之外还有50pts,我先把这些分打了。然后考虑剩下这种运算。(显然枚举取值是不行的 我根据前面想了个转移,复杂度离谱。(而且也没看见n=2的部分分 检查的时候发现RE,发现爆栈了。我就把蠢得要死的传数组的dfs换成了n次传int的,挽回了一些分数。

后面就很无聊了,各种思考做法。T1看错的那32pts好像产生思路了,但是统计答案好难。T2复杂度减不下来。T3也没有进展。最后十几分钟反复检查提交内容,发现我T2改传int的保存失败了,慌乱之中有敲了一遍。把3个题的小样例测了一下,交卷走人了。

出考场之后,发现同机房大家得分情况出奇一致,心情平和了许多。教练在外面等候多时了,给我们拍了照。我和几个同学讨论了一下就回家了。

回家之后感觉很轻松,毕竟一场大比赛已经结束了。但是内心还是有不安——考场的样例太弱,有可能会狂挂分。下午听了一下讲题,反正就记住了T2的表达式可能会胡搞,于是心态炸裂——最有希望的题可能爆了。

第二天混了一早上,下午想下楼活动一下,看到有颁奖于是参加了一下。没想到我挂的分很少,还是因为T1的玄学限制。最后摸到一块铜牌。我挺开心,跟父母,教练和要好的朋友们分享了一下,开心的下楼玩了。WC把我省选排名从近100救到前50,也是意外收获。

仔细回想学竞赛的初衷,本来以高分省一为目标,CSP-S 2020实现了;然后想混块铜牌,没想到WC 2021也实现了……真是一段精彩而值得回味的经历呢。whk爆炸阴霾烟消云散,生活 whk/MO/OI的奋斗还要继续……