GDOI 2021 游记

蹭了个名额去参加 $\text{GDOI}$ $\text{tg}$，体验了一下大佬的生活/kk （以下试题皆为 $\text A$ 卷 # DAY -1 不知道要复习什么。本来没有机会来参加省选的，所以省选的算法都没有学。把提高组的主要算法都码了几遍后就没管了。 准备爆零 # DAY 0 来到指定地点报了个告，看看了宿舍。 舍友都还挺好的。有了个好的开头 （顺便写完了作业 # DAY 1 第一天考试开始了。 ### T1 后两题感觉都不太可做，所以先开的 T1。 要使极差变小，必须翻最大和最小的牌，又因为同一张牌被翻两遍是没有意义的，所以相当于保留一个区间不翻转，其他部分翻转。 都想到这一步了，但是考场上脑抽不知道怎么翻转。。。（又是出考场就会系列 于是就打了个贪心，设一个左右端点 $l,r$，翻哪个能使极差缩小就翻哪个，直到不能使极差变小。 本来还想对 $n<5000$ 打一个 $\text{dp}$ 维护每一个区间最大值最小值的，但不会转移，后来就放弃了。 不知道会WA掉多少，只能祈求错解能多拿一点分了。 ### T2 T2 最后开的，因为实在无从下手。 $n,m\leq3$ 和 $0\leq b_{ij}\leq1$ 的部分分想了挺久，做不出来。 打了个 $m=2$ 的部分分就走了（压成一列之后瞎搞就行） ### T3 T3 写了有点自闭。 一开始先写了个暴力，然后开始考虑正解。 把 $u,v$ 和 $v,u$ 都有路径想成了只是有环，然后把操作逆序处理了一同一通 后来发现不只是环可以满足上面的条件啊啊啊。 然后就找不到环和 $f$ 函数的关系了，白给一个多小时qwq。 ### 总结 有个最坑的地方，就是选手牌上写的 $13:30$ 结束然后在比赛还有半个小时结束的时候才告诉说使 $13:00$ 结束（而那时我在写 T3 错解白给。导致没有检查前两题的锅。 如果不会出锅，期望得分： $0$ ~ $60+20+16=46$ ~ $106$ 实际分数： $100+20+0=120$ 第一题满分就离谱！！！样例都没过！！感谢ccf不杀之恩！ 第二题 $m=2$ 部分分码挂了才锅了 $10$ 分！！感谢ccf不杀之恩！ 不过第三题没开文件读写。。。我是zz 这就全是ccf的功劳好吧，我吹爆ccf。 ### 其他 下午有一个所谓的学术交流会。什么鬼啊。。就一堆大学疯狂做宣传，不知道在干什么。 而因为上午严重的白给和时间预判错误，下午有点炸裂。 期望明天安好。 # DAY2 上考场的时候有点忐忑。 ### T1 看了一遍题，感觉 T1 有希望能肝出正解。 然后想啊想啊想啊 想啊想啊想啊 打了暴力QWQ。 这个时候就有点裂了，留了个看似可做的链的部分分。 ### T2 最讨厌这种构造情况的题目了。还是最后开。 没有什么下手点，写了个 $O(n\times n!)$ 的之后就没在看了。 （不过挺涨信心的毕竟有六十多分 加了个 check 剪枝，不知道会不会多一点分。 ### T3 这道题真的不在我能力范围内了。于是开始打暴力。 一开始，我是穷举所有的路径来找受支配集。 然后第二个样例，一个询问 $5$ 分钟。 好耶。 于是重构了 dfs，分别检查 $1$ ~ $n$ 中的每一个点是不是受支配集内的元素。样例二时间复杂度终于可控了。 然后本来要搞 $m=n-1$ 的部分分的，但是由于没有看到题面中的 >从 $1$ 号点出发能到达所有其他点 然后就以为它并不是树。。。。。 （当时还觉得自己思维很严密 然后就没有管这个部分分了。 ### 回头看T1 最后尝试补掉 T1 链的部分分。 硬是想了一个半小时没有碰电脑。 使出浑身解数，回顾了两年学过的所有算法，但是我失败了。。 最后就很烦躁地走出考场了。 ### 总结 除了最后一题的树的部分分，其它能拿的分都拿了，就这样吧。 期望得分： $25+60$ ~ $80+30=115$ ~ $135$ 实际得分： $25+60+30=115$ 正常得分吧，剪枝没啥用。 # 总结 最后分数： $120+115=235$ 省选本来就没资格参加，就当是个经历吧。 见识到了dalao的世界。 还是太弱了啊。。。实力是硬伤 祝好，希望下次能变得更强，考得更好些吧。 ### 发成绩后 虽说成绩远超预期，但是这只是运气问题吧。因为自身马虎挂掉了 $56$ 分。希望这次比赛能当做一个激励和警示吧。 祝好。