PKUWC 2025 邮寄
流水行船CCD
·
·
生活·游记
没带电脑，考后回忆，部分分可能会有问题，已经记不清楚了。
Day 0
中午的飞机，飞的杭州萧山，由于种种特殊的原因，我们这届只有三个人去了 pku。
下午 3 点左右到了酒店，pku 就是好，订的大床房。直接打游戏打到饭点，去外面一个公园里的餐厅吃了一顿绍兴特色菜（其实也不算），有点小贵，绍兴明显比 CQ 冷，不带帽子有点受不了。
晚上被 lyj 督促早睡。
day 1
上午开幕式没啥好说的，听一堆领导发言，基本全在灌水。
食堂好评，免费餐券甚至有虾，比某 BS 好。
回酒店午休的时候在 WC 签名墙前面偷拍了一张，试图伪装集训对耶。
下午开考。
T1 考场的时候一直在想两两配对的思路，因为只有 32 次的提交限制，不是很敢交，一直 WA，最后过了 1.5h 打了个 A>B+1 的性质和 A = 2 的性质，只有 10 分，暴力都写不出来，太失败了。完全没有往鸽巢原理方面想。以后遇到这种题还是用平均思想，感性来说越平均次数越少，譬如 APIO2016 最大差分，搞笑的是 APIO 这道题在考前模拟赛出现的时候我还场切了。
看 T2，这不 SB 题吗，询问离线，K 从小到大枚举，在 BFN 区间上相邻点的 K 级祖先就会逐渐相同，可以看作合并，启发式合并就可以维护出每一个点的 K 级祖先，查询就变成了一个待修区间颜色种类数，修改 O(n \log_2 N) 个，查询 O(q) 个，考场直接树套树，O(n \log_2^3 n + q \log_2^2 n) 直接寄掉，成功 TLE 58 分。
T3 打暴力，10 分，主要是时间花了太多在 T1 上了，完全没有思考时间。
和同学一起在酒店吃晚饭，真的贵，一个人 70 rmb，joker lyq 饭钱付错人，退款还退了 20 min。
czx 没来成为最大遗憾，晚上 play 都没人陪。
# Day2
讲座又是 AI，听过 114514 遍了，但是那个泛化模型确实有点意思，可以抓没训练过的东西，挂衣服，只是速度有点慢。
午饭鸡排好评。
根据往年经验，开局直接看 T2 贪心错误性显然，考虑 DP。设 $f_{i,j}$ 表示前 $i$ 个盒子，最后一个盒子剩下 $j$ 个球，最小操作数。首先发现如果在区间中整体取，一定是从左往右依次取，取完一个再去取下一个，这就好转移了，分两种情况：$i$ 单独取，不影响后面；$i$ 取完后利用区间取操作将后面的盒子也取一些，这个二分算出影响区间直接转移就行。感性发现有效的 $j$ 就几个，开 unordered_map 存 DP 数组，理论 $O(NV \log_2 N)$，实际表现为 $O(N^2)$, 79 拿下。
T1 交互一点思路都没有（不是 pku 什么时候开始考交互了），但是发现对于 $(i,j)$ 若 $dis(i,j) > 2$，那么 $dis(i,j) = \min \{query(i,j,k)\}$，$dis(i,j)=2$ 的情况用另一种函数特判一下就可以做到 $O(N^3)$，10 分，正解应该是找最远点的做法，不是很会。
T3 暴力做法显然，bitset 优化 $O(\frac{N^3}{w})$ 居然过不了 2000，怒！拼上一个 $l=r,n \le 4$ 的搜索，遗憾 36 分。
$10+79+36=125$，总分 $203$，居然翻成三个人中最高的。
PKUSC Try Again！