？？省选？？流水账？？

· · 生活·游记

省流：高一，坐标 HB，非武汉，今年不打算进队，刷经验。

day -1 = 3.6，day 1 = 3.7。day 0 我吃了？？？

？表示？的意思？？？？？

？越多？的意思越重？？？？？？？？？？？？？？？

day -n

终于考完期末了，据说讲完题就全面听课竞赛？？还有这等好事？？？

什么？？？教练说我们直接来上竞赛课？？？？？还有这等好事？？？

什么？？？？学校居然专门为我们停课？？？？还有这等好事？？？

day -n+3

期末出来了，倒数。

先不管了？？？？准备省选？？？？

day -7

发现省选知识点已经学不完了？？？？那天排了一场模拟赛，机房倒一？？？？

day -1

抵汉。问教练是否有必要复习交互？？？得到回答最近几年都没考，没必要？？？埋下伏笔。

试机。什么填充？？？LGV 引理是什么？？？行列式求值不是 O(n^3) 吗？？？？手撕行列式？？？？喜提 0pts。

插一条广告：湖北2026省选试机题目 - 填充

出来吃午饭被阿姨嫌慢？？？下午看组合计数。

教练说 T1 至少花 3h。又埋伏笔。过了 200 pts 就是非常好的，只有 100 pts 是比较正常的。有没有可能还是伏笔。

day 1

第一个考试日。

开题。期望？？？？？？？第一题就上期望？？？？？再看第二题，什么玩意？？？傻了？？？？？？？？？？？？

建文件，推柿子。先设 f_u 表示 u 的重链期望长度？那么概率为 \frac{f_1}{\sum f_k}？？？欸等等，这不 O(n) 了吗？？？不对不对，绝对不对？出题人比我聪明！

欸，期望有线性性，这是线性组合吗？？？？？我在干什么？？？？既然线性性用不了，那么我就设 f_{u,x} 表示 u 的重链长度为 x 的概率？？？试试概率分布？？？

这个特殊性质 B 怎么这么有意思？？？是不是某个神秘树上背包？？？

列个柿子，重链总长为 l 的概率为 \prod \limits_{l_1 +l_2 + \cdots + l_k =l} f_{v_k,l_k}？？等等？这么这么像卷积？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？NTT？？？？？？？？？？？？？？？？？？？

NTT 的 O(n^2 \log n) 能跑 5000？？？？？？？？？？？？不可能？肯定不可能？？实际上我不会 NTT。但是我们不妨想一想生成函数？

我们钦定一下试试？？好像要去掉一个 PGF？？多项式求逆？？？暴力卷积？复杂度应该和树上背包一样？？但我不会证。大洋里过了，不慢。应该没问题？？做法省流。

看眼时间怎么只剩半小时了？？赶紧打暴力，T3 写给 O(T 2^n n)，没细算多少？？我常熟小，应该能得 8 分？？？？？？？？？？？？？？ 交卷。

估分：100+0+8？？？？

LA 大众分：64+30+16？？？T2有这么多部分分，我怎么没要？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？

下午看交互，晚上 DS。

day 2

解压。什么 perm.h ？？？？？？？？？？？？什么 starmap.h？？？？？？？？？两道交互？？？？？？

开 PDF。T1 交互？？？？？？？？？？？拿什么分？？？？？？？？？？等等？？T2、T3为什么都是传统题？？？？？？？？

看题面，MEX你就不能写一下吗？？T2 过于神秘？？T3 不止所云？？似乎只有 T1 可做？？？？？

先考虑二分 0 的位置，然后二分连续区间， 2\log n + \epsilon 次就做完了？？？不可能？？？？写一下？怎么启动不了？？？检查编译选项？？？没加 -static？？再编译？？wrong answer. ？？假了？？？？？

hack：4 0 2 3 1 5？？？我在干什么？？？？之前炼石 NOIP 模拟赛是不是做过这个题的弱化版？？？？（我不保证真实性）但我记不起来了？？？？注意到？最多交互次数为 n，加 \epsilon 单独计分是hyw？？？卡掉二分 0？？？那么我直接从两边向中间找？只有 Mex 发生改变的地方是有意义的？？？其他地方随便（不是简单随机，具体见题解）填填？？手玩能过样？？写了直接 Correct？？大洋过了？？

不放心？？先拍几百组 n \le 10 的防 corner case？？？再拍一下 3e4 的？？怎么不动？？？grader.cpp 怎么写？？？谁写的 O(n^3)？？？？改为拍 1e3 的拍了几组？？？应该没问题？？？

看 T2？什么最优化+构造？？？冥思苦想 1h，无法战胜。看 T3？？？？？什么集合的大小比较？？？子节点为 \varnothing？？什么东西？？？？？？？？？？？？？？？？？？

不慌不慌？？？教练说每天过了 100 就行，多的都是白赚？？先把 T1 再拍个几百组？？？？？？？？？然后 T3 一个八分的部分分写了 3KB？？？？延时？？？多坐会牢？？？？？

出来发现好像全校只有我过了 perm？？？高二学长把交互次数超过 6\times 10 ^5 没分看成交互次数不超过 6 \times 10^5 能过，祝好。

估分：100+0+8。

总估分 216，疑似全校最高？？？？？？？？但 NOIP 太低了，进队肯定是不可能的。说了就会被开盒。

见了在华科的学长。

下午晚上写游记，写完游记更新组合数学与计数dp学习笔记疑似广告？？？