PKUWC2025游记

· · 生活·游记

cnblogs 链接

Day -inf

CSP-J 360 被 T4 创飞了，四次 J 组一次没 AK（

CSP-S 考完发现前三题都是人均题，然后 T4 只写了暴力可怜的 12 分。

Day -inf

NOIP 272，GD 超过 50 人同分，这下 D 类有点难啊。

Day -inf

靠着补录的名额压线 S 组 312 分压线进了 NOIWC，成为 GD 守门员（

Day -inf

复习期末考试，我要上 A+！！！。

Day -inf

期末考试，掉到了 B+……

分数线咋这么高啊，我还觉得考的还行呢……

数学爆炸，没上 90。其他科目其实都能接受，主要是数学太低了。

Day -inf

CF 达到 2396，离 GM 差 4 分，下场我要上红！

Day -inf

有点感冒。

Day -1

明天一早的飞机，提前去机场住酒店。感冒好一些了。

晚上打 ARC，结果只会 A。

然后打 CF div2，结果这场挺难的，E,F 都不会。

Day 0

到了绍兴，从萧山到绍兴比从我家到机场时间还短（

碰到了先到的 bamboo，otterZ 要晚一些才来。

今天有省选模拟，下午打模拟，T1 不会，T2 感觉远小于 T1，T3 不会。

然后和 bamboo 一起去学校看，这个学校好像是新的，而且好大啊。

回来继续做题，然后打板子，打了 LCT，SA，SAM 这种好久不写的，发现好多都忘光了，什么矩阵树定理，PAM，万欧，希望都别考。

Day 1

同游者：otterZ,bamboo

这个学校真的好大啊！

然后开幕式。

开幕式结束后去食堂吃饭，结果人超级多，主要问题在于米饭要自己打，然后只有两个位置，以至于排了老长的队。

然后刚好排到我的时候只剩一碗，而我还要给 otterZ 打一碗，所以不得不重新去排了另一队。

不过饭还行，更上次在余姚类似，吓+西红柿炒鸡蛋+红烧肉+青菜，虽然我没吃虾，但剩下的还是挺好吃的。

回酒店午休。

12:20 去试机，很久没用 Linux 了，上次用还是上次营。

不过很快就熟悉了，决定还是用 Geany 来写。

但是试机赛有交互题，大胆预测两天必有交互题，所以交互题还是用 VS Code 来写吧。

13:00 正式开始考试。

开场先看 T1，发现是个小清新题，虽然 a,b \le 1000，但是根据往年经验很有可能有 O(1) 结论。

T2 是个 DS，T3 是个很复杂的题，定下目标：冲出 T2 就是胜利！

首先要做出 T1，开始手玩样例。

结果这个东西还比较困难，想不到怎么搜，先把 a > b+1 的分打了。

发现主要问题是 a \le b 的策略，想了半天想到一个方法：两两匹配，然后转移到更小的问题上，但是匹配代价 \times 4。

结果连 a,b \le 4 都过不去，不科学啊！

手玩了半天也想不明白为啥还能更小。

重新思考了一下，发现终点就是要使得存在至少两个有电的。

然后突然发现好像分成 a-1 组就行了，每组是个完全图。

然后就过了，怎么又是这种结论题啊。。。。

这时候 1h20mins 还能接受。

先把 T2 暴力打了，24 pts。

再把 T3 的 O(n^5/\omega) 打了，发现其实只用 O(n^3/\omega) 就行。然后就过掉了 n \le 3000 的 20 pts。

回去冲 T2！

先想线段树，不太会。

然后想分块和莫队，分块很难处理，莫队想到一个 O(m\sqrt n \log^2n) 的用可持久化线段树合并的复杂做法显然过不去。

然后想了很久也不太会。

先把 l=1 的 17 分写了，想到了一个用可持久化线段树合并加上倍增的 O(n\log^2 n) 的做法，其实不算很难写，大概半个小时就写完了。

然后一直想，还是不会。

最后 20 分钟突然想出了一个假的莫队做法，可以优化到 O(m\sqrt n)。

利用 l=1 的代码写完了，但是只过了样例。后来意识到其实是假做法。然后比赛结束了。

100+41+20=161 确实不是很满意，没有夏令营 Day1 高。而且感觉 T2 过的人会很多。

bamboo 想出了 T2 的做法，但是 T1 时间久了导致没写完，可惜了。

好像和 NOIP T4 很像，但我还没补。

心情不好，感觉 Day2 要是还这样就废了。

晚上把老师留的期末考试反思写了。

Day2

上午讲座很有意思，AI 和游戏以及机器人，收获很多。

吸取经验教训，回酒店吃饭。

然后就开始了 Day2 之旅。

昨天没考交互，非常希望今天交互放 T3，这样肯定只用打个暴力分就行。

结果交互放到了 T1，这下不得不做了。

用 VSCode 写，先把交互库什么下下来，结果这个交互库怎么编译还报 warning？？？怎么 scanf 返回值没用都不行？？

然后开始想题。猜测最大的 (x,y,z) 一定包含直径。这样有一个 6n 做法，但是交上去 WA 了。

开始对拍，结果对拍写了一会儿，原因是没法判断是否正确，所以最后不要 checker，直接多测。

然后发现是少写一句话，写完了就 58pts 了。

但是感觉 T1 还是要做出来的，于是继续想，发现能少一个 n，变成 5n。70pts。

然后继续优化，发现还能少一个 n，变成 4n，这下 83pts 了。

感觉这个分还能接受，已经一个多小时了，先看后面的题。

T2 不太会，感觉不是很容易，先看 T3。

显然这种题不是我能做出来的那种，直接看暴力。

有一个比较显然的 O(Br \ln r) 的暴力，能过前两个包，第三个 r \le 5 \times 10^6 冲不太过去。

然后看到 l=r 特殊性质以及 B \le 4，直接记忆化搜索 DP，状态数应该不多，也顺利的过了。

这样 T3 就有 36 了，感觉 T3 差不多了，后面都很难拿分。

这个时候只有 100 出头，还是要 T1T2 多拿一点，而现在已经快两个小时了。

回去看 T1，我的做法第一步就要 3n，感觉没有什么优化前途。

但是注意到后面的 n 是因为要找到 x \to y 路径上的点，所以只要找到 2 个就行。

于是直接大力随机化，对于 n=8 \times 10^4 只取前 6 \times 10^4 检查，对于 n=9\times 10^4 只取前 3 \times 10^4 检查，而且还有 \frac{2}{3} 的概率把链判掉了。

然后这个优化竟然冲到了 95 分！！！

意识到 T1 已经很高并且和满分只差 5 分，足够了，而 T2 还没有任何分，所以现在的目标是 T2 尽可能多拿分。

所以决胜在 T2！

T2 一眼上来先考虑顺序，按照 [1,m],[2,m+1] 这样来依次操作，那么贪心的想法是尽量操作前面的。

然后第一个贪心是先算所有能取 k 个，然后 k-1，依次类推，不过 WA 的很壮观。

想了一会儿觉得这种题还是得 DP 才靠谱。

发现由于问题在于每次可能会保留一些用第二种操作，而这样都是前缀都是 0，后缀不变，分界点不确定。

所以有一个 O(nA) 的状态，转移直接暴力转移到后面，是 O(n^2A) 的。

写写写，然后 WA 了，调了一会儿发现是转移没考虑 m 的限制，改完就 17pts 了。

然后看特殊性质 c=1，那么直接贪心就是对的，11pts。

现在是 95+28+36=159pts，勉强 320，还要更高一些才比较稳。

继续考虑如何和值域无关，发现这个东西就相当于有一些分界点，从分界点开始往后一直用操作 2，直到某个位置停下。

所以实际上状态只用是一维的，转移直接模拟这个过程即可，对于 \ge k 的直接计算，我们只用考虑余数，所以转移是 O(n) 的！时间复杂度就是 O(n^2)。

写写写，很短很好写，就 10 来行，写完很快就过了 n\le500,n \le 5000，+48pts。

现在 T2 已经 73pts 了，就剩最后一个正解的包，现在已经三个多小时了，想了一会儿还是不太会，感觉可能是要列出形式化的表达然后数据结构优化一下，想到了应该也写不完。

这时候算了一下分，95+73+36=204pts，竟然上 200 了，非常感动。

总分 365pts，这下好多了。

于是剩下的时间在尝试卡 T3 的常，但是没有成功。

然后就结束了。

感觉 T1 的随机化和 T2 的 n^2 暴力是为数不多的亮点。