邓明扬IOI2021参赛总结

非常荣幸能够代表中国参加2021年第33届国际信息学奥林匹克竞赛（IOI2021）。受新冠疫情影响，IOI2021仍在线上进行。我和队友们在北京市中关村皇冠假日酒店参加了比赛。荷兰选手 Andy Van Horssen因受困于中国境内，也来到酒店与我们一同竞赛，为比赛增添了难得的国际气息。

赛前我的选手身份遭遇了一些质疑。所幸韩领队和叶老师向组委会说明了情况，并未太多影响到我的心态。

IOI day1前一晚是我的毕业典礼。我的母校是北京市人大附中，恰好位于酒店旁边，于是我得以赶去参加。在夜晚的操场上听着毕业歌，我意识到中学生涯即将走向尾声。IOI也将是我OI旅程的终点。若能夺金自然最好，但无论结果如何，我希望自己能享受比赛。

第一天的竞赛较为坎坷。由于知道题目按名称而非难度排序，我先花十分钟阅读了所有题。第一题 candies 像是数据结构，并非我的强项。第二题 keys 乍读之下毫无头绪。第三题 fountains 是我擅长的构造，于是我又读了遍题，猜想连通则有解。此外，70 的部分分看起来很容易。高分而简单的子任务、毫无意义的无解判断，一切迹象都在暗示：这是一道送分题。于是我毅然将前一小时投入到 fountains 的构造中。我先尝试了删去最上最左点归纳的技巧，然而总有一些情况不对。我又试了几种贪心，一时却无法判断正误。

时间过去一小时有余，我却没有丝毫头绪。我的心态有些慌了。听到队友们敲击代码的声音，我决定再读读前两道题。keys 思考了五分钟仍一筹莫展，于是又转攻 candies。扫描线是常见转化，但计算糖果数量我走了许多弯路。我先猜测最后满的时刻是最后一个大于 c 的后缀，思考了十分钟发现不对。经过一段时间的推理，我意识到每个后缀的答案是总和减去最大前缀较 c 的余量。为验证这一结论我提交了一些暴力，虽写错一次，但终于获得了 3 分。知道结论没错，我便尝试优化。我交了一发线段树却仅得到 8 分，对拍后发现优化错了。我又回到最初的式子，发现写成前缀和后有一项单调，只需二分判定即可。终于，我在两小时左右通过了第一题。

过题之后再看 keys，我竟很快有了思路。我意识到只需将tarjan算法修改一下、记录dfs子树的钥匙和边进行启发式合并即可。我花了约20分钟写完，但由于状态不佳，启发式合并忘了insert钥匙。检查半个多小时后终于发现这个问题并通过了此题。

此时还剩一个多小时，我又转向了开场第一道阅读的 fountains。我发现开始的贪心构造似乎可以归纳证明正确，提交之后却只获得了15分。经过对拍，我发现归纳过程需要以 2 为周期；这意味着贪心方法也需在两种间交替。我稍加调试通过了此题。此时考试还剩约 50 分钟。看到身边的代老师还在提交，我默默地在注释中为他祈祷。我又想到了在 OI 中帮助过我的人们，将他们的名字一个个写到注释里表达感谢。没过多久，比赛就结束了。

出场后发现中国队只有我一人AK。鱼大（虞皓翔）和钱哥（钱易）前期都遭遇了不顺，最后时间不太够用。代老师快如闪电地通过了前两题，但fountains一题写了乱搞未能通过。查看榜单发现金牌线约为200分，中国选手均在前列。

两天之间我们参加了code combat，一个写AI对战的比赛。由于网络问题，鱼大和钱哥用我的电脑查看了题目。我尝试了一些做法，却总调不出来，最终获得了倒数第三。结果虽不理想，却算为正赛攒人品了。

day2前我VP了一下 IOI2019的day2，比较轻松地通过了后两道题，第一题也获得了99分。感觉竞技状态和代码水平比day1前有所提升。

day2我仍然先读了一遍题。dna一题较为简单，意识到结论后我于 14 分钟通过了此题。想了dungeons十余分钟仍无头绪，我决定先做registers。我比较快地意识到了可以通过 a + (-b) 判断两数的大小，而后加上111111得到mask，再将奇偶位置分开即可并行得到两两的min。代码实现看似复杂，但print语句调试非常好用。一个半小时左右我得到了第一部分的分数。我冷静了一下，发现只需稍加修改就能解决第二部分，于是在两小时左右通过了此题，还剩三小时专攻dungeons。我先写了11分暴力用于对拍，而后在思考部分分时，我意识到原题可以将边权按等比数列分类。于是我以 10 为底交了一发获得了89分，将常数除2之后通过了此题。

比赛还余下两个多小时，我再次在注释中感谢了帮助过我的同学们。

最终中国队包揽了前四，我以较大优势获得个人第一名，可以说是意外之喜。赛后我们四个选手一起吃烧烤庆祝这次的好成绩。

我这次IOI的好成绩得益于良好的心态和稳健的考试策略。IOI需要冷静，即使前期不顺利也不应慌张，而要稳扎稳打地做完后续题目。当水平足够高时，一道题的失利并不足以让你掉出金牌线，但若因此心态爆炸则可能直接崩盘。建议未来的选手能平常心参赛，以享受考试为目标，而不要执着于拿前几名或夺冠。这样即使做题不顺，仍有享受比赛、达成目标的机会，而不至于情绪崩溃。至于策略，我制定的方案是在每道题上至少认真思考半小时、至少认真工作一小时：就算某道题目不顺，其他题的时间也要花满。这样，即使有一题发挥失常，其他题仍能得到应有的分数；而夺金往往有一题的容错。未来的国家队训练或可多引入一些易猜错结论题/中等题很多的场次，帮助选手打磨策略以及做好应考的心理准备。

感谢父母和朋友同学们一直以来对我的信任和鼓励，也感谢老师们在赛前为我作的心理辅导工作。领队韩老师、教练叶老师、谷老师，我的三位队友在这次比赛中也给了我很大的帮助。我的发挥和他们是分不开的。

祝我的大学生活顺利，祝以后的选手们加油。

完结撒花owo