专栏文章

(PKU+NOI)WC 2025 题解

MMoeebius
算法·理论参与者 3已保存评论 2

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
2 条
当前快照
1 份
快照标识符
@miqdze33
此快照首次捕获于
2025/12/04 03:14
3 个月前
此快照最后确认于
2025/12/04 03:14
3 个月前
查看原文
引用框里写的是赛时想法。

PKUWC 2025

d1t1

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

d1t2

赛时会了没调完的题。
考虑 l=1l=1 怎么做。
扫描线，注意到对于深度不同的两个点 p,qp,q，他们的 xx 级祖先必然不同。因此我们对于每个深度 dd 维护一棵虚树，查询就是查询每棵虚树对应深度点数之和。使用 bit 维护即可。这样是 1log 的，同时也给出了一个根号 log 的莫队做法。但是后者常数非常大，跑不动 sub3。
题外话：听说 这个莫队做法回滚后可以做到单根号，有人场上用这个过了。
继续分析性质，如果 ll 不一定为 11，那么我们相当于要去除虚树上“过期”的点。容易想到我们对于每个点，维护其最后一次被覆盖到的时间 tit_i，修改相当于链赋值，查询相当于查询每棵虚树对应深度 ti≥lt_i \ge l 的点的数量。修改可以在每条重链上维护颜色段均摊，查询则是带修二维数点的形式。赛时写的 bit 套 pbds 的红黑树，常数很大而且写挂了。
由于赛时的树剖疑似挂了笔者并不清楚树套树能否通过本题（有人声称过了但是不清楚他是怎么写的）。一个更快的写法是，将带修二维数点转成三维数点然后跑 CDQ。这样复杂度是 O(nlog⁡3n+mlog⁡2n)O(n \log^3 n + m \log^2 n)，常数中等，可以通过。
record

d1t3

deepseek-r1 改编的现代诗
好题要点赞！
本题有一个非常简洁的线性做法。
一个想法是既然题目要求我们求出每个点最早的获胜时间，而这个东西信息量已经有 O(n)O(n) 了那么我们不妨只留下这个看看能不能递推。考虑 sub3，记 fif_i 表示起点是第 ii 个点时的答案（也就是最早的可获胜的时间），gig_i 为第一步允许留在起点时第 ii 个点的答案。首先一定有 fi=min⁡(i,j)∈Egj,gi←fif_i = \min\limits_{(i,j) \in E} g_j, g_i \gets f_i，然后对于 gg，由于 bi=ib_i=i 我们是知道如果第一步要留在 ii 所需时刻的，如果 fi≤aif_i \le a_i 那么第一步留在 ii 肯定不优；否则后手会在 ai+1a_i+1 时刻从 ii 出发，若 fi=ai+1f_i = a_i+1 那么先手必败，否则先手必胜，令 gi←aig_i \gets a_i。
接着考虑 sub4。首先缩点，记 E' 为缩点后形成 DAG 的边集。（一个小细节是 tarjan 求出来的就是反拓扑序，直接用就好了，不需要重新拓扑排序。）修改状态定义，令 fi,gif_i,g_i 为第 ii 个 SCC 内任取一个起点的上述值，由于 SCC 内答案相同所以是良定义的。
特判连通块内只有一个点的情况，此时与 sub3 转移相同。
否则：
  • 一个 SCC 有多个起始时间可选；
  • 一个点可以走回自己，故有 fi=gif_i = g_i。
依然考虑求出 min⁡(i,j)∈E′gj\min\limits_{(i,j) \in E'} g_j，记作 tt。接下来考虑在 SCC 内走的情况。
将 SCC 内所有点的对应时刻写在数轴上，找出第一段连续段 [st,ed][st,ed]（这个 sub 中暴力找的复杂度就是正确的）。如果 st≥tst \ge t 那么走到 SCC 内一定不优；否则，考虑 min⁡(ed,t)\min(ed, t)，不难发现在这个位置先手一定必胜，且在这之前先手的胜负状态是交替的（因为之前二人都不可能走出 SCC），通过奇偶性即可知道第一个先手必胜的时刻是 stst 还是 st+1st+1。
上述代码稍微修改一下即可获得 75 分，究其原因，在每个点的颜色有多个出现时刻的时候，暴力找连续段的复杂度不被 ∣SCCi∣|\text{SCC}_i| 所控制，总复杂度退化为 O(n2)O(n^2)。
考虑使用数据结构维护。求 stst 的复杂度依然正确，但是我们要支持快速找到 stst 后第一个未在 SCC 内出现的颜色。考虑从后往前扫描线，每次只保留每个颜色第一次出现的位置，这样每个颜色只出现一次，暴力找复杂度就对了，相当于要支持任意位置删除，push_front 和从头开始按顺序遍历，使用链表维护即可。一个小细节是看上去要持久化，但是注意到找连续段的过程与维护 ff 和 gg 无关，我们直接在最开始离线一下预处理即可。复杂度 O(n)O(n)。
record

d2t1

有趣（？）的交互题。
考虑维护直径的三个端点 x,y,zx,y,z。初始设置为 1,2,31,2,3。第一轮将 xx 替换为 query(p,y,z) 最大的 pp。第二轮替换 yy，第三轮替换 zz。这样使用了 3n−ϵ3n - \epsilon 次询问，找到了三个点（其中至少包含一条直径）和 dis(x,y)dis(x,y)。
再用 nn 次询问可以知道 dis(x,z)dis(x,z)，即可知道直径。
可以获得 8383 分，使用一些随机化技巧可以再高一些。
还能再给力一点吗？
找到 x,y,zx,y,z 的 3n−ϵ3n - \epsilon 次询问已经很紧了，考虑把最后的 nn 次询问压缩掉。
首先特判掉 n≤6n \le 6 的 corner case。这个阈值是随便取的。
在找到 zz 的同时我们其实获得了所有 query(x,y,i) 的值，记作 fif_i。找到 ff 值最小的点 mnmn，通过一次 in 询问即可知道 mnmn 是否在 xx 到 yy 的路径上。
  • 如果在：
那么 mnmn 必然在 xx 到 zz 或者 yy 到 zz 的路径之一上。再使用一次 in 询问即可知道是哪种情况，这样我们三条链长都知道了。
  • 如果不在：
这意味着 x,yx,y 在树上相邻。由于 n>6n > 6 所以树的直径必然不小于 22，也就是说 zz 一定是直径端点。不难发现此时 x,yx,y 中非直径端点的一者必然在直径上，使用一次 in 询问即可。
record

d2t2

下称单次消耗代价为 11 的为 A 操作，代价为 cc 的为 B 操作。
考虑贪心。不难发现如果我们使用 B 操作时完整地取走了 kk 个球，那么一定不劣。进一步，我们发现：
一定存在一组最优解，满足 B 操作形成了若干个连续段，并且只有不在连续段上或者是连续段末尾的位置可能使用操作 A。
通过这个不难设计一个平方 DP。记 fif_i 表示将 [1,i][1,i] 的盒子内的球全部取完所需代价，两种操作的转移代价都是好算的，拼上 c=1c=1 即可获得 73 分。
进一步考虑什么样的点可能成为连续段末尾。假设 pp 是连续段末尾，那么 apa_p 可能已经被取走了一些球（不妨记此时为 ap′a'_p，并且有 ap′+∑i=p+1i+m−1ai<ka'_p + \sum\limits_{i=p+1}^{i+m-1}a_i < k。
假如我们可以对于每个 ii 求出 ii 后面第一个可能成为连续段末尾的点 jj，就可以从后往前 DP。记 fif_i 表示 [i,n][i,n] 取完的最小代价，分类讨论 jj 开始是继续 B 操作还是断开，两种代价都是好算的。
如何快速求 jj 呢？注意到上述条件相当于 (sumj−sumi−1)mod  k(sum_j-sum_{i-1}) \mod k 在落在一个区间内，使用颜色段均摊做区间覆盖即可。
record

d2t3

你觉得这是题吗。
注意到可以贡献到 [L,R][L,R] 中的数很少，具体地，考虑倒序撤销操作，那么只有 [L/y−B,R/y+B][L/y-B,R/y+B] 中的数可能出现，其中 y∈N+y \in \N^+。
整除分块找到所有可能产生贡献的区间并去重，发现数的数量可以接受，分解出质因数跑 B 次狄利克雷前缀和，发现过了。
分解质因数的时候要对于不超过 10710^7 的数预处理最小质因子。
复杂度不会证，应该也卡不掉。
record

NOIWC

t1

场切。

t2

record

t3

record

评论

共 2 条评论，欢迎与作者交流。

正在加载评论...