很荣幸成为中国队的一员参加在线上举办的第32届国际信息学奥林匹克竞赛，感谢CCF和科协组织竞赛，感谢领队老师们帮助鼓励我们和为我们翻译题目，感谢主办方对比赛的重视与支持。

本届IOI因新冠疫情的影响，首次采用了全部线上比赛的形式，未能到新加坡现场参赛，不能说不是一个小小的遗憾。中国队集中的比赛场地设在北京中科院计算所大楼内部，四周都有摄像头，以保证比赛的真实性。比赛时间为北京时间晚上7点~12点，安排到这个时间是为了照顾世界各地的参赛选手，但对我们有一定的影响，毕竟国内的OI比赛一般都在上午进行。我从NOI结束就开始慢慢调整时差，将做题的兴奋点调到考试时间。

第一天比赛，我首先阅读了所有题目，第一遍阅读时没什么思路，不过反复阅读后很快就发现了一些性质。

首先是supertrees一题，稍微分析一下就会发现路径数目为0、1、2分别代表不可达、可以不经过环到达、可以经过一个环到达。这样p≤2的部分分就可以完成了。而路径数目为3则表明需要经过一种不是环的点双到达。然而这种点双一旦出现，就会导致存在两个点之间路径数目为4，题目保证这种情况不会发生。所以路径数目为3时必然无解。这样就完成了这题的所有情况。我按照这个思路，在约45分时通过了这道题。

然后是tickets一题，可以发现对于任何一组合法的解，都可以通过合理分配正负的方式使得权值和为相应的答案。我猜测任何一种合理分配正负的方式都可以对应一组解并尝试证明，发现n是偶数时结论正确，n是奇数时有问题。不过仔细阅读题目就可以发现题目保证n是偶数。这样就可以贪心解决这个问题了。按照这个思路，我在约1小时50分时调出了这道题目。

plants是一道数据结构题。仔细分析题目和数据范围后，我猜测任意距离小于k的植物都可以确定出大小关系，并在这个结论的基础上尝试进行拓扑排序。然后发现可以利用线段树维护找到一棵植物高于与它距离小于k的所有植物，这样就可以进行拓扑排序了，同时也证明了结论的正确性。进行完拓扑排序之后，关键问题在于判断两棵植物是否能确定大小关系，也就是判断在相应的图中一个点是否能到达另外一个点。x可以到达y当且仅当y的位置在某个和x以及拓扑排序在x和y之间的点相关的区间中，所以只需要维护这个区间，而这可以通过倍增维护区间的两个端点做到，不过需要特别注意这是一个环。我在约3小时15分时通过了这道题目，并获得了第一天AK的成绩。

第一天中国队取得了好成绩，全部AK，根据第一天的金牌线232分，第二天只需拿到232就可以确保金牌，所以第二天的策略以保金牌为主的前提下再冲击高分。

第二天比赛，我阅读完所有题目，发现biscuits是一道二进制相关的传统题，mushrooms是交互题，stations是通信题。

stations一题我感觉需要利用dfs序对点进行重标号。普通的先序遍历或者后序遍历都难以仅通过标号确定需要前往的点是否在子树中，所以不可行。不过我很快就发现可以采用奇数层先序，偶数层后序的遍历方式。我按照这个思路在约45分时通过了这道题。

然后是biscuits一题，我稍微分析后发现y合法当且仅当y仅考虑最低的若干个二进制位不能超过某个相应的值。然后再经过一些分析就发现可以用一个状态数是位数平方的数位dp解决。我在约1小时20分时调出了这道题。

做完另外两道题后，我开始认真分析mushrooms一题。首先可以发现询问次数为n-1和n/2的两种做法分别只能获得10分和25分的分数。要获得足够高的分数，应该需要询问次数为根号级别的算法。我很快就发现可以先暴力询问每一种蘑菇的种类直到确定出足够多（根号级别）的A或者足够多的B，然后可以利用这些A或者B做到一次询问确定多个蘑菇中有多少个A。这样已经可以获得高于50分的分数。我先在约1小时45分时实现了这个做法。经过一些进一步的分析之后，我发现其实可以不需要先暴力询问每一种蘑菇的种类，因为在一次询问确定多个蘑菇中有多少个A的过程中可以每次询问额外确定出一个蘑菇的种类。我在约3小时25分时实现了这个做法，该做法可以获得略高于80分的分数。继续分析和计算之后，我发现如果在比较靠前的若干次询问中一次确定两个蘑菇的种类而不是确定多个蘑菇中有多少个A，可以获得92.24分。我在约4小时25分时实现了这个做法，这也是我最后的得分。事实上，我在分析mushrooms一题时已经发现了更优的做法，甚至能做到更优的复杂度。不过我当时分析时可能有一些错误，认为这个做法不够优秀，而且我认为我无法写出这个做法，所以就没有关注这个做法。

这次IOI中国队取得了优秀的成绩，获得团体总分第一。唯一的遗憾是没有获得个人的冠军。

此外，我有一些感受。IOI和国内比赛的赛制有很大的不同，IOI赛制可以在每次提交后得知自己的得分，而国内的OI赛制只能在比赛结束后才能得知自己的得分。IOI的题目类型也和国内有所不同，国内的题目大部分都是传统题，非传统题很少。而这次IOI就出现了两道非传统题：交互题和通信题。即使是传统题也会要求实现一个函数而不是使用标准输入输出。IOI的题目其实不算很难，能进国家队的选手应该都有实力冲击金牌。关键在于注意赛制和题目类型的区别，注意开题顺序，不要出现策略上的失误。