点击输入文字

· · 生活·游记

在游记开始之前，先输出一点垃圾话。

小时候我经常会看着学长的游记感慨，他们为什么这么厉害，连这些东西都会。而现在，我也到了他们的年纪，但是却感受不到自己这几年来的进步。

当然这听起来可能比较主观，但是从客观上讲，看着之前他们能做出的题目，我还是和从前一样无从下手。

拿一个最近的例子来说，pkuwc2025 的试机题有“圆”。一看到这题，我就不禁回忆起去年 Day2 的搞笑发挥，做这题做了一两个小时的阴影挥之不去。为了判断自己的水平有没有长进，我尝试在试机的时间内重新做这题，然而不幸再次坠机。

当时心情确实比较失落，不过紧接着的考试很快让我忘记了这件事，没有再过多沉沦。现在来看，或许我的智力真的从来都没有进步吧。

Day 1

开局异常的顺利。第一题为了保险仔细推了一下边界才写，不过并没有花费很久。

然后第二题一眼就知道复杂度肯定和 n^2/w 脱不了干系，随后编出来一个 n^2\log w/w 的魔怔做法。

为了写的方便，我一上来就手写 bitset，这也为后面以小常数 3.6s 通过大样例埋下了伏笔。

此时比赛才过去 1.5h，我感觉自己简直稳了。

然后开始做第三题。

这个题一看来者不善，又是字典序最优化又是图论的，所以我第一想法就是先得到一个 \operatorname{poly}(n) 的做法。

推了半天性质，先会了合并多个联通块，然后又注意到了 p_1=1，再讨论一下看起来就可以删点然后用子问题的答案计算原问题答案了。

看起来差不多是 O(n^2) 的复杂度，还有 2h 时间，总该能写完吧？

然后就写出玉玉症了，最后连那个 n=10 的样例都过不去。

出考场的时候多少有点破防，尤其是听到大家全都过了我根本没额外考虑的森林部分分。不过我心里也有一股莫名的平静，毕竟我已经没有什么能失去的了。

好像同校和很多认识的人考的都不太好，这其实比我自己的情况更令我难过。

Day 2

开题一眼看到这个 T2，差点没绷住。感觉又要拿去年的剧本了。

不过不同的是今年大家都已经是 dag 容斥高手了，所以很多人通过这题可能是预期内行为。

一开场大致想了想 T2，先用“考虑所有 w\leq x 的边形成的联通块”来刻画最小生成树，然后以每个联通块里可以作为根的点集 S 来刻画最小外向树。感觉再编一编就能做了，但是写起来会很变态。

于是先放下这题，回过头看 T1。发现这题直接按照 t 从小到大贪心就是对的，因为每两个状态之间都是能走最短路的。

然后写了一个用了 set，排序和二分的代码，跑得还挺快。

回过头来继续编 T2，好像用力一下就做到单次 3^{size} 了，用点强连通计数之类的锤子。但是感觉复杂度有点大。

仔细分析发现只在产生新连通块的时候做更新复杂度就是 3^n，然后就直接开写了。

写起来确实挺变态，中间我还怀疑自己假了，对着最小的样例调了半个小时，不过最终是在 3h 的时候通过了所有的样例。

然后继续看 T3，有种 AGC 计数的感觉。

一开始连 n,m\leq 10 都不会，但是写了个爆搜，发现跑的很快。然后观察了一下可行解的集合，发现答案好像是 nm2^n 级别的，这个时候我就想写一个 \operatorname{poly}(n)2^n 的做法来通过 n\leq 18，但是发现编着编着就倒闭了，最后也没有回过头来看 AB 性质，和昨天死法完全一样。

出考场发现过了 T2 的人并没有那么多，可能自己还不至于进不了省队。

细心的读者可能发现了，这次省选我一个题都没有对拍。

可能是自己厌倦了 OI 赛制吧，反正赛时是完全没有对拍的欲望，即使知道去年自己拍挂了好多地方。

现在回过头来看这场比赛，发现高手还是太多了，甚至有人两天 T3 分别拿了 100 和 72。

感觉自己就算训练一辈子也是有一个水平上限的，不知道接下来的半个赛季能不能对得起自己许下的诺言。

不过在这之前能做的也只有等着，希望这场大梦不会让我醒的太早。

从比赛的反思来讲，我觉得这两天打的都算顺风局了，但是就是 T3 完全没有找到正确的做法，以后一定要多考虑特殊性质，不要一上来就给自己下个定论了。

还有些话等到省选结果出来再说吧，如果真挂出省队就说不出话了。