钱易IOI2021参赛总结IOI2021参赛总结2021-07-13 13:14:36阅读量:1

 
 

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

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

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

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

第一天比赛前,我还是略微有点紧张,而且还要提前半个小时到场,到场后坐在位置上也十分无聊。比赛开始后,我先阅读了一遍题目,感觉 T2, T3 可能较难,T1 是数据结构,或许相对来说会简单一点。于是我便着手于 T1,但在两个多小时后,我仍未解决这题。因为我之前一直认为这题比较重要必须通过(事实上最后这题通过人数也是最多的),白白浪费了很多时间。此后我绝对先尝试解决 T2T3。我简单的思考了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 给数排序。我先利用取反和加法两种运算迅速设计了一个快速比较的方式,并且可以改造到并行之中。于是我每次将一个序列折半,把第一个评测包解决了。

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

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

最后,感谢 CCF 给我参加这次 IOI 的机会,感谢韩文弢领队,感谢符老师、应老师对我的悉心照料与指导,感谢和我一起交流成长的同学!