PKUWC 2025 游记

· · 个人记录

2025.1.13

杭州 \to 绍兴。
室友是 @xieruyu。
又被 D。
晚上 @xieruyu 22:30 睡的，我在床上水知乎水到 12:00。

2025.1.14（D1）

去吃早饭时没几个人。
上午听了一个听过 2 遍的讲座。
笑点解析：有人尝试在 PKUWC 时面基去 THUWC 的人。
12:20 进行了一个试机。
貌似傅大神把大半参赛选手的路带偏了。
T1 是 PKUWC2024 的 D2T1，我记得当时 10min 切了，但忘了咋做了。
T2 是神秘交互。
写了个 T1，发现没过，卡了卡了卡了，花了 15min 还没过。
怀疑精度被卡，改了一下，过了……
T2 刚看会一个 k+1，然后会一个二分套二分的 3\log^2n，感觉能拿 60。
还有 3min，懒得写了。
熟悉了一下厕所。
（13:00） 正赛开始。
T1 是个神秘题，T2 是个 Ynoi 状 ds，T3 是个博弈（题面放最后了）。
看了一会 T1 感觉没什么思路。
（13:05）查看了一个部分分，发现有个 a>b+1，想到了一个摩尔投票，就是每次验两个，然后如果失败就都丢掉，他显然不会让你成功。
令 f_{i,j} 为 a=i,b=j 时的答案，随手想了个 f_{i,j}=\min(f_{i-1,j-1}+1,C_j^2+ij+1)，写了写，发现 10 分，过了 subtask 2,4。
（13:10）玩了一下 a,b\le 4，发现最优解可能会有验一个 (a,b),(b,c),(a,c)，此时他显然不会让你赢，那么 a,b,c 中至少有两个 0。
猜测 f_{i,j}=\min(f_{i-1,j-1}+1,f_{i-1,j-2}+3,C_j^2+ij+1)，写写写，20，过了 subtask 1,2,4。
（13:20）玩了 10 min，感觉验任意完全图都是行的，猜测 f_{i,j}=\min(f_{i-1,j-k}+C_k^2,,C_j^2+ij+1)，O(n^3)，写写写，70，TLE on subtask 7。
（13:22）注意到 C_x^2 是凸的，所以均分一定优，则 k 在 \frac{j}{i-1} 左右，枚举 \pm 3 就过了，100 pts。
（13:30）T2 我会 O(n^2)，写写写，再获得 24 pts。
（13:40）注意到区间“本质不同”想到 HH 的项链，l=1 想到只需 pre=0，注意到一个点 pre=0 的 k 显然可以二分+BFS 序上 ST 表，再来个二维数点就行。
（13:50）注意到每层独立，考虑用 r-l+1 减去 dfn 相邻 k 级祖先相同的数量，然后对每层所有可能 dfn 相邻的对写出一个三维偏序，cdq 即可，这么唐吗？考虑 16:00 前写完。
（13:55）哎我假了假了假了，“所有可能 dfn 相邻的对”是 O(n^2) 的，What should I do?考虑写个 l=1。
（13:58）这么难写写个鸡毛，考虑加点怎么做。
（14:18）l=1 好唐啊，考虑加点，独立每个深度建虚树，相当于在虚树上插入点，用 n 个 set 维护，然后多出的那一个 LCA 用 BIT 后缀加就行，写写写。
（14:40）感觉挺好写的，没怎么调就过了 subtask 5，因为没拼，所以此时 100+24+0=124 pts
（14:42）再套个删点不就能莫队了？写写写。
（14:50）写完了，只能过 subtask 1,5，27pts。
（14:55）哎我莫队排序写错了，改完后过了 subtask 1,2,5，此时 100+41+0=141pts，不是 O(n\sqrt m\log n) 怎么过不去 n=5\times 10^4,m=2\times 10^5。
（15:00）时间过一半啦，分数还不到一半。
（15:05）发现 LCA 可以换成 ST 表 LCA，查询 O(1)，且这题只用查深度，还是 41pts。
（15:20）发现莫队+BIT 很唐，把 BIT 换成分块，O(1) 改，O(\sqrt n) 查，还是 41pts。
（15:30）造了组 subtask 3 级别数据，发现我要跑 27s，要进行 8\times 10^7 次 set 插入/删除/求前驱后继。
（15:35）加了个奇偶优化，然后仔细计算块长为 \frac{\sqrt n}{2}，要跑 13s，要进行 3.3\times 10^7 次 set 插入/删除/求前驱后继。
（15:47）突然想到秃子酋长，发现回滚莫队+链表就可以做到 O(n\sqrt m)，但是非常难写。
（15:55）仔细思考如何可撤销链表后，进行一个开写。
（16:20）写完了，还有 40min。
（16:35）“大样例”（自己造的那组）过了！！！2.1s！！！
（16:40）四分钟前交的，测到这时候，100+77+0=177pts，subtask 6 TLE。
（16:52）阅读 T3 题面，写出了最低档暴力，100+77+10=187pts。
（16:55）突然意识到 T2 IO 量很大，敲了个快读，交。
（16:57）T2 还在测，进行一个 T3 subtask 2 的写，写不完。
（16:59）T2 过了！100+100+10=210pts。
（17:00）结束，T1 0.78k,T2 5.04k,T3 1.02k。