GDKOI 2025 寄

· · 生活·游记

？现在还能投稿吗？？

Day -inf

没人和我组 THU。我现在都不知道有几个队过初赛。

Day 1 —— IOI

得分 153。

逆天键盘。按一个键出字符的概率只有 80\% 左右。

使用这种键盘获得 153 分的难度不小于用正常键盘 300+ 的难度。同意的扣 1。

假的。以 @ZnPdCo 为例，严格偏序掉我。

T1 写出了

O(c_1 \cdot M +\sqrt{M} \log^2M + n\log M + c_2 \cdot q)

的逆天复杂度，其中 \zeta 是黎曼 zeta 函数，

c_1 = 1 + \sum_{i=2}^4 \zeta(i), \quad c_2 = 261.

四项有三项是复杂度瓶颈，且无法优化。

这个做法甚至不能稳定通过子任务 1、2，需要拼 inf 次包才能通过。

因为键盘的原因我无法正常思考其它题的正解。

最终得分 100+31+8+14=153。

T2 是我在「心态不爆炸」「键盘不出事」的情况下有 > \varepsilon 的概率做出的题。

T3 建议放 IMOSL C8。

T4 初中生比高中生容易做出来一点。哦哦哦！

这个入的第一反应：

(A + \frac{B^2}{C})(A+C) \ge (A+B)^2.

还有就是高中其实也学二次函数（不是指抛物线）。

Day 2 —— ACM

题目一句话总结：贵校是「不是题的题」王国吗。

先开了三个签到 CDH。欸欸欸我 H 怎么挂了。三题杀三士。

关于 D，yjc 写了一个神奇的猫树分治后开始调试。此时我一眼发现 H 题的弱智错误，修改 O(1) 个字符后 AC。在这之后过了一个 L，yjc 的 D 也调试成功。

？D 被卡常了？原来是 push_up 时「在算法正确性不依赖于维护的数值信息有序的前提下将两个大小不超过 3 的有序数组的各项 merge 拼成一个 vector 后直接 sort 一遍再取前面至多 3 项作为新的有序数组」。

卡常后迅速通过。很快会了 G。关于 G 的正确性：我现在都不知道为什么是对的。

注意到 F 有 O(1) 个队通过，而其他题只有 o(1) 个队通过。

显然有 \text{lcm}(P) = \prod p_i^{\alpha_i} \Rightarrow \min\text{len}(p) = \sum p_i^{\alpha_i}。

如果 m_1 \neq 0，问题是容易的。而 m_1 = 0 就困难了。

随后，yjc 发挥惊人的注意力，注意到 \min\text{len} \le 58！！！！太有水平了！！！！

此后 yjc 又口胡了一个复杂度完全未知但可能正确的算法，然后交给 zdd 写，然后发现不对，随机修改 inf 次后赶在封榜前通过。

A 是构造，我主动提出写 A。用 10min 糊了一个随机化打表。

我编写天才 Convex checker，直接判定是否不存在三个三角形面积之和等于另外一个，Ad-hoc 程度不小于双序列拓展，智力要求不小于 ⑨，0 个队友看懂我在写什么。

选择上厕所缓解心情，并嘱咐队友测试效率如何。

什么叫 A 题的随机化用了七秒钟跑出来了所有答案？
那这个题？
意义是什么？？
和一位？？？？？

我敢赌十年内没有人能发现这题其实是题。

表打出来 56kb，直接通过，也是拿下非 Very Easy 题了。

:::info[第一个 A 掉这题的人 Be like:]

:::

M，J 可能是科技或者哈集幂，我不会捏。BEIK 是 Impossible 吗。最后一直在吃麦当劳。国宴十分甚至九分好吃。

最终过 ACDFGHL，但因为 \sum \text{time} 太大所以 rk12 银牌（罚时并不算多）。打爽了是真的。

据说 A 正解是困难拼构造，不太会。F 题搜出所有解后直接暴力可过，D 是二维 st 表板子？