PKUWC & NOIWC 游记

_lmh_ · 2025-01-24 10:24:21 · 生活·游记

（Chorus：当舞台降下光）

先做 T1。假了几个贪心之后发现可以把 a+b 个点拆成几个团，然后 dp 就过了。

T2 可以先用长链剖分将合并次数减小到 O(n)，这可以启发式合并。先写了个暴力验证正确性，很快就获得了一些部分分。

考虑到树套树常数巨大（没注意到 cdq），不一定可以通过，写了个特殊性质。

树套树一个（额外的）部分分都过不去，不会卡常，果断放弃。发现每个左端点和每个右端点只有一个区间，分块做是简单的。多一个根号，但是可以轻松通过。

然后开 T3。很快会了平凡的暴力。AB 性质感性理解了一个做法，调了一会过了。

此时还剩 1h，但是肚子巨他妈疼然后似了，没思路，最后总分 250。

水了一会群发现这个分似乎还可以？

唐。

开场不久就会了 T1 的 5n 做法（找到距离最大的一组 x,y,z，在这里面找直径），获得 70 分。T3 写了个暴力获得 36 分，但 44 分卡常失败，遗憾离场。

然后写了 T2 c=1 的贪心，发现这玩意在 c>1 的情况下会似。乱搞失败后开始 dp，写出了 O(nV)。

发现有效的状态数是 O(n) 的，一通优化之后获得 73 分。

感性上用一点 ds 可以优化，但写不太动。

想了一百万个 T1 的做法都假了，最后把自己的做法优化到了 4n。感觉随机化随不动一点，遗憾离场。

总分没上 200。

不好评价。

用了 10min 发现 T1 是两两配对，这就好做了，30min 成功通过。

然后开 T2，发现事情不妙。先写了 28 分暴力，然后开搞特殊性质。经过了 2h 的调试与对人生意义的怀疑之后获得 0 分。死因：没有特判全相等的情况。

感觉要似了所以只能啃 T3。这玩意和 PKUWC D2T2 长得很像，导致一开始以为区间长度固定完全不可做。发现可以任意选区间之后很快设计出了 O(nV) 的 dp，并且可以轻易优化到 O(n^2)。

注意到 dp 数组的值形如一些斜率为 -m 的段和斜率为 0 的段，这个可以用平衡树维护，复杂度带两个 \log 但跑得很快，1.5s 轻松通过。

最后还是调不出 T2，人生完蛋了。

有 30+ 个人卡在 234 分，把咱挤到了 rk 100+。

退役。

策略和心态上还有很大的问题。NOIP 运气好有足够时间调完 T3 和 T4，但这种依赖 rp 的方法自然走不远。

PKUWC D2T1 的做法可以随机化但是赛场上没有看出来，D2T3 的数论题完全没有思路，这在正式比赛中是无法接受的。

在 NOIWC T2 上浪费了 2h+ 才开 T3，这对心态造成了极大的影响，无法静下心来做题又怎么能考虑到 corner case 呢？结局就是特殊性质写了一辈子也只能拿到 28 分。

不要骂题目出的不好。别人能拿高分，你为什么不能？菜是原罪。

如此状态，如何省选？如何 NOI？