WC 2025

2025-01-14

T1

有 a 节好电池和 b 节怀电池。你需要找到两节好电池。每次你可以询问两节电池是否是好的。问最优策略下，找到两节好电池最坏情况至少需要几次尝试。

T2

给定一颗有根树，每次询问 (l, r, x)，问 [l, r] 节点的 x 级祖先构成的集合大小。

T3

Alice 和 Bob 在一张有向图上博弈。每个节点有一个颜色 $a_{i}$，有一个颜色串行 $c_{i}$。从 $x$ 节点出发，Alice 和 Bob 轮流操作，第 $i$ 次操作到，从当前节点出发，走若干步，找到某个节点，使得其颜色为 $c_{i}$。如果没有这样的节点，或者 $c$ 不够长，则输。问对于每个出发节点 $x$，最小的 $r$ 使得当颜色串行 $c$ 去掉前 $r$ 项时，Alice 有必胜策略，如果必败输出 -1。

考得很差。好多时间都浪费在 T1 上面了。死活调试不出来。暴力也很难写，最后觉得写一个 $O(2^{n^{2} + n})$ 的试一试，结果发现 $a=3, b=3$ 的答案居然是 6。我一直以为是 7。然后豁然开朗，写了一个 $O(n^3)$ 小常数的，过了。

T2 本来以为会了 $O(n^{1.5} \log n)$，结果假了，只有 24 暴力。

T3 也只会暴力，$O(n^3 / w)$ 的 20 分也没写完。

考得稀烂😭️。再次被 ssz 爆杀。

2025-01-15

T1

交互题，有一棵大小不超过 $10^5$ 的树，通过以下两种询问，找到这颗树的任意两一条之径的两个端点。

1. query(x, y, z)，返回 dis(x, y) + dis(y, z) + dis(x, z)。要求 x, y, z 两两不同。调用次数不能超过 $3 \times 10^5$。
2. in(x, y, z)，返回 x 是否在 y 到 z 的路径上。调用次数不能超过 $2$ 次。

T2

有 n 个桶，第 i 个桶有 $a_{i}$ 个球，你需要通过一下两种操作，将所有桶内的所有球拿出来。

1. 选择一个桶，拿出一个球，代价为 1
2. 选择一个长度不超过 m 的区间，从这个区间的桶中拿出不超过 k 个球，代价为 c。

问将所有球拿出的最小代价和。

T3

从 x = 1 开始。有三种操作：

1. $x \gets x + 1$。
2. 若 $x > 1$，$x \gets x - 1$。
3. 选一个整数 $k > 1$，$x \gets xk$。

问对于 $[l, r]$ 中的每个整数 $y$，经过不超过 $B$ 此操作，从 $x=1$ 操作成 $x=y$ 有多少种操作方案。

T1 不会做，写了一个多小时只会 7n 的做法，其中 4n 用于找一条边的两个端点，2n 用于寻找直径的一个端点以及紧挨这这个端点的一个顶点（唯一），n 寻找直径另一个端点。好像没什么思路优化了。

开 T2，一下子也没有什么思路，感觉可能可以强制从左往右拿球，但又不确定对不对。又开 T3，一看就不太会的样子，先写一个很显然的 24pts $O(r\log r B)$ 暴力。试图卡过 5e6 的点，但是卡不动。有尝试写了写 B <= 4，l=r 的点，结果写半个多小时也写不出来。感觉和整除相关的题目也不是我能做的。于是放弃。

又回来看 T2，尝试写了 $a_{i} \le 100$，$n \le 500$ 的 subtask，令 $f(i,j)$ 表示 $[0, i)$ 拿完，$a_{i}$ 还剩 $j$ 个，$[j + 1, n)$ 没动的最小代价。然后又写了 $c=1$ 的 subtask，比较简单的贪心。发现这个 dp 虽然和值域相关，但是似乎状态数不多，于是把值域那维换成 map，而且转移也只用考虑当前在 $i$ 为左端点使用了 $\left\lfloor\frac{j}{k}\right\rfloor$ 个操作 2，和使用了 $\left\lceil\frac{j}{k}\right\rceil$ 个操作 2 的情况。居然拿了 70 多分！太振奋了！！！

PKUWC 四个小时真的好紧张啊，三道题，一道都不会，同时处理三道题就会手忙脚乱。如果能赶快把 T1 做出来，那确实就轻松很多。

szz 会 T1，太强大，orz。

唉，如此成绩如何省选。

2025-01-16

上午去了鲁迅纪念馆。中午吃了绍兴菜，品鉴绍兴黄酒。

带图画的山海经（神似奶龙的刑天）：

回来时在酒店对面的儿童乐园玩（特别好玩），面积了群友 0x3b800001。

2025-01-17

伙食比 PKUWC 好多了。

和不知名选手和不知名教师打了乒乓球。结果一天就战损两个乒乓球。

找到传奇特级自习室：

可惜这个办公室空调似乎有点问题，晚上巨冷无比。

杜子德单口相声。

2025-01-18

不能再颓废了！要认真听讲！

掀起了一股找讲师要签名的热潮。

中午和不知名工作人员打乒乓球，似乎还是说是省队，被虐爆了。

2025-01-19

上午去第二课堂听网络流，下午听思维题。第一课堂听不懂。

乒乓球晚上到了，又可以打球耶。

晚上再战 WC24 代码堵塞，写一个多小时，一百多行，简单背包。被题解区二十几行代码震惊到了。

2025-01-20 (考试日)

睡的不是很好啊，最近睡觉总是起夜。于是在试机的时候又睡了近一个小时。

T1 做的比较顺利，很快就有思路，写出来结果 selfeval 只有 65pts，仔细思考发现没有考虑很多个大小 n/2 的优质猫粮的情况，改一改就过 selfeval 了。但是我还不知道有没有什么其他情况没有考虑到，本打算写个暴力对拍，但感觉暴力机难写，于是选择相信 selfeval。

T2 很没思路，要输出不超过 m 个方案，就很诡异。令 f(i,j,k) 表示考虑前 i 个数， xor 和为 j，用 k 次加法，的方案数。后又发觉不必记录方案数，改成 f(i,j) 表示前 i 个数，xor 和为 j，最小加法使用次数，找方案直接搜索，得到 28pts，又想了一个来小时感觉没啥思路，加法和异或放到一起太神秘。

T3 反而还容易一点，很快写出 $O(n^2)$ dp，结果过不了大样例，仔细分析，离散化应该要把 $a_{i}$ 和 $a_{i}-1$ 都包含进去，然后就得到 40pts。发现 dp 数组更新比较简单，用数据结构维护。最后在比赛还剩 20min 的时候调试完 $O(n\log^2 n)$ 的版本，只有 85pts，双 log 是因为二分线段树。尝试改成单 log 线段树二分，结果发现不会写从特定端点开始的线段树二分：

// 摘自 atcoder library
    template <bool (*g)(S)> int max_right(int l) {
        return max_right(l, [](S x) { return g(x); });
    }
    template <class G> int max_right(int l, G g) {
        assert(0 <= l && l <= _n);
        assert(g(e()));
        if (l == _n) return _n;
        l += size;
        for (int i = log; i >= 1; i--) push(l >> i);
        S sm = e();
        do {
            while (l % 2 == 0) l >>= 1;
            if (!g(op(sm, d[l]))) {
                while (l < size) {
                    push(l);
                    l = (2 * l);
                    if (g(op(sm, d[l]))) {
                        sm = op(sm, d[l]);
                        l++;
                    }
                }
                return l - size;
            }
            sm = op(sm, d[l]);
            l++;
        } while ((l & -l) != l);
        return _n;
    }

总分 100 + 28 + 85 = 213，好多人比我高啊。唉，如此成绩如何省选。

和 xzc 打 40min 左右乒乓球，战损两球，狗屎天花板设计。

晚上讲题人 13 min 速通讲题。然后文艺汇演，挺好玩的，甚至还有 cosplay 大佬，可惜我没有参加表演的勇气。

文艺汇演

极大概率是最后一次参加冬令营了，好像也看不到那么远，只希望能过省选。

晚上还有 codeforces，没有打，jiangly 上 4000，太强大。jmr 上 grandmaster，被初三后生远远超越了。

洛谷修复了能看全网犇犇的 bug，猜猜犇寿命才两周就暴毙，犇站也挂掉了。

2025-01-21

上午是讲随机相关的科普性讲座，听了一半跑路了。

下午又听动态图连通性问题，说实话黄洛天讲得挺好的，但是有点困，后头掉线了就跑路了。同时集齐了 IOI2024 国家队签名（原谅我不会做图片）。

晚上和何钒佑玩，打了乒乓球。

探访神秘 KTV，不敢去唱歌，内向自闭 OIer。

又玩了 crazy games 小游戏。想到这些金牌的选手冬令营结束就要离我们远去了，就很伤感。

2025-01-22

上午讲稀疏图上更快单源最短路算法，大概是 TCS 相关内容，没想去听，颓颓颓。下午讲仿真退火和概率编程，比较有意思。

今天同时也是国家队选拔第二试，何钒佑这场考试后竟是第六！问题来了，他没有准备论文，而前六名必须要答辩。他来之前积分排名是第九，本以为全无进前六的可能。于是从当天下午开始狂暴赶论文。

我晚上去陪他，同时打了一场 cf。是 Round 1000，div 2，阳间场，手速有点慢，被 D 硬控了好久，F 题都没来得及看，好在还是上了 Master。而何钒佑赶论文和 PPT 赶到凌晨三点过，还没来得及准备英文自我介绍。

2025-01-23

最后一天，上午是国家队答辩。

提问特别有意思：

刘恒熙

杜：呃，我们的同学把手机带进了考场，有同学遗憾地被取消了资格，就没有得到牌牌。有人说：「领队为什么不提醒我们的选手，别把手机带进去」。你怎么看这个事情？

刘：作为选手，如果我能有幸被选入国家队，我在之后一定会注意这个问题。我认为选手也是有一定的责任的，就是比赛，它一定是不能带进手机的。然后领队的话，之后也应该要最好要做好提醒。感谢杜主席的提问。

杜：我现在告诉你，你选上还是选不上，我们以后都不会提醒你，因为规则已经定在那儿了。就像是马路上的红绿灯，警察不提醒你你就闯红灯，你觉得可以吗？人家就按规则办了，那你怎么办？

刘：呃，那只能在之后更加注意。

杜：一定要按规则办，不需要提醒。

刘：好感谢杜主席的教导。

杜：哈哈哈哈。

刘海峰

杜：海峰你好。我们中国国家队队员呢，是经过层层选拔的，都非常优秀。呃，不光是四个同学，即使去八个同学，往往我们都可以拿足四个或所有的金牌（没听清？）。去年是因为规则问题，我们吃了一点亏。好了，我假如啊，假如你被选入这个中国国家队，今天到玻利维亚去，代表中国去参加 IOI。我呢，是你的指导教师，我也觉得挺荣幸的，我就打算在现场，拿个摄像机，向全世界来直播的这个行为，啊。刘海峰已经顺利到达了玻利维亚首都，他即将要比赛，啊这个海峰是我培养的众多学生之一……还有更多。我一直在直播。你觉得我的这种行为好吗？

刘：我觉得这种行为是不对的。首先感谢杜老师的提问。我觉得这种行为是没那么恰当的。因为，首先我们学信息学是因为热爱而学，而不是……我觉得作为一个教信息学的教练，他应该……应该想方设法如何去培养学生，而不是把心思，花在如何蹭流量方面。

杜：海峰，我感谢你当着这么多人的面，批评你的老师。经过你的批评，我决定修改我的想法，我不再直播了，谢谢你。

附参考文献：

被罚，我认为是好事。我发现现在我们（当然包括我自己）有点骄傲了，有点飘飘然了，以为夺得金牌就意味着中国教育先进，科研创新力强，产业也打压外国！这哪儿和哪儿呢？这只是孩子们的智力游戏而已，不要拔那幺高。而中学也借此大做文章，吹牛，为招生做铺垫。这不，这次居然有随队老师现场直播，意思是他们的学校盛产金牌！这样做，真是全球第一！

后头懒得转录了，AI 识别准确度太低。

IOI25 中国国家队答辩问答精选集

最终国家队也没有什么悬念的 1234，恭喜。

下午颁奖仪式，szz 金牌太厉害。拜谢。然后冬令营就结束了。

hfy、xzc 这些选手下学期就去北大读预科了，就此远离我们了，有些伤感。

希望能过省选。