原来我会写半道题【2026省选邮寄】

· · 生活·游记

教练，我也要打省选吗？

省流：【0】+【30】+【0】+【?】+【0】+【8】

day -inf

啊，我也要打省选吗？NOIP考出了 123 分的好成绩，还没初二的语文期末高。

day 0

全初三要打省选的都在 17:45 走了，就剩了我和 @DimStar 留在学校明天和学长一起去考场。

day 1

早上到了校门口，等了一会上了车。@DimStar 身份证被他做在腿下面了，找了半天。

到了校门口，刚好看见 JX 的在考点门口拍照；遇到了 @liuhongcheng2013，JX初一打省选的大手子。

然后连续来了 @pylktz@Grace2022@Danielcdo@JDScript0117 ，有说有笑的进了考场。

开考。

T1，嘶——期望+树上问题，题目还给了一个随机剖分的思想(O_O)?行；想了一会很不好维护。下一题；T2，诡异 string，发现保留比较好打。O(2^n\times n^2) 有 15 分。然后 ABC 性质应该都不难，大概 30分钟；把性质 A 写出来了。这还要我写个唐唐 DP。

然后推性质 B，好像不怎么好写；不同于 s_i=0 把 1 看做分割，s_i=1 的话只要子串长度小于 n 或前 n 个里面有一个 0 就可以计数；恰好 k 个还是太神秘了。最后没写出来，正解不清楚；串串不太熟悉。

回看 T1，发现好像有思路。拆式子 f[u][k]=\sum_v \sum_i f[v][k-1]\times (k-1)\times (\sum)^{-1} ，然后这个 (\sum)^{-1}，我唐唐的拆成了 \sum_i f[v][k-1]\times (k-1)\frac{\prod 概率}{\sum 方案数}。然后 \sum \prod 概率 我就认为是 1 了，然后只需要维护 \sum 方案就行了，结果确实 \sum \prod 方案=100\%，但这是所有方案的，我们这里限制了一个 v 的贡献为 k-1，就不是 [1,dep[v]] 的所有了。然后写了一个小时，调样例一个小时最后证伪。

考完听大家 T1 写了个 O(n^3) 的 48pts 做法，(ΩДΩ)！什么(O_o)?? 行，想了一下没有立马的思路；周一在去看看吧。

然后机房各位大手子还是太强了，虽然 @Danielcdo 说他 T1 的伪 O(n^2) 过不了；但就 @Danielcdo 这个入，绝对又切了。然后 @DimStar 的估分就比较拟人 【48】+【15】+【12】；tql orz。

~~听说 @JDScript0117 没 AK，大为震惊~~。

回 cw 拿东西到考点附近的酒店住下了了，晚上打不了 ABC 了。┭┮﹏┭┮

day 2

拟人的一天。

省选：不会 Linux 下的运行指令，然后 CCF 也没写；唐唐的 T1 里面质问 CF。考号好像是 SC-184，洛谷迷惑行为等我。

看到交互已经死了，看到两道交互已经想问候 CCF 了。看到 T3 是传统题（不是 T2 你配叫传统题吗！）然后看半天没看懂样例解释2，12点多才订正；无语。然后燃尽 3k 代码写了 8pts，n\le 10 的 8pts 因为没搞懂 \{\emptyset ,\emptyset \} 和 \{\emptyset ,\{\emptyset \}\} 的大小关系于是就没写。

然后 T1，想到了一个二分做法。假设已经确定 [L,R] 内包含 [0,now-1]，考虑 now 的位置；查一下 [0,R] 和 [L,n-1]，看看哪个的 MEX>now 说明 now 在哪边。然后去二分这个即可。然后二分到的 now 的位置更新 [L,R]。这个 [L,R] 的 MEX 在拓展的时候可能不连续，跳过的值说明在 [L,R] 里面找空位放就行了。

考完听 @DimStar 一讲，每次二分查 [L,mid] 或 [mid,R] 的时候；等价于查 [0,mid] 和 [mid,n-1]，因为不包含 now 的 MEX 一定是 now。然后就只需要查 [0,i] 和 [i,n-1] 共 2n 个区间；精细实现就过了。

更正：才发现 2n 过不了，大数据只能得一半的分。

啊，原来我会写半道省选 day2 T1！\ 啊，原来我会写半道省选 day2 T1！\ 啊，原来我会写半道省选 day2 T1！\ 啊，原来我会写半道省选 day2 T1！\ 啊，原来我会写半道省选 day2 T1！\ 啊，原来我会写半道省选 day2 T1！

行，明年高一正式名额的时候希望不要再怎么炸了。