非常荣幸能够代表中国参加2020年第32届国际信息学奥林匹克竞赛（IOI2020）。受新冠疫情影响，IOI2020首次采用了全部线上比赛的形式，赛制仍为两试6道题目（满分为600），于9月13日至9月23日在主办国新加坡以及世界各国同步举行，共有来自87个国家（地区）的343名选手参赛。

IOI2020中国队四位选手分别是浙江省绍兴第一中学周雨扬和王展鹏、浙江省宁波镇海中学罗煜翔、四川省成都第七中学蒋明润。担任中国队领队的是全国青少年信息学奥林匹克竞赛（NOI）科学委员会副主席、北京航空航天大学赵启阳博士，副领队是NOI科学委员会副主席、北京大学蒋婷婷博士。中国计算机学会（CCF）秘书长、NOl主席杜子德研究员，NOI科学委员会主席、清华大学王宏博士，NOI科学委员会顾问、北京航空航天大学尹宝林教授，NOI科学委员会委员、清华大学韩文弢博士，NOI科学委员会委员、中国人民大学赵鑫博士，NOI科学委员会学生委员、清华大学高闻远同学作为观察员全程参加了本次赛事活动。

本次比赛虽然采取线上赛形式，但是各参赛队四位选手都集中在一起参赛，赛场按主办方标准实行全程、全方位无死角监控。中国队的比赛场地设在中国科学院计算机技术研究所，领队、选手和教练们统一居住在北京骏马国际酒店。

受疫情影响，从组建国家队到参加IOI2020，只有不到一个月时间，因为比赛时间为下午7点至第二天凌晨0点，我们备战过程主要是按国家队教练组要求，适量刷题，参加训练赛，保持状态，调整时差，一般凌晨2点睡觉。

第一个比赛日。我先阅读了比赛的注意事项，再我大致浏览了一下三个题目，对后两题都有了一定的想法，认为可以比较快实现，于是决定先解决第一题plants。

在思考第一题plants中，我注意到如果确定了其中连续k个数的大小关系之后就可以利用给出的信息得到任意连续k个数的大小关系，从而将整个大小关系建立成一个有向图，只需要判断这两个点是否能够互相到达。但是在进一步分析中，我并没有很快得到解决思路，在比赛开始一个小时后，我决定先解决后两个问题。

第二题supertrees，我在比赛开始浏览题目时就发现，前96分只需要一个基环树森林就可以解决。而后4分，当时我认为需要再添加一条边，但由于没有想清楚细节所以决定先拿下96分。

第三题tickets，不难发现每一轮的最小奖励就是最大的一半减去最小的一半。对于每一种颜色，只会使用最大的一部分和最小的一部分，我们要在每种颜色选择k个。注意到最后的约束条件是小的部分和大的部分数量一样多，于是考虑进行凸优化，即对于小的x权值为-x+W，大的x权值为x，要求权值和最大。通过二分W使得小的数量和大的数量一样多。

在基本解决了后两题后，我回到了第一题。出于保守的策略，我决定开始一个一个写子任务拿部分分。很快我注意到其中一个部分分保证每次询问的两个数一定可以比较大小，这表明只需要求出一种可能的顺序。于是我考虑每次从序列中取出一个可能的最大值，这要求它本身比后k-1个大且前面k-1个位置没有这样的数。在取出这个数后，它之前和之后的一些数就可能成为最大值了。如此反复下去就得到了一个顺序。进一步发现这个算法可以判断相邻k个的大小关系。于是利用线段树优化和拓扑排序后通过了2,3,4,5三个子任务。然后我又补了第一个子任务。

然后考虑如何优化建图过程，我发现只需要向左右两边k-1个中最大的连边即可。而最后判断两个点是否能够到达可以通过倍增找到最后一个位置，判断下一步能否走到即可。于是在大约4个小时的时候我解决了这个问题。

最后只剩下第二题的4分。我尝试了一些添加边的方法都没有成功。过了半个小时之后我认真看了一下图，发现我所设想的图会导致出现4条不同的路径。认真分析了一下发现确实是这样，于是最后一个子任务只需要额外判断无解即可。

比赛结束后发现大家果然都AK了。

第二个比赛日，赛前领队提醒了我们题面顺序是英文字典序，和难度无关。注意事项和第一天差距不大，但在看完三道题后发现都不是很直接。看了一段时间第一题后没有什么成果，于是开始看第二题mushrooms。发现可以设置一个阈值，先找到足够多数量的A或B，然后每次统计一段中的A的数量。发现AxAy的查询可以一次确认xy分别是什么。于是计算了一下阈值的大小后获得了约80分。

然后我开始看第三题stations。我花了比较长的时间才理解清楚题面的意思，发现大致只需要一个DFS序。但由于DFS序实际上浪费了一些信息，发现使用奇数层左括号、偶数层右括号的括号序列就能解决这个问题。

于是我又回到了第一题biscuits。我还是选择了逐个子任务的方式解决。很快我就发现了在确定了y后可以在二进制位从高到低贪心填放。于是解决了第1个子任务。对于2、3两个子任务的x都比较小，发现可以将贪心的过程写成搜索的形式，而搜索过程可以保证状态是O(kx)的，于是就解决了这个部分。对于最后两个部分，我尝试了一些方法优化这个搜索，最后发现直接用map进行记忆化搜索即可通过。在考场上我并没有思考这个算法的合理性，赛后发现这个算法的状态是O(k^2 )的。

最后我回到了第二题，发现在后半部分每次查询一段A的个数时，还能顺便求出其中一个是A还是B，从而增长每次查询的长度。使用这个优化后得到了92.62分。最后一个半小时使用了多种方法尝试进一步优化，但并没有改进。

比赛结束后发现大家都获得了292.62左右的分数。

感谢CCF精心组织竞赛，为IOI2020中国队的顺利参赛提供了全新的机器、网络、摄像、场地和后勤等保障；感谢领队老师赵启阳博士和蒋婷婷博士的帮助鼓励和题目翻译；感谢符水波老师对我的悉心照料与指导；感谢陈合力老师和蔺洋老师的关心与指导！