GDKOI 2025 流水账（不是游记）

· · 生活·游记

GDKOI 24 是 24 年一月办，GDKOI 25 是 25 年十二月办？

——间隔了两年……

对我来说，上次打 GDKOI 还是很久以前的记忆，我们去了东莞一个非常偏僻的地方住上了一个酒店，然后周围没有任何可以玩的地方，任何都没有，荒无人烟，而且距离比赛地点又远，每天要坐车来来回回……

哦，这不是 GDKOI 24 游记，这是 GDKOI 25 游记。

GDKOI 24 给我的记忆并不是很好，我差点打铁，第一天没过签到，第二天最后十分钟过签到终于拿下了铜牌倒数。而且比赛地点附近又没有什么好玩的地方，并且没有带电子设备，只能用酒店的小度玩 https://generals.io/。

所以，这次的目的，就是在两天的比赛中，拿下银牌，守银就好。

你说什么，两天分开颁奖？第一天 IOI 赛制第二天 ICPC 赛制？还有抽奖环节？什么时候 GD 这么有格调了。

Day 1

Day 0 的事情抛开不谈吧，大概就是躺在酒店玩了一个下午的手机，你说面积？太冷了不去不去。

打开电脑，发现说好的是 Ubuntu 24，结果是冰冷的 Windows。原来我们 402 考场因为设·备·原·因只有 Windows 啊，这样这样，也不是不能用，让我打开 vscode 看看。

哇，原来是死机了的电脑呢，让我等个几分钟让它老人家缓缓，然后熟练地更改快捷键和相关设置。接着……Ctrl + W，哇，怎么没有关闭当前标签页呢，怎么打开了智·能·云·课·堂主页面，哇塞，牛逼欸，是哪个神人想出来全局占用这个快捷键的。

让我再写一段 Hello World，哇，怎么 Ctrl + A 也用不了，哦\~原来 A 键很不灵敏呢，真是太棒了呢。让我 F5 运行一下——天哪，竟然是高贵的 MSVC g++，竟然一点都没配置过呢！

遂光速修改配置文件改为 Dev-C++ 的 g++，只能这么做了，我不知道为什么 MSVC g++ 跑不了一点，而且代码补全全是坏的。

欸，怎么没有输出……哦，My God，原来是神人配置呢，这么命令行输出不了一点东西呢，让我写个 freopen 吧……欸，怎么没有效果？

经过我几分钟的缜密分析，我将 freopen 的地址改成了绝对路径，然后就看到了输出的文件。

哇，原来这么厉害，还要写绝对路径。

让我试试关掉同步流吧——

然后就没有输出啦！

至此，我已经完全掌握这台神人 Windows 电脑的相关信息：不能用 Ctrl + W，不能用 A，不能用标准输出，freopen 不能用相对路径，不能关闭同步流……

而且，操作不能过于频繁，否则会死机。

现在距离比赛开始还有五分钟，让我静坐一下吧……

什么，你说 IOI 赛制用的 cms 系统，现在就可以登录。

等等，为什么，我登不上去。

经过一番调查，几位志愿者终于弄明白了，我的网线坏了。

好吧，我不能说我完全掌握了这台神人 Windows 了（至少，在开始之后又坑了我几次，这些是后话）。

遂光速更换到备用机子，进行重复配置，终于在开始之前配好了。备用机子的 A 键是好的欸。

※※※

打开 T1 后我的电脑又死机了几次，然后又遇到了一大堆无法运行的问题，最后我大概在九点左右熟练掌握了调试技巧。

没有关系，反正比赛也延时了半个小时，这不是刚刚好。

T1 呢，剥开外皮之后，大概是一个求方案数的东西。而且是很有性质的若干个数相乘小于等于某个数。我首先就想到了删掉所有 e_i>\log M 的数。然后，就发现我可以考虑对于每个数分解质因子考虑，然后每种质因子最多只有 \log M 个，然后需要分给 \log M 个有上限的背包的状物，第 i 种背包放的个数必须是 prime_i 的倍数。暴力分解质因子当然不可以过，但是可以写个 DP，做到线性。

写完代码，再跟 Windows 系统鏖战一会儿，然后终于在九点二十几时通过了。一遍过。

说句闲话，这个 Dev-C++ 的 gdb 是有概率看不了 STL 容器的内容的，原因不明。

※※※

打开 T2，发现可以直接优化建图 dij 做掉前两种边（父亲和子节点，父亲是容易的，子节点也就是后辈节点，可以直接建另一张一样的图，每次从当前点连出去，这张图上所有边都是免费的，但是跑回主图时要付费 b_v）。发现不考虑第三种边的话可以拿到链的分，再拼一个暴力走第三种边的，交上去发现只过了链的部分。

欸？我哪里写错了吗？不过不要紧，这是暴力，我觉得可以放在最后来调试。

然后对着题目接着想，思考怎么才能刻画同一层的之间连的边……刻画同一层的点的话，就是刻画一个树中的一部分点——虚树！

对于每层的点建出虚树，在虚树上优化建图即可。

写完这部分代码是到了十点半，样例过了之后交上去发现拿到了链的分和一个 c 递增的分。

欸？

不对，难道我也写错了——但是，c 递增的分都拿到了，没道理啊。

我的正解和暴力是分开写的，既然都有地方错了，总不能错得一模一样吧。

那么我写了一个对拍——

拍不出来？！

这真是太诡异了，好在 cms 可以显示 checker 信息，它提示我两种做法都在第 86 行出错了。这么巧？

此时只有一种可能的答案了，我读错题了——

经过我的重新阅读，我发现了：子节点，是儿子节点啊，不是后辈节点。

十一点钟，通过此题。

※※※

打开 T3，看起来非常可怕。

正着计数似乎不是那么好做，考虑计数没有三层嵌套的吧：发现当你有两层嵌套时，最左侧的匹配上的左括号左边不能还有没有匹配的左括号。所以当你打算匹配左侧括号时，若中间已经有一个匹配成功的括号对，就只能连最左边的未匹配左括号。

先口胡了一个 O(n^3)，然后写出来……答案 1 输出了 4？

这种计数 DP 的调试方法是比较经典的，维护一个 vector<vector<int>> dp 数组，用这个数组存具体的方案。最后就可以与暴力比较判断得出自己的计数哪里写错了。

然后发现是我之前口胡错了，每次匹配左侧括号不一定要匹配完，可以只匹配一个。

写完发现自己实际上写的是 O(n^4)，不过也可以随便优化优化，交上去却拿了 O(n^3) 的分。

等等，那我写 O(n^3)，是不是可以过 O(n^2) 的点。

现在是一点钟，还有一个小时。赌吗？

一边是完全没有细想过的 T4（实际上开始时想过，不过总·不·能·随·机·化·能·过·吧），另一边是可能可以多拿二十几分的 T3。

我选择了后者，写了 O(n^3)，然后顺便犯了些糖（包括但不限于滚动数组时有地方忘记滚动了），加上 Windows 电脑过于好用，难以调试。不过还是写完了。

发现根本过不去 O(n^2) 的点。

45 分跑路。

※※※

还有半个小时，用了十分钟拼了 6 分，然后写 dp 做出 8 分……

欸，怎么还是拿不到 8 分？！

经过我的不懈调试，最后也没有能够调出来。

好吧，6 分，总之，肯定有银了吧。

※※※

所以，T4 随机化能拿到 78 分？

拿到了 100+100+45+6=251 分，rk 60，总能有银牌了吧。总共 240 人，按照 123 的获奖比例也有了吧。

肯定守银了。

Day 2

ICPC 赛制，队名是经典的 danielqf takes me fly。但愿真能飞吧。

在飞之前，我们就发现，怎么没有纸质题面。

哦，原来正在打印……

嗯？！

比赛开始后依旧没有拿到纸质题面，遂开始使用电脑读题。三个人滚鼠标看题，A 题看起来是我不擅长的计算几何，B 题没看清，不是那么一眼。C 题……

lnw143 在我连题面还没有读完时就会做了。

等他开始写代码时我才大概弄懂了这题在做什么，就是一个 lca 和并查集。

lnw143 果然还是稳，不愧是金牌✌。7 分钟抢下首杀。

此时我们继续看题，我们一起看的是 I 和 J，I 似乎很像之前某一道 cf 题目，数据范围也很可以分块，但似乎并不好做。而 J 可以枚举每一个喜欢的某一个人来计算贡献，不过当时也只是一眼扫过去也没细想（悲惨）。

然后 fydj 开始想 D，H 题也有人过了，lnw143 开始想 H，纸质题面也终于发了下来。

欸，我在做什么呢？我在想 L。

D 题写完一部分代码之后，lnw 想到了 H 然后过了（26 分钟），然后 D 题在 35 分钟时也写完了，结果 T 飞了。

L 此时有人过了，lnw 接手 L 的工作，并在 55 分钟时写完通过。这段时间内我注意到 G 通过了，于是开始想 G。

G 是一个计数合法的东西的状物，那么经典做法是造一个自动机。但是我造的自动机状态数为 O(n^3) 过不去，经过我乱七八糟的口胡我发现这个自动机似乎不能做到更优。所以我们不能通过自动机去计数这种状态。

那么另一种思路是对每种做法确定一种唯一匹配方法。不难想到一种做法，手模样例正确。此时大概过了 90 分钟，不过电脑仍旧被占用，所以开始想别的题。

我选择了 F（当然是什么都没有想出来）。

在我 129 分钟时写完 G，我们已经在 D 罚了 9 发。仍旧没能通过 D。

然后我想支援一下 D，发现我会了一个小常数做法（二进制分组，那么就需要实现「统计一个矩形内删掉所有为 0 的数之后只剩下一种数」，维护每一行上一个和它不同的数的位置是 O(n^2\log n) 的，然后直接用 st 表维护每一列这个的 \max，查询右边界，判断这个最大值有没有达到左边界即可），刚想给大家分享，lnw143 就给 D 加了一个 shuffle 通过了（捂脸）。

好吧，现在快要到 12 点了。fydj 会了 F，开始写代码。

然后 lnw143 大胆提出 A 随机化做法，于是他和 fydj 开始交叉写题。最后我们因为随机化实现的不够好看，所以跑了大概二十分钟，这段期间 fydj 将 F 通过后我们注意到 A 跑完了，打表之后就通过了。

此后我们一起看 J 和 M（我看 M），M 完全不会，J 大家会了一点集合幂级数可以做到 O(2^nn^3)，不敢写，最后二十分钟由 fydj 和 lnw143 交互写完，但是被卡常了没过。

封榜后过了两题，总共七题，rk 13，银牌回家。还是被带飞了。

然后颁奖告诉我 day1 我只有铜牌，6。是不是因为这次人太少了。

煽情什么的懒得写了，累了，一边去吧。