WC2021打铁记

本人 SD 选手，线下比赛。 本文中 Day1=2021.2.5 ~~前几天网课什么的就不写了吧~~ # Day0 上午听逻辑学课，认识了许多希腊字母 听完课直接出发去济南 路上听了下午的课，感觉并行算法很有意思，唯一不好的地方在于青岛到济南的高速上有许多隧道，每进一次隧道，就会断网一次，然后聪明的 zoom 就会贴心的为您退出会议并重连，带来了很不好的体验（ 据靠谱统计，路上一共有 18 条隧道 大约在下午四点半抵达济南并入住，接下来就是喜闻乐见的面基环节（ 我和 qyc 定好在酒店碰头，顺利面基，就是场面一度十分尴尬（ 然后和 qyc 去恰了一顿 KFC，聊了一些算法问题~~并疯狂膜拜 qyc~~ ~~qyc 真的又帅又强啊啊啊啊啊啊啊啊~~ 恰完饭去 ssfz 试机，然而门卫不让进，声称不知道这件事（ 在校门口见到了 dyx 和 hws，非常开心 到了七点门卫终于让进了 进去抽签然后试机，先写了一个网络流 ~~没过样例~~ 然后开始调对拍，这时有人发现电脑的 fc 功能炸了，而且整个机房的电脑都有这个问题，感觉很离谱，问了问老师，说是路径问题，前面加上路径就好了 然后发现自己忘了对拍怎么写，调了半小时调出来了对拍代码 这时有人问老师 E 盘能不能存东西，老师说可以存，而且明天不会被删 于是大家开始把毕生绝学丢进 E 盘（ 然后就走了，在群里发现 qyc 好像就试机了很少一段时间就跑了，我们试机结束已经到家了，甚至不知道 E 盘可以放东西（ 晚上回家瞻仰了一下去年的真题，感觉自己啥也不会，又看了看去年 NOIP 的题解，睡了 希望出题人不要整活 # Day1 早上进考场，又一次面基了 qyc，还见到了 Pbri，在外面聊了会天然后进了考场 开题，题目好像没有去年阴间？ ~~反正我还是一题不会~~ 半个小时看完题目，感觉 T2 部分分给的非常足，至少不带问号的部分有一个很显然的 $O(n|E|)$ 模拟做法，有 50 分，于是果断把这部分写掉了，这时大约过了 1.5h 写完这部分紧接着发现含有问号的情况只要在前面做法基础上稍微改一改就有一个 $O(nm^2|E|)$ 的做法（我好像写假了所以是$m^2$），把栈里面的数字改成 vector 统计贡献就好了，用了 0.5h 写完了这部分，大概可以拿 70 分？ 然后对比 T1 和 T3，感觉还是 T3 可做一些，一眼可以看出 $F_p=af_{p-2}+bf_{p-1}$ 然后打了个表发现当模数在 $10^5$ 以内时，循环节不会超过 $5\times 10^5$，然后前 20 分无脑跑一遍就好了，0.5h 写完，挂着对拍 接下来去想 m 是质数，半小时，没想出来（其实想过查表但是没有去写……） 这个时候已经过了 3h 了，再不写 T1 暴力可能会死，于是去写暴力 dfs 然而这个路径可以有重边，dfs 的层数要比 m 大，否则答案是错的，然而这样第二档部分是过不去的，权衡一下我感觉 dfs 层数在 m+4 左右还是比较靠谱的也比较快，于是就写了个玄学的 dfs 上去（ 接下来第二个样例打表，结合第一个样例，发现整个图分成几个块，块内互相能到达，块与块不能。然后就不会了，我并不知道这些块是怎么划分出来的，感觉不好 又看到那个 $m=n-1$ 而且没有环的情况，感觉好像树上点分治可以做？ 然后紧接着发现这个部分分是用来耍猴的，因为图不一定联通，于是没事了 后来 rush 一波 T3 发现假掉了又改了回去，时间差不多到了，检查输入输出，T3 暴力的对拍也没有挂 估分： $[16,32]+[55,70]+20=[91,122]$，运气好能 Ag？ 和 qyc 对了下做法，基本一样，估分也差不多，感觉题目确实比去年简单，不会出现啥也不会的情况 然后直接回了青岛，在车上听讲题，发现 T1T2 都不难，感觉非常自闭 还是自己水平不行吧，T1 显然的做法没有想出来，希望以后能提升下水平 另外省选应该无望了 下午颁奖，到时候更新成绩 upd：出成绩了，T1 加的 trick 可能让我挂了 4 分…… $28+70+20=118$，刚好擦线 Ag ~~不过这和 Cu 也没有什么太大区别啊~~ ~~不过我还是直呼好耶~~