GDKOI 2025 游记

2021CHD · 2025-12-31 07:20:28 · 生活·游记

没想到 GDKOI 2025 在十二月月底复活了。

Day 0

出发前的上午还在做 Puzzle。

坐中巴去酒店，没有试机。

晚餐没吃围餐，点外卖。

酒店环境好，和 fydj 一个房。

Day 1

:::warning[警告]

以下所说“写完”等可能省略包括但不限于调试代码、自行构造测试数据、在 OJ 测试处提交测试等非主要步骤。

:::

早餐酒店自助餐一般，连个炒饭都没有。

坐中巴去学校，8:30 开始比赛，13:30 结束，时间五个小时，严格 IOI 赛制。

获得了四道题的题面，分别是「填数游戏」、「树上跳跃」、「嵌套区间」和「三元组」。

首先看看题，感觉「填数游戏」比较可做，开始尝试。

这时有人发现 OJ 交不了题，管理人员说正在修复，反正我现在也不着急交题，没管那些。

过了一段时间，我对「填数游戏」发现了 O(M\log\log M) 做法。现在不写何时写，于是我狂暴写代码。

听说 OJ 修好了，不管那么多了，继续写代码。

写完一测样例，完美通过。一交，袜袄，TLE 0 分！

仔细一看，发现连 Subtask 0（样例）都没过！

发现 OJ 有个“在线测试”功能，赶紧拿来测了一下，样例好像贴着一秒的时限飞过去了。

这可不行！意识到我预处理超时了，我决定先把 M 开到 10^6，先拿到分。一交，袜袄，WA 73 分！

莫名其妙把两个性质档冲过去了，不过后来想一想，觉得也有道理，这是应该过的。

总之，我已经发现我愚蠢的错误：这题可以被轻易优化到 O(M)！现在不写何时写，于是我狂暴写代码。

写完一测样例，完美通过。一交，袜袄，AC 100 分！

中间好奇，在提问哪里问了一下提交次数限制，得到回复“目前没有提交次数限制”，回复真快。

开下一题，也就是「树上跳跃」。

观察良久，最终也没有发现性质。暴力也比没分好，于是我狂暴写代码。

首先写了链的性质，写完由于没有样例，直接不测样例。一交，袜袄，WA 15 分！

接下来写 O(N^2) 暴力,写完一测样例，完美通过。一交，袜袄，RE 22 分！

由于这场比赛是严格 IOI 赛制，所以可以拼包，所以我已经在「树上跳跃」获得了 31 分。

还有一个 19 分需要建虚树，感觉性价比偏低，计划后面有时间再来写。

这时我发现比赛时间从原本的 8:30 到 13:30 改成了 9:10 到 14:00，多出来了半个小时！

我赶紧发了一个提问，得到回复“以 OJ 为准”，回复真快。

开下一题，也就是「嵌套区间」。

观察到了指数级暴力做法，感觉打个表可以过两个子任务，但是显然这没有前途，我必须想一个多项式级的做法。

经过一堆题意转换，我终于得到一个 O(n^3) 状态，O(n) 转移的 DP，通过一点前缀和优化，可以做到 O(1) 转移。暴力也比没分好，于是我狂暴写代码。

写完一测样例，完美通过。一交，袜袄，TLE 45 分！

开最后一题，也就是「三元组」。

观察良久，最终也没有发现性质。暴力也比没分好，于是我狂暴写代码。

先写了指数级暴力做法，写完一测样例，完美通过。一交，袜袄，TLE 6 分！

接下来写 Subtask 3 的特殊性质，写完由于没有样例，直接不测样例。一交，袜袄，WA 8 分！

由于这场比赛是严格 IOI 赛制，所以可以拼包，所以我已经在「三元组」获得了 14 分。

居然还有一个多小时？反正做不动了，闲着也是闲着，「树上跳跃」的 19 分不能白丢，于是我狂暴写代码。

写完由于没有样例，直接不测样例。一交，袜袄，WA 34 分！

把链的性质也过了，不过那不重要。

由于这场比赛是严格 IOI 赛制，所以可以拼包，所以我已经在「树上跳跃」获得了 50 分。

最后一点时间试图随机做出任何一道题的任何一档部分分，最终失败了。

:::warning[警告]

以下所说“声称”等可能省略包括但不限于队内交流、推导式子、设计算法流程等非主要步骤。

:::

早餐酒店自助餐一般，连个炒饭都没有。

退房，拿行李，坐中巴去学校，8:30 开始比赛，13:30 结束，时间五个小时，ICPC 赛制。

队名 CHAK takes me fly，队友是 2021cyq 和 qczrz6v4nhp6u。实际上并不是我带飞了队友，而是队友把我带飞了。

怎么电脑在边边。经过协调，成功把电脑换到了中间。

获得了十三道题的题面，分别是「贵校是构造王国吗 V」、「嘟南玻行山」、「回文」、「城市」、「尖尖的」、「【模板】幂函数」、「符字串炒翻」、「基础概率练习题」、「基础卷积练习题」、「幸福指数」、「线性的」、「旅行」和「无限背包」。

怎么没有纸质版题面？哦，原来还在打印。

随机开题，若干分钟后观察到「回文」有人提交，于是三个人开始观察「回文」。一段时间后，2021cyq 声称这题是水题，于是狂暴写代码。

写完一测样例，完美通过。一交，袜袄，AC！

此时排行榜上「基础概率练习题」也有了动静，于是三个人开始观察「基础概率练习题」。一段时间后，qczrz6v4nhp6u 声称这题是水题，于是狂暴写代码。

写完一测样例，完美通过。一交，袜袄，AC！

我们的纸质题面终于到了一份，于是我和 qczrz6v4nhp6u 开始看「城市」，2021cyq 随机开题。

qczrz6v4nhp6u 表示「城市」是难写的数据结构题，我坚持认为「城市」与随机哈希有关，总之，一段时间后，qczrz6v4nhp6u 声称它会做「城市」，于是狂暴写代码。

我发现随机哈希有前途，经过与 qczrz6v4nhp6u 的交涉后 qczrz6v4nhp6u 接受了我的提案，并且成功将常数与代码量同时减小。

中途，我们的纸质题面终于到了第二份。

我继续看题，一段时间后发现「旅行」是个水题，由于 qczrz6v4nhp6u 还在写代码打算先囤着。

此时 2021cyq 去完洗手间以后感觉智商增加了，声称「符字串炒翻」是水题，由于 qczrz6v4nhp6u 还在写代码打算先囤着。

中间什么时候似乎「城市」的时间限制从 2\text{s} 变成 3\text{s} 了，不重要。

我继续看题，一段时间后感觉智商增加了，声称「【模板】幂函数」是水题，排行榜上那么少人过一定是因为歪榜了，由于 qczrz6v4nhp6u 还在写代码打算先囤着。

「城市」写完一测样例，完美通过。一交，袜袄，TLE！

仔细观察发现 qczrz6v4nhp6u 使用 std::cin 读入了 40\text{MB} 的数据还没关同步流，于是赶紧把同步流关上。一交，袜袄，AC！

2021cyq 拿到电脑决定写「符字串炒翻」，于是狂暴写代码。

一段时间后，2021cyq 发现样例过不去，于是开始调试。

此时由于我认为「【模板】幂函数」排行榜上那么少人过一定是因为歪榜了，邀请 qczrz6v4nhp6u 来检查一下我的想法是否正确，突然发现数据范围里 m_1 可以等于 0。由于我的做法只对 m_1>0 有效，我需要对 m_1=0 单独设计算法。而后 qczrz6v4nhp6u 随机开题并常常追忆过去。

一段时间后，2021cyq 发现做法假了，于是破防。我拿到电脑后，决定先写「旅行」。于是我狂暴写代码。

写完一测样例，完美通过。一交，袜袄，WA！

仔细调试，发现代码里有一些降智小错误，于是修正。一交，袜袄，AC！

此时 2021cyq 认为他对「符字串炒翻」有新的想法，于是开始调整他的代码。

此时我对「【模板】幂函数」m_1=0 的情况有了新的见解。

「符字串炒翻」写完一测样例，完美通过。一交，袜袄，WA！

一段时间后，我发现了 2021cyq 做法的漏洞，解决方法就是将一个条件语句删掉一半。一交，袜袄，AC！

此后，2021cyq 与 qczrz6v4nhp6u 随机开题，并且锁定了「幸福指数」。

此时我认为，对于「【模板】幂函数」，“实践就是检验真理的唯一标准”，于是我狂暴写代码。

此时，2021cyq 给出了「幸福指数」的暴力做法，qczrz6v4nhp6u 表示他可以用 FPS 优化。

发现根据实践数据，果然「【模板】幂函数」的正解已经被我发现了，于是我狂暴写代码。

写完一测样例，完美通过。一交，袜袄，AC！

此时，我和 2021cyq 开始观察「贵校是构造王国吗 V」。

由于 qczrz6v4nhp6u 需要「幸福指数」的暴力，于是狂暴写代码。

此时 2021cyq 认为，对于「贵校是构造王国吗 V」，“实践就是检验真理的唯一标准”，于是狂暴写代码。

实践结果不理想，失败了。

一段时间后，qczrz6v4nhp6u 开始写 FPS，写到一半发现复杂度多了个 n，于是 2021cyq 开始帮助 qczrz6v4nhp6u 卡常。

写完一测样例，完美通过。一交，袜袄，TLE！

卡常卡常卡常……

一交，袜袄，TLE！

循环展开循环展开循环展开……

一交，袜袄，AC！

一看榜，发现早就封榜了，封榜时名次 13，现在又多做了一道题，感觉进前十拿金牌还是有希望的！

不过感觉还是多做一道题才保险。

此时 qczrz6v4nhp6u 开始观察「无限背包」并追忆过去。

此时 2021cyq 认为，对于「贵校是构造王国吗 V」，“实践就是检验真理的唯一标准”，于是狂暴写代码。

此时，我认为对于「贵校是构造王国吗 V」，随机化很有前途。

写到一半，qczrz6v4nhp6u 感觉智商增加了，声称「无限背包」是水题，于是狂暴写代码。

此时我们收到了午餐，是汉堡包，我和 2021cyq 开始吃午餐。

薯条和鸡块都没酱，薯条还软了，不开心。

最后时刻，qczrz6v4nhp6u 写完了「无限背包」。

一交，袜袄，WA！

开大数组！

一交，袜袄，WA！

发现缺省源因为给「幸福指数」卡常改坏了，改回来！

一交，袜袄，TOO LATE！

一交，袜袄，TOO LATE！

一交，袜袄，TOO LATE！

最终 7 题（887 分钟罚时）遗憾离场。

qczrz6v4nhp6u 吃午餐。

询问得知「贵校是构造王国吗 V」的正解是随机化，那一段时间 qczrz6v4nhp6u 差点被我刀了。

用微信和朋友发送了豪取银牌的悲报。

下午去一个类似报告厅的地方颁奖。Day 1 也是喜提铜牌。学校团体总分获得第二，反正也不是我贡献的。

接下来有一个老师激情献唱，虽然我不认识那个老师也没听过那首歌。

中间穿插了一些神秘的抽奖环节，反正也没抽到我。

接下来是滚榜环节，主持人的解说非常有意思。

:::success[张力来]

……

……

……

……

……

……

队伍“不想起名字”通过了 L 题，名次 44\to8，进入金牌区！

……

……

……

队伍“猴猴猴”通过了 L 题，名次 33\to8，进入金牌区！

……

队伍“Danielqf takes me fly”通过了 F 题，名次 31\to7，进入金牌区！

……

请以上获得铜牌的队伍颁奖仪式结束后到舞台左侧领取奖牌。

……

队伍“星仔特攻队”通过了 F 题，名次 27\to7，进入金牌区！

……

队伍“想起名字”通过了 A 题，名次 26\to6，进入金牌区！

……

队伍“无敌特工队”通过了 A 题，名次 25\to7，进入金牌区！

……

……

队伍“华附2队”通过了 L 题，名次 22\to6，进入金牌区！

……

队伍“因为太怕WA就全点大模拟了”通过了 A 题，名次 22\to6，进入金牌区！

……（马上就要到我们队了）

队伍“CHAK takes me fly”通过了 J 题，名次 21\to7，进入金牌区！

……（榜 7）

队伍“屈家军超级激动狂喜”通过了 A 题，名次 20\to6，进入金牌区！

……（榜 8）

……（榜 8）

（难道说？）

……（榜 8）

……（榜 8）

队伍“学军一队”通过了 J 题，名次 12\to4，进入金牌区！

……（榜 9）

（难道说！）

……（榜 9）

请以上获得银牌的队伍颁奖仪式结束后到舞台左侧领取奖牌。

（拿到金牌了！）

:::

有意思的是，有个队伍封榜时 0 题，每题封榜后都有提交，最后切了 7 题，冲到了榜 17。

同学校的 UTG 在封榜前就打到榜一了，膜拜。

最终喜提金牌，qczrz6v4nhp6u 终于不会被我刀掉了，之前发给朋友的悲报也被我撤回了。

感觉今年还是有一个好的结局的！

下午坐大巴车回学校，在学校吃晚餐，喜提没有周末。

晚上打 AGC 被打爆了，悲伤。