PKUWC2025

· · 生活·游记

Day 1

试机怎么是元旦激光炮，我写了半天挂成 80，瞪出来的时候试机已经结束了，埋下伏笔。

因为没啥事情所以直接快进到开题吧！显然 T1 是签到啊，这个 T2 和 T3 看上去我都不能做掉。但是 T1 咋这么难啊。

手玩了十分钟写了一个贪心出来，获得 10 分，连 a,b\leq 4 都没过。

又玩了一小时相继发现 a=3,b=4 挂了，a=4,b=4 挂了，a=3,b=3 挂了。改了半天贪心结果只过了 a,b\leq 4，这贪心不能要了。

又玩了半个小时决定放弃贪心，随便写了一个很暴力的 O(n^4) dp 出来。我去怎么过了这么多点。

打表找了一下 dp 决策的规律，把 dp 弄成 O(n^2) 就 100 分了，赶紧走人。此时已经过去两个半小时，倒闭了。

赶紧写了一个 T2 的 O(n^2)，两发后过掉了 n,m\leq 10^4。然后时间太少了啊，先去拼个 T3 暴力。

写了十分钟发现我怎么过不去样例啊？原来题读错了。不过 O(n^2) 还是一眼的。补个 Tarjan 在剩 50 分钟的时候拿掉了 20 分的 O(n^2) 暴力。

这个时候发现 T2 的 l=1 是容易的，用长剖和 BIT 维护一下两个点合并一个点时的贡献就行了。莫队看上去反而不一定能拿分，事实证明我高估了数据的质量，以及没想到莫队可以拿下 l=1。

剩 20 分钟的时候写出来了，自己造了数据调了几下子在剩 10分钟的时候通过了 l=1，然后觉得莫队实在写不完了。

最终得分 100+41+20=161，和我去年 PKUSC Day 1 怎么一个分啊。

最大的失误还是在 T1，感觉 T2 做了 l=1 以后是很有前途的，莫队也有分，如果能冲出来一个若干 log 的或者分块说不定就 197 或者 220 了。

Day 2

早上通过一些小技巧拍到了 Nullptr_qwq 的照片。太帅了。我没带徽章啊，欠了他一个。

上午休息时间随便开了一把范式起源，结果打出了 1000000 的分数，又伏笔了。

因为还是没啥事情所以直接快进到开题吧！怎么 T1 是交互啊，伏笔回收了。手玩半小时写了一个我认为对的东西，交上去全 WA 了。

毛估估玩了一会决定先写个暴力，怎么暴力也全 WA 了，决定先给那个不太靠谱的正解对拍一下。我的运气其实还行，至少一开始的做法是有朝着正解的方向的，虽然有点太远了。于是边拍边写边修正做法终于用两个半小时过掉了这个题。

怎么又是逆风局啊！但是今天我的大脑已经倒闭了，T2 看了 5 分钟打算写一个贪心，因为没想出来贪心哪里假了，万一 T2 才是签到呢。写到一半想出来贪心哪里假了，重新想发现我怎么只会指数级别的做法啊？先去看 T3 吧。

T3 也太神秘了，写了个记搜过了 18 分，卡了几分钟发现卡不过去，没有什么优化的思路赶紧回去看 T2 了。

然后想出了一个关于值域的 T2 dp 做法，喜提 17 分。

最后 15 分钟的时候发现这个 dp 做法可以扩展到 c=1 的，赶紧写写写，然后最后 5 分钟的时候过掉了。

Day 2 最终得分 100+28+18=146，勉强战胜去年了，多了整整 6 分！

出来才发现 T2 73 分是非常简单的？？？

感觉万恶之源是菜啊，多练吧。练到真的进步不了的时候就退役吧。

我会的东西题解

D1T1：最优的方案是拆成 a-1 个大小尽可能平均的集合，然后对每个集合两两询问。

D1T2：莫队我好像确实不是很会。l=1 就是做一次长剖，把 x 级祖先相同的点的贡献挂在编号最小的地方，启发式合并然后 BIT 维护。有一个 \log^3 的做法就是在此基础上用 CDQ 做三维偏序（修改数是 n\log n 的），这也能过？？

D1T3：赛后其实多会了一个 sub，整整 30 分啊。严格的 n^2 暴力就是考虑缩点后倒推，同一个强联通分量的可以一起处理。b_i=i，图是 DAG 就考虑答案只能是可达的 \min 或者 \min+1，记录一下就行了，似乎再发掘若干下就是正解了，唉唉。

D2T1：考虑随便选两个点 1,2放进一个栈，然后重复做 3 次：取出栈顶两个点，找到到它们的距离和最大的点，放到栈顶，记这三个点为 3,4,5。同时可以用另外一种操作两次找到 dis(1,2) 和 dis(2,3)，解方程可以得到五个点里任意两点距离，答案就在 dis(3,4),dis(3,5),dis(4,5) 里，可能需要卡一卡交互次数。

D2T2：考虑确定了哪些位置操作以后直接从左到右贪心地取一定不劣，因此可以把所有操作拆成若干个删除的连续段，做一次 1D1D 的 dp 就行了，是 n^2 的。

D2T3：sub1 和 4 考虑直接记搜，sub2 和 3 据说 O(nB\log n) 可以直接过，也可以狄利克雷前缀和做到 O(nB\log\log n)。场上怎么没想起来，太搞笑了。