联合省选 2026 游记

· · 生活·游记

cnblogs 链接：https://www.cnblogs.com/tkdqmx/p/19683724，推荐洛谷专栏观看。

Day 0

wx 说最后一天就别做题了，模板也别打了，做点自己喜欢做的事，遂爽颓。

雀魂四人南 413342433，杰2 打到只剩 42/1400PT，这会是考好的预兆吗？

不过八倍对线想进队肯定是不可能的，期望一下有没有概率翻三倍对线吧。

Day 1

反正娱乐场，心态放平随便考咯。

看 T1 怎么题面这么大一坨，不过读完过后题意还是很清晰的，先做常规转化，如果一个点被选为轻儿子轻边总数就会增加它的子树大小，所以考虑直接算每个点被选为轻儿子的概率，f_{i,j} 表示以 i 为根子树包含 i 的重链长度为 j 的概率，设 g_{i,j} 表示 i 父亲的其它子树包含根的总和重链长为 j 的概率，则 ans\leftarrow sz_i\times f_{i,j}\times g_{i,k}\times \frac{i}{i+j}，f_{fa_i,j}\leftarrow f_{i,j}\times g_{i,k}\times \frac{i}{i+j}，因为最开始想了点奇怪的东西，所以到这里已经花了接近半小时了。

然后直接背包转移是 O(n^3) 的，但可以用 NTT 做前后缀的卷积达到 O(n^2\log n)，所以就开写，写完 O(n^3) 过后大概已经开考一小时了，开始打 NTT，结果发现 NTT 写挂了怎么都看不出来哪有问题，所以重新开始思考。（其实我感觉做卷积的时候在暴力和 NTT 分别的 O(nm) 和 O((n+m)\log (n+m)) 选最小值跑应该是能过绝大多数数据的，所以这里一直盯着 NTT 看而浪费了好多时间）

重新考虑一开始被自己放弃的退背包，发现这是一个类多项式求逆的形式，重新手推了一遍 O(n^2) 求逆过后开始打，写完发现不太对，应该从第一个不为 0 地方开始跑，写完过后反复卡并确认各个地方的上下界，最后大样例最大时长 0.55s，菊花跑了 1.2s，考虑到 CCF 评测机应该会快一些，所以就继续往后做了，不过现在已经花了近三小时了。

T2 完全没啥头绪啊，本来时间也不是很多就直接开始搞特殊性质，A 直接暴力不过写着不是很爽，B 性质是个背包也比较简单，C 性质看着大样例猜的一定只在前后加 0，感觉没什么大问题不过也不太确定，但是时间不多就先这样了。

T3 先拼了暴力和 m=1，因为很简单，m=2 看着不是很难但是好像细节很烦就没写，B 性质给得很好，反正就把后面的数丢来丢去就行了，但是没写完，少 16pts 很可惜。

最后期望得分 100+45+12=157，感觉很普通的分数，出来过后确实是，听 thr 说巴蜀人均过前两题，还疑似做过 T2 原题直接吓傻了，不过好像还是很多人没过 T1（原因是不会多项式求逆？？？），不好说看明天的题怎么样吧，反正最高理想就是三倍队线。

Day 2

早上从沙八宿舍醒来发现 7:53 了？？？迅速叫醒 MornStar 往巴蜀赶，幸好没迟到。

T1 最开始想二分，发现没必要，左边右边跑就可以了，有点水过头了。

T2 做了全场硬是一分没拿到，想了一堆完全错误的结论，想到转换成操作四元环也不会，倒闭。

T3 题面看了就放弃了，什么奇异幽默搞笑题，一堆没有非集合元素的东西比大小，暴力都没打。

考试开始快 3h 了改样例解释 hyw，考试还有不到 20min 结束又改一遍是人吗？最后 4min 的时候告诉我考试时间延长 15min 这都啥东西啊，拉完了这个 Day2。

100+eps+0，不过反正今年是娱乐场，下个赛季再来吧，希望不要再在 NOIP 提前倒下了。