(PKU+NOI)WC 2025 题解

· · 算法·理论

引用框里写的是赛时想法。

PKUWC 2025

d1t1

通过百万富翁一题的结论不难想到，一定是询问若干个团。询问一个大小为 a 的团可以找到至少 a-1 个坏电池。之后 n^3 DP 或者直接推出式子均可通过。（赛时写的 n^3）

场切。

d1t2

赛时会了没调完的题。

考虑 l=1 怎么做。

扫描线，注意到对于深度不同的两个点 p,q，他们的 x 级祖先必然不同。因此我们对于每个深度 d 维护一棵虚树，查询就是查询每棵虚树对应深度点数之和。使用 bit 维护即可。这样是 1log 的，同时也给出了一个根号 log 的莫队做法。但是后者常数非常大，跑不动 sub3。

题外话：听说 这个莫队做法回滚后可以做到单根号，有人场上用这个过了。

继续分析性质，如果 l 不一定为 1，那么我们相当于要去除虚树上“过期”的点。容易想到我们对于每个点，维护其最后一次被覆盖到的时间 t_i，修改相当于链赋值，查询相当于查询每棵虚树对应深度 t_i \ge l 的点的数量。修改可以在每条重链上维护颜色段均摊，查询则是带修二维数点的形式。赛时写的 bit 套 pbds 的红黑树，常数很大而且写挂了。

由于赛时的树剖疑似挂了笔者并不清楚树套树能否通过本题（有人声称过了但是不清楚他是怎么写的）。一个更快的写法是，将带修二维数点转成三维数点然后跑 CDQ。这样复杂度是 O(n \log^3 n + m \log^2 n)，常数中等，可以通过。

record

d1t3

deepseek-r1 改编的现代诗

好题要点赞！

本题有一个非常简洁的线性做法。

一个想法是既然题目要求我们求出每个点最早的获胜时间，而这个东西信息量已经有 O(n) 了那么我们不妨只留下这个看看能不能递推。考虑 sub3，记 f_i 表示起点是第 i 个点时的答案（也就是最早的可获胜的时间），g_i 为第一步允许留在起点时第 i 个点的答案。首先一定有 f_i = \min\limits_{(i,j) \in E} g_j, g_i \gets f_i，然后对于 g，由于 b_i=i 我们是知道如果第一步要留在 i 所需时刻的，如果 f_i \le a_i 那么第一步留在 i 肯定不优；否则后手会在 a_i+1 时刻从 i 出发，若 f_i = a_i+1 那么先手必败，否则先手必胜，令 g_i \gets a_i。

接着考虑 sub4。首先缩点，记 E' 为缩点后形成 DAG 的边集。（一个小细节是 tarjan 求出来的就是反拓扑序，直接用就好了，不需要重新拓扑排序。）修改状态定义，令 f_i,g_i 为第 i 个 SCC 内任取一个起点的上述值，由于 SCC 内答案相同所以是良定义的。

特判连通块内只有一个点的情况，此时与 sub3 转移相同。

否则：

依然考虑求出 \min\limits_{(i,j) \in E'} g_j，记作 t。接下来考虑在 SCC 内走的情况。

将 SCC 内所有点的对应时刻写在数轴上，找出第一段连续段 [st,ed]（这个 sub 中暴力找的复杂度就是正确的）。如果 st \ge t 那么走到 SCC 内一定不优；否则，考虑 \min(ed, t)，不难发现在这个位置先手一定必胜，且在这之前先手的胜负状态是交替的（因为之前二人都不可能走出 SCC），通过奇偶性即可知道第一个先手必胜的时刻是 st 还是 st+1。

上述代码稍微修改一下即可获得 75 分，究其原因，在每个点的颜色有多个出现时刻的时候，暴力找连续段的复杂度不被 |\text{SCC}_i| 所控制，总复杂度退化为 O(n^2)。

考虑使用数据结构维护。求 st 的复杂度依然正确，但是我们要支持快速找到 st 后第一个未在 SCC 内出现的颜色。考虑从后往前扫描线，每次只保留每个颜色第一次出现的位置，这样每个颜色只出现一次，暴力找复杂度就对了，相当于要支持任意位置删除，push_front 和从头开始按顺序遍历，使用链表维护即可。一个小细节是看上去要持久化，但是注意到找连续段的过程与维护 f 和 g 无关，我们直接在最开始离线一下预处理即可。复杂度 O(n)。

record

d2t1

有趣（？）的交互题。

考虑维护直径的三个端点 x,y,z。初始设置为 1,2,3。第一轮将 x 替换为 query(p,y,z) 最大的 p。第二轮替换 y，第三轮替换 z。这样使用了 3n - \epsilon 次询问，找到了三个点（其中至少包含一条直径）和 dis(x,y)。

再用 n 次询问可以知道 dis(x,z)，即可知道直径。

可以获得 83 分，使用一些随机化技巧可以再高一些。

还能再给力一点吗？

找到 x,y,z 的 3n - \epsilon 次询问已经很紧了，考虑把最后的 n 次询问压缩掉。

首先特判掉 n \le 6 的 corner case。这个阈值是随便取的。

在找到 z 的同时我们其实获得了所有 query(x,y,i) 的值，记作 f_i。找到 f 值最小的点 mn，通过一次 in 询问即可知道 mn 是否在 x 到 y 的路径上。

那么 mn 必然在 x 到 z 或者 y 到 z 的路径之一上。再使用一次 in 询问即可知道是哪种情况，这样我们三条链长都知道了。

这意味着 x,y 在树上相邻。由于 n > 6 所以树的直径必然不小于 2，也就是说 z 一定是直径端点。不难发现此时 x,y 中非直径端点的一者必然在直径上，使用一次 in 询问即可。

record

d2t2

下称单次消耗代价为 1 的为 A 操作，代价为 c 的为 B 操作。

考虑贪心。不难发现如果我们使用 B 操作时完整地取走了 k 个球，那么一定不劣。进一步，我们发现：

一定存在一组最优解，满足 B 操作形成了若干个连续段，并且只有不在连续段上或者是连续段末尾的位置可能使用操作 A。

通过这个不难设计一个平方 DP。记 f_i 表示将 [1,i] 的盒子内的球全部取完所需代价，两种操作的转移代价都是好算的，拼上 c=1 即可获得 73 分。

进一步考虑什么样的点可能成为连续段末尾。假设 p 是连续段末尾，那么 a_p 可能已经被取走了一些球（不妨记此时为 a'_p，并且有 a'_p + \sum\limits_{i=p+1}^{i+m-1}a_i < k。

假如我们可以对于每个 i 求出 i 后面第一个可能成为连续段末尾的点 j，就可以从后往前 DP。记 f_i 表示 [i,n] 取完的最小代价，分类讨论 j 开始是继续 B 操作还是断开，两种代价都是好算的。

如何快速求 j 呢？注意到上述条件相当于 (sum_j-sum_{i-1}) \mod k 在落在一个区间内，使用颜色段均摊做区间覆盖即可。

record

d2t3

你觉得这是题吗。

注意到可以贡献到 [L,R] 中的数很少，具体地，考虑倒序撤销操作，那么只有 [L/y-B,R/y+B] 中的数可能出现，其中 y \in \N^+。

整除分块找到所有可能产生贡献的区间并去重，发现数的数量可以接受，分解出质因数跑 B 次狄利克雷前缀和，发现过了。

分解质因数的时候要对于不超过 10^7 的数预处理最小质因子。

复杂度不会证，应该也卡不掉。

record

NOIWC

t1

场切。

t2

record

t3

record