联合省选2026游记

Feynman5210 · 2026-03-07 16:42:56 · 生活·游记

省流：[68,100]+[15,45]+0+[80,90]+[12,28]+[20,28]=[195,291]。加上NOIP就是 [343,439]。

-25min进校园，考场在比较靠里，要走一百多米。
-20min进考场。在他们实验楼，楼梯上有四次工业革命的介绍年表()
-15min进教室。相邻座位有隔板，而且我还在最里面一列……考试用机时间比正常快8个小时。
-10min提前了整整10分钟发卷，系统密码和解压码什么的就不说了。开考前大致看了一遍题。怎么一到点就很多人开始敲代码。。
T1一眼树形dp，状态 dp[i][j] 表示以 i 为根时 i 所在的重链长为 j 的概率（取模）。这个用树上背包就能做。统计答案用算两次，每条边的贡献就是 它是轻边的概率 乘以 它深度较大的点子树大小。大约30min时写了个大概，然后发现各种写假，特别是统计答案要从背包里删掉一个物品，类似多项式除法状，带个log（不然就要写 线段树建树 状物，但不好写而且快不到哪儿去）。懒得搞了。这时大约1h。
看T2，A是平凡的，想了一会儿B和C，大概用背包都能做（B简单一点C难一点）。然后看D（包含B但不包含C），发现大概一段一段的加入 a个0和b个1（a,b不超过 O(k\log k) 对)，也是背包。后面那40分看着就不好拿。想着“有空就写”，去看T3，发现有12分是平凡的，看数据范围和部分分像三四次方区间dp，但看不出来咋dp。2h去了个厕所，排了大概5分钟队。
总觉得T3有蹊跷，盯了一会发现每个数都是循环位移后一段的异或和。但依然不知道怎么判Yes/No。想了一会儿没啥收获，又去想T1怎么搞没那个log，也没有收获。这期间可能还写了T2的A没调。大概2h40min，开始写T1最后那一部分。发现一般是大常平方，最坏小常方log（逆元的log），菊花图取到。写，调，发现假了。3h20min，心态炸了，怎么三分之二时间了还是零分啊？
我:"冷静地想想，100min能干什么？显然，先用20min调出T1，之后做T2部分分，还有时间再打T3的12。"于是再调T1，发现依然有错，再调，过样例1了，但没过n=18或19的样例2，感觉自己要挂掉了，被T1创飞了。发现有地方爆ll没取模，然后过样例了。3h40min（正好用了20min）测完了大样例，极限数据（三个链两个随机树）0.8秒多。
写T2 B+D（一个C分太少了不划算），想着调完就搞T3 12。写完发现暴力WA了，发现唐诗typo，暴力过样例了。测B+D先RE后WA，发现转移完全假了，基本得推翻重写（这期间去上了个厕所，不用排队）。大概4h25min，我选择冲一下这30。调了一会儿，好不容易过了手造超小D样例，发现过不了B。4h55min。发现我的转移对p=n错误，改一个式子就好了。改完，4h58min，写了freopen交上去了。之后在本地测了一下发现没有CE。中样例（这题数据本身就不大）没空测了。
Day1估分：[68,100]+[15,45]+0=[83,145]。~没考过NOIP（这会被当成P话吗）~ 今天还算不留遗憾吧。（大概率过了这个上位蓝T1，我还是幸运的）明天继续加油。

比Day1提前五分钟到场。附近座位有不少同学。~这次不坐在最里面了~。
-5min发的解压码，我在发码的时候才下载题目，结果10多MB的文件下到了开考后几十秒。
先看题。T1 CF风排列交互，T2套个交互壳的神秘构造，T3明显数据结构。看T1，首先二分或暴力求出 0 的位置。发现假设给定 0\sim k，则更大的数只有比它们都靠左或都靠右的才有用，中间的随便找空填上就行。每次先查它是不是在中间，如果不是再查是左还是右，最后指针暴力往左或右跳(这里不要二分)即可，3n+logn。顺便就会了A的n和B的比较少。C每次二分大概也是n。（我说怎么不给30000的样例，原来grader复杂度不对）这个分数貌似不是很高，准备看看T2T3继续想。
T2 k=3想了想会了（等价于修改若干环的并，由此做法是有相邻边就改，没有就结束），但完全不会怎么单独修改一条边/两邻边/两条不相邻的边。由此想到一个假贪心（只要有可以让ans变大的就立刻选否则认为已取到max），只能跑n=18。这题（当时以为）大概有28pts。继续想T3，一开始读错题把后代看成了儿子（题目文件也错了），发现这题a>b就是a的最大儿子大于b的最大儿子，最大儿子相等就比次大、第三大……（“儿子”应改为“后代”）发现菊花是简单的分讨，r=1直接敲个倍增LCA就行。3和4等价于找根的最大儿子，不会。5\sim 8 就是每次找一个点为根所有点的排名，大概按子树高度从1到n每个高度搞一搞就行了（代码不想写）。树是随机的那么复杂度大约是m*nlog。大概会了24。1h40min
回去做T1，先敲点一定要用的函数之类。这时发现问题：交互题写不写freopen？如果grader没有freopen，发现我怎么开都是错的（不能写main那么要干任何事至少要先输入c和t）。再看看perm_template也没写freopen。说明不用写。这时已经2h。
思考，发现问了上一个数就可以省去问这个数在不在中间，这样就是2n+logn。又发现初始把0到0，0到1……0到n-1全问一遍，就不用单独查每个数在左还是在右了，这样就是2n了，但分数还是不高。B一上来用二分，说明后面要严格小于n。想了想发现只关心每个数在左还是在右，问下一个数就不要往左或右问一个，直接问到头，平均一次出2个数的位置（1/2\times 1+1/4\times 2+1/8\times 3\dots），这样就是 1/2\times n+logn 了。至于每次到底问左还是右（如果某一边到头了就不用问了），正常来讲是问多的那边，为了防止被卡搞了个按两边数的数量加权随机(比如左边7个右边4个就是十一分之七问左)。发现这样无特殊性质可以搞到最坏期望3n/2。好像有八十多分，开写。2h40min基本写完调完（写了110行只有3KB，有复制粘贴成分），但是性质C的二分不对。调了20多分钟C决定放弃（这不到3分没必要搞）（实测100的数据我问了约110次，CCF水一点我分还能更高一点）。至此3h5min，[80,90]。
写T2，过了一会儿k=3写了，WA了，过了，暴力写了，WA了，过了小样例，WA在了n=18。发现暴力基本假的，不管了。4hmin左右，T2 [12,28]。
写T3，先写点2（1的分讨不太好写），没测（我对我的LCA板子蛮有信心的）。再写5678，调了几次，还没过，剩15min了，剩5min了，延时了15min（这我放心了），在原本剩一分钟的时候过了小样例。测2000的，跑得比较慢但应该能过。测点2的也过了，写点1的菊花分讨，基本一遍过。交代码。T3 [20,28]。剩五分钟就等着结束和同学确认交互不用写freopen。
Day2估分：[80,90]+[12,28]+[20,28]=[112,146]。~又没考过NOIP()。~ 昨天算是正常发挥，今天算是比较好的正常发挥。非正式选手第一次打，也不抱什么期望了（这分好像不够D）。打得个人看还行。