PKUWC2025 游记
Lonely_NewYear
·
·
生活·游记
火车上写一大半没保存。
省流：100+100+75+100+73+32=480。
DAY 1
到 12:50 还没调出来试机的交互。
1:00，T1 看了 10min，猜个结论过了。
T2 数据结构小练习，推了半小时，得到 n\log^3+m\log^2 做法，不知道能不能过，反正先写。写了一个小时，交上去只能过 n^2，有点着急。发现是写了个 n^2\log 的预处理，改完过了，此时 3:00。
2h 做 T3。想了半个小时啥也不会，写了个 20 分的 n^2。此时大脑很混乱，半个小时半蒙半推把性质 AB 过了，拼起来 50 分。还剩一个小时，觉得 A 性质其实没啥用，但是想不清楚，于是一直瞎改，最后 5min 把 B 过了，一共 75 分。然后觉得正解也不难，但是没时间想，最后 1min 交了个瞎写的没过。
最后 100+100+75=275。
DAY 2
1:00，T1 一看是交互。半个小时想了个大概，写了一个小时过不了，到 3:00 发现假了，此时获得 0 分。
有点着急，闭眼，静心，先拼暴力。T2 一眼有 n^2 和 c=1，但是半个小时没写对，就先写了个理论 n^2a 的模拟，莫名其妙给除了最后一个包全过了，73 分。T3 直接 dp，狄利克雷前缀和有 32 分，写到 4:00 写过了。
回去看 T1，仔细想，花了 10min 重新设计了个 4n 次操作的做法，写了半小时过了 83 分。最后发现 n 比较大的时候随机化可以避免很多细节，很容易改成 3n 次操作，最后 5min 写过了。
最后 100+73+32=205。
两天基本上都打满了。但是考场上经常思维很混乱，想不清楚，还是不能着急。
题意&考场做法
D1T1
题意
有 a 个有电的，b 个没电的电池，你不知道哪些有电。每次你可以任选两个电池并得知是否都有电，求最少几次操作能保证一定能试出两个都有电的电池。
### 做法
给选的两个电池连边，则要求这两个电池不能都有电，相当于一个独立集。令 $n=a+b$，则是求最少的边数使 $n$ 个点的图没有大小 $=a$ 的独立集。
容易想到均分出 $a-1$ 个完全图，答案是一个 $O(1)$ 的式子。证明略。
## D1T2
### 题意
给定 $n$ 个点的有根树，$m$ 次询问给定 $l,r,x$，求编号在 $l\sim r$ 中的点的 $x$ 级祖先并集大小。
$n\le10^5,m\le10^6$。
### 做法
考虑从小往大不断加入点 $i$，不妨先只考虑某一深度 $d$ 的点。
维护 $f_u$ 表示 $u$ 子树最大的编号，则点 $u$ 会贡献到所有 $l\le f_u,r=i,x=d-dep_u$ 的询问。
加入一个点相当于链覆盖 $f_u$，发现这一段链实际上会贡献到所有 $l\le i,r\ge i,x\le d$ 的询问。
每次链覆盖可能会把之前加入的链覆盖掉，直接取消之前的贡献即可，可以重剖加颜色段均摊证明操作数是 $n\log$ 的。
此时就是一个标准的三维数点，直接 cdq，复杂度 $O(n\log^3+m\log^2)$。
## D1T3
### 题意
给定 $n$ 个点，$m$ 条边的有向有重边无自环的图，点 $u$ 有颜色 $a_u$。图上有一个棋子，A 和 B 要在这个图上博弈。
博弈分 $k$ 轮，A，B 轮流操作，A 先手。第 $i$ 轮指定了一个颜色 $b_i$，此时操作的人要将棋子沿着边至少移动一次走到某个颜色为 $b_i$ 的点，无法操作者输。如果 $k$ 轮全部完成，则最后操作者赢。
A 可以将 $b_i$ 的前 $0\le r<k$ 位删除，博弈轮数变为 $k-r$，仍然 A 先手。求当棋子初始位于每个点上时，A 可以选择的最小的 $r$ 使得 A 必定能获胜，或报告 A 必败。
$n,k\le10^6,m\le2.2\times10^6$。
Subtask 1/2：$n,m,k\le3000$，20分。
Subtask 3：性质 AB，30分。
Subtask 4：性质 B，25分。
Subtask 5：无，25分。
性质 A：边满足 $u<v$。
性质 B：$b_i=i$。
### 做法
记 $f_{u,i}$ 表示点 $u$ 出发，跳过前 $i$ 步是否能赢，转移可以直接 $k$ 轮 bfs，$O((n+m)k)$。
先考虑性质 AB，不妨直接记录 $g_u$ 表示点 $u$ 的答案，即最小的 $i$ 满足 $f_{u,i}=1$。容易发现对于边 $u\to v$，若 $f_{v,i}=1$ 则 $f_{u,i}=1$，所以 $g_u\le g_v$。若 $f_{v,a_v}=0$，则 $f_{u,a_v-1}=1$，此时 $g_u\le a_v-1$。直接倒序递推 $g_u$ 即可。
再考虑性质 B，一样的做法，缩点后一个强连通分量内 $f_{u,i},g_u$ 都完全相同。只是此时若 $f_{v,a_v}=0$，则 $f_{v,a_v-1}=1$。对一个大小 $>1$ 的强连通分量内的所有点按 $a$ 从大到小排序，依次判断是否 $a<g_u$，是则 $g_u=a-1$ 即可。
正解（口胡），把一个强连通分量内所有 $a$ 维护下来，每次先找到最小的 $p$ 满足 $b_p\in a$，再找到最小的 $q>p$ 满足 $b_q\notin a$ 或 $q=g_u$，若 $q-p$ 为奇数则 $g_u=p-1$，否则 $g_u=p$。
## D2T1
### 题意
交互题。有一个 $n$ 个点的无边权树，你要通过如下两种询问得到任意一条直径的两端。
- 给出不同的三个点 $x,y,z$，得到 $d_{x,y}+d_{x,z}+d_{y,z}$，最多询问 $3\times10^5$ 次。
- 给出三个点 $x,y,z$，得到 $x$ 是否在 $y,z$ 路径上，最多询问 $2$ 次。
$n\le10^5$。
### 做法
先任选两个点 $x,y$，询问所有 $(x,y,i)$，记结果最大的为 $z$，可以证明直径要不然一端为 $z$，要不然两端分别为离 $x,z$ 路径最远的点，离 $y,z$ 路径最远的点。
询问所有 $(i,x,z)$ 和 $(i,y,z)$，最小的结果除 $2$ 就是 $d_{x,z}$ 和 $d_{y,z}$。
有个小问题，如果距离为 $1$ 这样求出来结果是 $2$。实际上分别用一次第二种询问即可，但是考场上没想到。直接随机两个点 $x,y$，$n$ 足够大就不会出现这种情况，$n$ 小再换做法。
得到 $d_{x,z},d_{y,z}$ 后根据 $(x,y,z)$ 的询问结果就能求出 $d_{x,y}$。根据 $(i,x,y),(i,x,z),(i,y,z)$ 很容易就能算出 $d_{i,z}$。
根据结论，直接找到最大的 $d_{i,z}$，以及 $(i,x,z)$ 结果最大的点 $a$，$(i,y,z)$ 结果最大的点 $b$，询问 $(a,b,z)$，减去 $d_{a,z}+d_{b,z}$ 就是 $d_{a,b}$。两种结果取大的即可。
## D2T2
### 题意
一个长为 $n$ 的序列上，位置 $i$ 有 $a_i$ 个球，给定 $m,k,c$，有以下两种操作：
- 花 $1$ 代价取走任意一个球。
- 花 $c$ 代价，选择一个长为 $m$ 的区间取走至多 $k$ 个球。
求最小代价取走所有球。
部分分：$n^2$,$c=1$，加起来一共 73 分。
### 做法
记 $f_i$ 表示前 $i$ 个位置取完的最小代价。若不放右端点为 $i$ 的区间，则 $f_i=f_{i-1}+a_i$，否则，这个区间一定从后往前取一段后缀。
记 $j$ 为最后一个没取完的位置，显然下一个区间右端点 $\le j$。若 $<j$，则 $j$ 左侧的部分独立，答案为 $f_{j-1}$，否则下一个区间右端点 $=j$。容易发现这个过程中区间的选择是没有决策的。直接模拟理论复杂度是 $O(n^2a)$，而且随机数据下就过不了，但是过了 73，怎么回事呢。总之很好优化到 $O(n^2)$，$c=1$ 根据这个也很好做。
正解不会。
## D2T3
### 题意
给定 $l,r,b$，你初始有一个变量 $x=1$，有以下三种操作：
- $x=x+1$。
- $x=x-1$，要求 $x>1$。
- 选择一个整数 $k>1$，$x=x\times k$。
对于每个 $l\le i\le r$ 求有多少种 $\le b$ 次操作的方案使得最后 $x=i$。两种方案不同指任意一次操作不同或同为第三种操作但选择的 $k$ 不同。
$l,r\le3\times10^9,r-l\le30000,b\le100$。
部分分：$r\le5\times10^6,b\le40$ 32 分，$l=r,b\le4$ 12 分。
### 做法
记 $f_{i,j}$ 表示 $i$ 次操作得到 $j$ 方案数，转移形式是狄利克雷前缀和，32 分。
$l=r,b\le4$ 时直接倒序搜索即可，但是没时间写。
正解不会。
谢谢观看！