pkuwc2025游记

· · 生活·游记

Day 1

讲座。无聊。

饭比较正常，不好吃也不难吃。

上机。

t1 是策略题，感觉要被硬控了。

猜测是 O(nm) 的 dp

交上去只有 10pts。

反复枚举策略，大概在 0.5h 过了 t1。

t2 是数据结构题。

直接莫队就是根号老哥的。

写出来只有 41 分。

log 来源于 set 和 bit，把树状数组改成分块，获得了 58 分。

此时比赛过去 1h+，先去看 t3。

t3 看起来像困难题，写完 20 分暴力就跑路了。

发现 t2 上不添加回滚莫队就可以做到 O(n\sqrt m)，看起来很像正解。

过样例后 wa 了好几发，于是写了拍子。

调了一会，又在 $n=100$ 处挂了。 发现一个很离谱的错误：没有对点按深度分类。修改后提交，发现过不了 sub1。 发现能过 $l=1$，想到分块没清空，改完后就能拍上了。 但还是过不了 sub1。 此时距离比赛结束还有不到 1h，我有点红温了。 我认为错误肯定就在清空那里，检查发现有一个 $n$ 打成 $i$ 了，应该是 ub 导致我拍不挂的。 提交后终于能过 sub1 了，但还是只有 58 分。 我对着自己造的数据疯狂卡常，在剩余 10min 左右获得了 77 分，$m=4e5$ 跑了 3s。 继续卡常无果，遗憾离场。 100+77+20=197。 出来后确认大众分是 220，安心地似了。 ## Day 2 不会 t1。看到是交互题的时候心就凉了半截。 想了 2h+，却只拿到 46pts。 t2 想了个贪心策略，但不知道对不对，先放在一边。 开 t3，先把暴力写了，然后发现好像有效状态数挺对的，直接开冲。 调了 1h，而且跑的很慢，在最后剩余 5min 时才过掉了 $n=10^8

46+0+59=105。

其实不会 t1 的时候就已经知道结局了，打到后面就只想拼上 100pts，给自己一点心理安慰了。做不出来 t1 确实是水平差距，回去要好好训练了。