虞皓翔IOI2021参赛总结
很荣幸能代表中国参加由新加坡主办的线上第 33 届国际信息学奥林匹克竞赛。由于新加坡的疫情仍较为严重，因此本次比赛仍然采用线上的形式。今年中国队比赛的场地设在北京中关村皇冠假日酒店的一个会议室，平时就住在酒店的楼上。不得不说 CCF 还是非常用心的，在各方面都做了充分的准备，以让我们专心投入到比赛中。
为了照顾来自世界各地的选手，本次比赛的时间为 18:00 ~ 23:00，对中国选手略有一些影响。因此在一个月前的集训时我们已经开始调整时差，以使我们在考试的时间获得最好的状态。此外，今年除了中国队的四位选手外，还有一名来自荷兰的选手来中国的赛场上参加比赛。我们和领队老师们对其表示欢迎，并进行了深入的交流。
第一天，我首先读了所有的题目，发现第一题 candies 是比较传统的数据结构，第二题 keys 是关于图论的综合题，第三题 parks 则是一道图论的构造。
浏览完毕后，对 candies一题，我并没有很好的思路，于是转而先做 parks。经过观察，我发现题目需要你找一张网格图子图的生成树，使得其对偶图是基环森林。在一个小时左右，我想出了基于对角线构造的方法，写完后交上去发现只有 70 分。然后我利用 assert 的方法，找出程序运行失败的位置，在对应位置构造例子并修改，经过若干次修改后最终在 2 个小时左右通过了 parks 一题。
然后回到 candies，我马上得到了前 4 个子任务的做法，不过直观感觉我觉得这道题的定位应该会比 parks 更简单，于是我继续思考正解。然而我思考了好一会也没想出用线段树等 poly log 复杂度的做法，于是我转而考虑根号做法。我将第 4 个子任务的做法改编成了一个 O(n√(nlog(n) )) 的做法，然而因为常数过大只通过了第 1 个子任务。经过细致地分析，我发现可以通过单调性和均摊分析可以得到 O(n√n) 复杂度的做法，于是便通过了这道题。此时距离比赛结束还有 1 个小时。(事实上这道题的正解是在线段树上二分后缀 max - min，确实是一个比较妙的构造)
此时开始做 keys，首先我迅速过掉了前 3 个包，获得了 37 分。接着尝试考虑标算，但我未能继续获得些许进展。赛后我发现这道题只需要像类似 Borůvka 算法一样暴力启发式合并 O(log n) 轮就可以得解了。
比赛结束后，发现邓明扬和代晨昕分别获得了 300 和 270 的分数，位居榜首；而我和 钱易只有 237 分，不过最终仍然还有并列第 7 名的成绩。第二天比赛前，领队韩文弢老师再次强调了题目按照字典序编排顺序，与难度无关，需要选择合适的策略。
第二天包含两道传统题和一道造计算机题。经过 10 分钟的阅读，我发现第一题是一道简单的贪心题，于是马上通过了此题。
面对数据结构题 dungeons 和造计算题题 registers，我打算先做 registers。题目要求用二进制大整数的位运算和加法来实现取最小值和排序的操作。由于数的个数比较多而数位不多，因此我使用逐位确定的方法完成了取最小值。而对于 n = 2 的部分，可以利用熟知的等式 min(a, b) = (a + b - |a - b|) / 2 来在常数时间内完成。
而对于后面的排序部分，我首先想到的是 O(n log²n) 次比较的排序，发现只能通过 n = 10 的部分。于是尝试对其进行优化，可惜最终没能通过 n = 100 的部分。赛后得知正解是通过大整数位数多的性质来进行并行，这样就只依赖与排序网络的深度而不是比较器个数。于是一些如奇偶排序等的 O(n²) 排序在这方面有体现出了优势。这一点恰恰是我在赛场上没有想到的。
最后回到 dungeons 一题，根据部分分的提示和以往的经验，我知道这是一道和值域倍增有关的题。即将值域以 2 的幂次划分后，在每个段中的部分可以使用数据结构一次性解决。从而我将值域以 2 的次幂划分，每一个部分使用数据结构解决。由于划分的值域段数太多，由于空间原因我只好放弃倍增而转用树链剖分。可惜由于两个 log 分配不均，我的做法在最后的 n = 4 × 10⁵ 被卡常数了。于是我将底数改成了 4，然而由于奇怪的原因并没有能够获得最后的 11 分。
结束后，我发现全场有两个 AK，而且都是中国队的。出乎意料的是，这次 IOI 中国队取得了前所未有的包揽前四的成绩，遗憾的是我没有取得个人最理想的结果。
对于这次 IOI，总体来说和目前国内 OI 在赛制以及风格上还是有较大区别的。在平时的训练中，不仅要培养对 IOI 赛制的适应，更应该加强对这类题型、风格的把握，如这次的赛前训练中 JOISC 和CCO 的题就是比较好的例子。希望中国信息学竞赛的氛围与环境能不断向前，今后取得更辉煌的成绩。
最后，感谢中国计算机学会为我们提供参加 IOI 的宝贵机会，感谢领队韩文弢博士、赵鑫教授的指导，感谢符水波老师对我的照顾与关心，感谢一路上帮助过我的老师和同学们！