王修涵IOI2019参赛总结2019-08-13 11:17:04阅读量:13500

 
 

首先,我很荣幸能作为中国国家队的一员参加第31IOI。特别感谢王宏老师、赵启阳老师辛苦地为我们翻译题目,为了确保题面的正确性,他们每天工作到凌晨4点左右,让我们在赛场上能心无旁骛地做题。我们取得的成绩是与他们的辛苦付出分不开的。

巴库是一个非常漂亮、干净的城市,这里的人十分热情好客,唯一美中不足的是风太大了。巴库的名称原意是“风之城”,名副其实。我们去参观了一些博物馆和自然保护区,感受到了这座城市的历史文化底蕴,也欣赏到了优美的风景。

接下来来谈谈我的比赛经历。

第一天的题目是三道传统题。第一题shoes是一道很简单的题,我轻松地解决了这个题。接下来我开始做第二题split和第三题rect,两道题我都只会暴力分,对于正解并没有特别好的思路。我打完split40分暴力和rect72分暴力之后,我认为split的得分空间更大,也可能更简单,于是思考重心便放在了这个题目上。

这个题目的基础是树的部分分,不妨假设abc,我们只需要检查是否存在一个子树的大小在 [a,n-b] [b,n-a] 之间即可。推广到图上,我们需要选出一棵生成树来满足题目条件。所以我开始思考用调整法解决这个问题,即先任意选一个生成树,再用非树边进行调整。这个限制其实有点像树的重心:存在唯一的一个点,其子树大小大于上界,而它的所有儿子的子树大小都小于下界。一开始我认为只有“重心”子树内到子树外的边有用,可以用它们来删除一个子树,提交后WA了。对拍后发现还存在一种情况是“重心”并不在原来的“重心”,需要再加一些特判。

直到比赛结束,我也没有调出来这个题目。其实我要是再深入思考一下,使用DFS树,就可以减少很多细节,我在赛后一小时之后重写了一份代码通过了这个题。

第二天的题目是一道提交答案题,一道造计算机的交互题和一道传统题。我看完后vision walk两个题,认为walk可做一些,就先去做这个题了。我先试图解决起点在左侧,终点在右侧的部分分,我的做法是用数据结构强行维护最短路,这个做法细节挺多的,我对拍拍出来了很多个错误。但是,我过了对拍的时候,提交的代码返回结果仍然是WA。这时候我决定去开另外两个题,拿一些暴力分。之后我返回walk这个题,重写了一种不同的做法,仍然能过对拍,但还是WA掉了。最后三个题分数都不高,名次也比较靠后。

对于我而言,这个成绩并不算很理想。我认为自己的失误在于开题策略出现了一些问题,对题目的难度估计失误,两天的简答题rectvision都没有过掉,而是选择去做较难的题。另外,赛场上有了做法之后就没有再去认真想想split这个题,如果再稍微想想是可以很轻松地过掉的。

值得一提的是,IOI的实时反馈赛制和国内的OI赛制区别很大,策略也相应不同。我认为国家队员应该加强这方面的训练,以更好地适应比赛环境,尽量避免由于策略失误而导致的失分。

另外,我们与国外选手进行了亲切友好的交流,也交换了一些小礼品。我想这次IOI会成为我的一次终生难忘的经历。


最后,感谢中国计算机学会提供这次机会,感谢教练的指导,感谢父母和朋友的关心,感谢所有帮助过我的人,谢谢你们!