信息学奥赛IOI2021钱易参赛总结

信息学奥赛IOI2021钱易参赛总结：非常荣幸能够代表参加 2021 年第 33 届国际信息学奥林匹克竞赛（IOI2021）。受新冠疫情的持续影响，由新加坡主办的第三十三届国际信息学奥林匹克竞赛（IOI 2021）于 6 月 19 日 - 28 日在世界各地以线上比赛形式同步举行，共有来自 88 个（地区）的 355 名选手参赛。IOI2021 队参赛活动在北京举行。

我们四位同学在前往北京参赛前，已经在镇海中学训练了十来场比赛，我在训练中也调整好了状态。

参加练习赛时，我略微适应了一下 CMS 系统，发现其测评并不会显示每个点的运行时间和程序使用的内存，每个测试包中测到第 一个未通过的点就结束当前测试包的评测。这与我预想的不太一样，但也不构成问题。

练习赛后便是开幕式，开幕式前我了解到参赛的不仅有我们四位同学，还有一位荷兰队的选手因为疫情的影响，也和我们一起参赛。

第 比赛前，我还是略微有点紧张，而且还要提前半个小时到场，到场后坐在位置上也十分无聊。比赛开始后，我先阅读了一遍题目，感觉 T2, T3 可能较难，T1 是数据结构，或许相对来说会简单一点。于是我便着手于 T1，但在两个多小时后，我仍未解决这题。因为我之直认为这题比较重要必须通过（事实上较后这题通过人数也是较多的），白白浪费了很多时间。此后我先尝试解决 T2、T3。我简单的思考了T2之后，决定使用迭代缩点的方法尝试一下。我自己想了一下没能想到可以卡掉这种做法的数据。实现后我发现这一做法通过了绝大多数的点，而且未能通过的点是因为数组开小了，修改后重新提交便成功地通过了此题。

但此时我的分数仍然较低，因此我先迅速写了 T1 的一个部分分。然后我思考了一下 T3，认为这题非常困难，需要花较长时间去构造。此时我想到了一个基于 2-sat 的乱搞做法。于是我就把 T2 的缩点拉了过来迅速实现了一下，略微调参得到了T3 70 分的成绩，在调参提交评测过程中，我抽时间写了 T1 另外一些部分分，较后在 距离比赛结束还有 8 分钟时提交上去并得到了分数。

比赛结束后我依然心有余悸，开局的不利让我心态几乎崩裂，幸好关键的 T2 乱搞做法让我有了生机。在看到上我依然排在并列第 7 的位置后，我松了一口气。在晚上睡觉前我又重新思考了一下 T1，突然发现我考场上 30 分钟左右的时候就得到的一个做法能够很好解决这个问题。但当时我认为这和原问题等价，可事实上这非常简单就能完成，因此我感到了非常地懊悔。

第二天比赛前有两天的休息时间，我也利用这段时间调整好了心态。在得到题目后，我读了一遍题，T1 是一道签到题，T2 应该是一道不是很难的题目，T3 好像是利用压位优化的一道造计算机题。

首先，我迅速地解决了 T1之后来研究 T2。略微观察后，我便发现了题目的关键点：打败一个怪兽加的是怪兽的能力值，于是按 2^k 分组一下然后倍增就可以得到一个 log^2 的做法。但是观察较后一个包，n=400000,q=50000，我发现把 2^k 改成 16^k 就可以了。于是我迅速写了一下代码，但是没能通过。我肉眼查了一下错没能查出来。于是我写了一个对拍，在这一过程中浪费了一定的时间，但较后还是顺利的在 1 个小时 40 分钟的时候通过了这题。

较后剩下一道造计算机的 T3，他让我完成两种任务，一种是取 n 个数的较小值，另一种是给 n 给数排序。我先利用取反和加法两种运算迅速设计了一个比较的方式，并且可以改造到并行之中。于是我每次将一个序列折半，把第 一个评测包解决了。

对于第二个评测包，我首先想到了之前了解到的双调排序，但我对其不是很了解，因此我转而尝试其他做法。在思考一段时间后，我得出了一个改造冒泡排序使之能并行的方法，实现了之后优化了一下常数便通过了此题。

第二天出来后，我和四名同学去吃夜宵。当得知我们四个包揽的时候，我感到十分不可思议，也十分开心。