省选 2026 游记

· · 生活·游记

Day -INF

什么叫初三的寒假和高中一块放？？？

寒假共计三周半。第一周冬令营，第二周过年在家摆摆摆，最后十几天去南京集训。

六场模拟赛共计场切 0 题，补出 8/18 题，你也来试试吧。

从南京回来刚好开学😄。上了一天就省选了。

Day -1

原本以为是五点多报道完就能试机。结果都进机房并打完 A+B 了又被人赶出来了，说要七点半才能试。不过刚才五分钟感觉电脑没啥问题干脆不来了。

酒店房间好小啊。洗澡睡了。

Day 1

进考场。读题。T1 求期望？一眼秒出状态 f_{u,i} 表示 u 正在一个长度为 i 的重链上的……坏了值应该定义成啥？期望答案？或者我再弄个 g_{u,i}，一个记方案数一个记总和？

刚开始好好想外面咋着火了。我去那个监考老师喊那一声吓死我了。

哦哦哦我可以拆贡献，计算每条边是轻边的概率然后乘上子树大小。那就 f_{u,i} 表示概率就行。

转移的话……不会呀。其实我可以弄个辅助的数组 h_{i,j,k} 表示 u 的所有儿子中，它们所在重链总长为 i，并且长度为 j 的有 k 个，对应的 f_{v,?} 的乘积和。这这这复杂度不爆炸了。

后来就尝试优化，然后注意到了一些维度的大小是均摊的，但反正最后也没优化出不超过 \mathcal O(n^3) 的做法。

我甚至没意识到这东西有个名字叫树形背包。

（事实上我 h 状态里记“长度为 j 的有 k 个”完全完全没有必要。正确思路是枚举 u 从哪个儿子的重链继承过来，并枚举这个重链的长度，然后 h 只记其它儿子长度总和。这样显然 \mathcal O(n^3)。不知道为啥场上一直在想 h_{i,j,k} 这种一坨的东西）

不知不觉过了好几个小时了。感觉每场省选模拟赛包括现在的正赛都是前几个小时忙活了一堆东西但一点好看的分没有。

然后我尝试写这个好像是 \mathcal O(n^5) 的做法，尽管我知道不会获得比 2^n 更好的分数。写了一会发现算答案好像很麻烦（骗你的其实也不是很麻烦）就放弃了。时间过一半了先看看后面部分分比较好。

看 T2。2^n 暴力依旧秒。B 性质想了一分钟也会了。饿啊 CD 是个啥。看 T3。2^n 暴力依旧秒。m=1 依旧秒。等会就这点分吗。

然后一个小时左右把三个题能秒掉的暴力都写了。

剩下半个小时尝试写 T2 的 15 分。由于前几天刚复习了 AC 自动机所以打算写这个。最后写挂了。

结束了。

何意味。

这场比赛你给我一个小时我也能打这些分。

下午去爬千佛山。累死我了。

打 ABC。

我的首 A 就这么没了呃呃呃。

Day 2

我的发交互题，这么牛的。

T1 怎么题意这么简洁。一开始以为 n \log n 次询问就能满分，结果是 n \log n 次才不爆零（

思考了一会，想到一个依次确定 0,1,2\dots 的位置做法。这样最劣是 n \log n 但一般跑得很快。调出来之后放到虚拟机上测大样例发现最多才五十多次（n=100）。

然后尝试优化。后来得到一个大概是 2n+\log n 的做法，差不多还是先找到零的位置，然后尝试往左拓展并尽可能多的确定一些数的位置。确定不了了就往右拓展，这样左右左右交替的做。这样 l,r 指针分别是不升和不降的，它们总共移 n 次。由于你还需要判断是否扩展到最左侧也无法确定任意一个数的位置，所以每次还需要求 0\sim i 和 i \sim n-1 的 mex，这样就是 2n，但实际远远小于这个界。

后来就没获得什么更好的优化了。于是把上面两个做法整合在一起，拼上特殊性质，弄了一坨 200 多行的东西。

呃其实比赛这个时候就快结束了。改 T1 的同时我也在思考 T2 的部分分不过没有任何进展。最后半个小时写了个正确性也不对复杂度也不对的东西。关于 T3……说实话直到我现在写游记的时候也没看懂题（样例解释一堆滚木的嵌套）。

最后延时的几分钟算了算 T1 的分。最理想能到 80 多（骗你的 qoj 上只有六十多）。

结束了，又一次。

回家。

路上尝试理解 D2T1 题解不过失败了。第二天又看了看，发现一次 query(l, r) 可以拆成 \min query(0,r), query(l,n-1)。于是只需要预处理所有前后缀的 mex。这样就是 2n。然后一个位置的前缀和后缀一定有一个为 0，所以把无用的去掉就是 n 次。就这样。

也就是说所有部分分都是骗你的。任何一个 n \log n,2n,n+\log n 之类的做法加上这个东西后都能变成满分。