非常荣幸能够代表中国参加在匈牙利举办的第35届国际信息学奥林匹克竞赛（IOI 2023）。特别感谢领队蒋婷婷老师、副领队韩文弢老师和观察员赵启阳在每场考试的前一天夜里为我们翻译题面，让我们可以直接阅读中文题面，减少了我们比赛的负担。

每个队伍有一个guide，我们的guide是一个中国留学生，十分热情，为我们提供了许多帮助。

这次比赛采用CMS系统进行评测。赛时的提交只能看到每个子任务中第一个得分最低的点的错误信息（即WA,TLE,RE等），无法看到任何一个点的运行时间和空间。赛时也无法看到排行榜相关的信息，需要自行判断题目难度。

比赛第一天，我采用了先读一遍所有题目，然后按照难度顺序做题的策略。第一题closing看起来是一个贪心，但是对依赖关系的处理可能比较复杂；第二题longesttrip是一道交互题，但是感觉即使知道整张图也不是很容易，需要花一些时间构造策略；第三题soccer看起来比较可做，我看了样例之后得到了“一个方案合法当且仅当存在一个中心行和一个中心列，使得它们把平面划分成的四个部分都是阶梯”的错误结论。

于是我认为第三题soccer是这场比赛的签到题，并立即写了一个基于该结论的做法，但交上去只通过了第一个子任务，连n=3的子任务都没有通过。我写了一个暴力进行对拍，发现这个结论是错误的。于是，我决定先去做其它题，此时比赛大约过去了40分钟。

我思考了一会儿第一题后，想到了按照“一对依赖关系中两个数字的大小分类”的做法，并在80分钟时通过了这道题。

通过了第一题后，我开始做第二题，很快得到了“与一个点不相邻的所有点构成完全图”的结论，但是没有什么很好的想法。我又转而去做第三题，此时我想到了判定合法的充要条件，只要在之前错误的结论中加上“行与行之间只有包含关系”就可以了。我实现了这个做法，获得了每个子任务25%的分数，并很快得到了一个O(n^4)的dp，获得了65.5分，此时比赛过去了2小时。接下来我用了很多时间尝试将这个dp优化到O(n^3)，但是没有成功。

比赛时间已经过去了一半，而我第二题longesttrip的得分还是0，于是我赶紧去做第二题。我思考了一会儿，得到了一个O(log n)次操作增加一个点的增量算法，其瓶颈在于对每个点找到当前点集中的一个和它相邻的点。我又想了一会儿，发现可以拿0号点和所有点问一次，这样每个点要么和0相邻，要么构成完全图，那就可以直接增量构造了。我实现了这个算法，在3小时的时候获得了85分。

从85分到100分需要一些常数上的优化，于是接下来我又开始做第三题。我发现可以把O(n^4)的区间dp倒过来，这样就可以O(n^2)求一列的答案，也就是可以O(n^3)。实现了这个做法并获得了77.5分后，我感觉这个做法并没有优化前途，但是利用这个做法进行爬山似乎非常难卡！具体地，我们每次求出一列的答案，然后找到这一列中最优的那一行，再求这一行的答案，然后再求这一行对应的最优的列的答案，这样不断进行下去。如果数据里空格的数量比较多，那么行列之间的关联就会很大，而如果障碍的数量比较多，由于求一行或一列的dp复杂的实际上是空格连续段长度的平方和，那么求一行或一列就会很快。我实现了这个做法，交上去到第七十几个点才有一个点出错，改了一个随机种子就过了。此时比赛还剩1小时。赛后我又交了5遍这个做法，均可以通过。

接下来我开始优化第二题的常数。由于交互库不是adaptive的，可以先对点的编号进行shuffle。经过一些观察，我发现图比较稠密，于是我交换了一些询问的顺序，尽量先进行答案为1就能解决这个点的询问。这个做法在图联通时表现较好，而当图不连通（此时图必定是两个团）时，如果0号点所在的连通块很小，就会超过操作次数限制。于是我加了一个特判：如果新加入的点和0及当前链尾之间均没有边的次数超过了80，就认为0号点和链尾的连边关系一致。这个做法有一定概率不正确，但是我提交之后通过了。于是我在还剩15分钟时通过了所有题目。赛后我也交了5次这个做法，通过了4次。

走出赛场和其他队员交流了一下，第二题大家的做法都是每次把三条链合并成两条，只有我是把图分解成一个星和一个完全图。第三题的正解就是优化那个n^3的dp，不过我没有想到优化方法。

看了看榜，前两题都只通过了10人左右，第三题只有3人通过且均是中国队的。金牌线在180左右，也就是第二场只要拿到180就必定能获得金牌。

我又和队友们交流了一下比赛的策略。其中一位队友的策略是一题一题做，做前面的题时不看后面的题，如果1.5小时还没过再换下一题。我感觉这个策略放在第一天很对，我第一天做题就是一直在题目之间反复横跳，如果不是运气比较好，可能就只能过一道题了。于是我决定day2时使用一题一题做的策略。不过我开场还是会把三题都看一遍。

比赛第二天，我先读一了遍所有题目，第一题beechtree是个推性质题，第二题overtaking看上去像比较套路的数据结构，第三题robot是个题面很长的交互题，感觉不会很容易。

我的感觉上是第二题会比第一题容易一些，但是由于day1的教训，我还是决定先开第一题。首先，一个点的儿子中有重复颜色肯定是不合法的。我在草稿纸上画了一些情况，觉得合法的条件大概是某些子树之间需要满足一些包含关系。我举了几个例子，发现兄弟之间要满足包含关系，父子之间也要满足包含关系。我实现了这个结论，发现不对。于是我又猜测任意两个子树之间都要满足包含关系，交上去发现结论是对的，此时我的写法是O(n^3)的。我先加了一个启发式合并，优化到了O(n^2log n)，获得了66分。接下来我打算写链的部分，这只要加一个记忆化就行了，加上记忆化之后，我意外地直接通过了这题，似乎这样做的复杂度实际上是O(nlog^2 n)的。此时时间过去了80分钟。

接下来去做第二题，很快发现可以把题目抽象成有O(nm)个操作，每次把[l,r]内的数变成r，然后求每个数经过这些操作会变成什么。如果不强制在线的话直接排序后拿线段树维护就行了，但是这个题是强制在线的，所以只能用动态开点线段树维护了。我写完这个做法之后提交，结果由于动态开点线段树的log是log V而不是log n，我被卡常了。于是我只好又想了一个用map维护连续段的方法，在比赛进行到2小时的时候通过了这道题。

接下来有3小时的时间做第三题。由于感觉这题难度比较大，我先用1小时写了所有特殊性质。由于不对无用的位置进行清空也能得到一定分数，而清空无用位置是在找到最短路线的基础上进行的，我决定先不考虑清空无用的位置。我想到了一个每次求出bfs树的一层的做法。每个点需要存它的父亲是哪个，以及它在当前dfs时的状态（未访问、正在访问、已访问），加上最短路线的颜色总共需要13种，可以获得72分。接下来我想到了一个优化，我们不需要记所有点的方向，而是可以通过记录它到起点的距离模3的余数来确定它的父亲，这样就只要10以内的颜色，可以获得77分。然而，这个优化导致必须记录dfs路径上的位置模3的余数，这使得它无法被继续优化。我想了很长时间都无法把它优化到更好，于是写了清空无用的位置的部分，需要使用14以内的颜色，获得了79分。最后我一直在尝试继续优化这个做法，但是都没有成功。
出来之后看了看榜，中国队的4名选手排名均是一位数，算是比较好的成绩。我的队友许庭强比我高1分，获得了第一名，而我是第二名。

总体而言，这次比赛的题目难度偏高，两试都没有特别简单的题，金牌线也是近几年来最低的。如果目标是金牌线，那么只需过掉一道题，写足部分分就够了。但是想要获得比较高的分数的话，由于题目难度偏高，可能对卡题的容错就会比较小。我认为我这次的运气特别好，soccer、longesttrip和beechtree三题都是在不完全会正解的情况下就通过了，这也使得在soccer一题上浪费的很多时间并没有对我的分数造成影响。尽管最后以1分之差没能获得冠军，但我对自己的发挥还是十分满意的。

通过这次比赛的经历，我有几点体会：

1. 是否卡题会对选手的发挥造成极大的影响。如果发现自己开错了题，已经花费了足够长的时间但仍没有把握通过或获得高分，要及时切换到其它题目上。

2. 由于CMS系统提供最小的得分最低的测试点编号，这使得一些随机化做法可以比较容易地测出优劣。而且最终的得分是每个子任务取max之和，没有“我到底该交哪个代码”这种问题，这使得在IOI赛制中使用随机化算法比OI赛制更容易。IOI的时限一般比较宽松，而在当前CNOI环境下，中国选手的代码能力和卡常技巧一般是强于外国选手的，所以在没有其它想法的情况下可以大胆尝试。比赛的时间一定要全部用完，不要中途放弃。

3. IOI的大纲对题目的知识点做了严格的限制，这使得很多算法和数据结构都不会被考察。在平时训练时，要重视思维题、构造题和非传统题。

最后，我要感谢中国计算机学会给我这次机会，感谢父母对我的关心和支持，感谢领队老师和教练对我的帮助。没有你们，就没有我今天取得的成绩。