联合省选 2026 游记

· · 生活·游记

是前提要（过了一年画风突变）

因为我太菜，所以没有体验选手的名额，NOIP 四倍队线以外，挑战 D 队。

Day -114514 ~ Day -1

一直在摆烂，一直都没有学，还沾上了雀魂。

Day 0

上午终于开始主动写题了，中午回家，打了一下午游戏，晚上去车站到酒店，和小男娘住一间房，晚上 10 点准时睡觉，然后开始和室友一起银叫。

Day 1

开考前本来想答辩一下的，但是忘了考点学校厕所没有包间，于是又折回了，后面想到可以开考后去，因为中间人就基本没有了。

因为时长增加，所以早就做好了 T1 就是紫的准备，看到题面直接释然，超长题面加树形期望 DP，直接启用暴力拼满策略。

大概分析一手，发现题面好多废话，其实题意很简单，因为对概率期望不熟，所以误以为想出来接近正解的做法，很快便发现假完了，又以为想出了三次方做法，打算先看后两题。

发现 T2 暴力还比较足，一开始以为送了 30，看了眼 T3 感觉巨难，性质也都一个不会写，打算先放一放，目前一共过了一个多小时。

按照策略，后两题肯定都是写不出来的，所以先写后两题暴力，T2 爆搜写的有点答辩，调的有点久，写全是 0 时更难受，先假了一次，然后又发现好像不能直接贪，还得加 DP，不过幸好没有特别难，最后也是调完了，一共又耗了一个多小时。

全是 1 的大概想了想，感觉没有很难，本来打算写的，但是看了下大样例看到了一个极其离谱的 n=1 的情况，意识到我少考虑了很多，直接被吓跑了。

怕 T1 写不完，于是先写 T1 了，然后发现做法依旧假完，最后也是决定不写有前途的做法了，不敢再像 NOIP 死磕 T2 一样暴毙。

想了一个可能分会高些的暴力，就是求 f_{i,j} 表示到节点 i 重链长为 j 的概率，转移用搜索转移，即枚举每个儿子重链长多少，乘起来算对应概率。轻边的期望同理不难，最后加一下就可以了。

注意枚举的时候是不枚举概率为 0 的，这样会快很多，且不会被链、菊花、菊花套链、链套链、菊花套菊花卡掉，但是刻意构造也是比较能卡，应该不会放过去很多。

最后一个大样例跑了 6.5s，其他的最高 0.4s，本来想着卡卡常加 CCF 神机再多过几个的，但是 longlong 改 int 一直改不对，就红温放弃了。

这个时候去把考前欠的答辩解决了一下，虽然中途隔壁考场还是有人进来上厕所。。。。。。

把 T3 送的 12 分又拿了一下，想了想其他的也没好思路了。T2 搜索拍出了一点小问题，最后剩下的 1h 没什么进展了，感觉这个时候已经完全没脑子，无力思考了，无奈只有 28+30+12=70。

一点的时候遇到诡异事件：我的身份证输入错误，应该是系统录错了，最后搞了 20min 才交上去。（我不会告诉你前面我还把密码大小写看错，然后密码错误问监考员，虽然监考员也没看出来）

虽然也不是很 adhoc，但总归没有算法。

和同学讨论了一番，70 真是我们这边的大众分，但是据说水星湖要当队长了（怒）。

一中和我们不在一个酒店（悲），约朋友散步被拒。

晚上学弟让我复刻一下 T1 写法，在 QOJ 拿了 64，祈祷 CCF，CCF 我爱你。

然后就是一直打游戏了，教练收手机的时候不知道是教练来了，于是打游戏的时候直接把手机关上了，导致我想清一下缓存，但是缓存还有声音，被教练听到了批了一顿qwq。

还是 10 点准时睡觉。

Day 2

这天的目标是正常发挥稳一下 D。

第一眼就看到的表格里的“交互”，当时还是挺震惊的，虽然教练提前给我们说了按照这个趋势可能要出交互，但是我自然是不信的。

我并不怕交互，因为平日里我交互水平也不是很低。

T1 显然有个 n\log n 次数的做法，再加上 ABC 性质，大概有 60 左右，很快便想到做法，根据 B 性质感觉可以推广出一个新做法，但是脑子卡再那了，推广失败，看后两题。

T2 超级大思维图论，甚至暴力都难写的离谱，直接放弃并且后面也没怎么看了。

T3 题意超级长，于是想着先再想想 T1，但是仍然没有进展，于是开始读题。读完题后发现题意其实很简单，想明白后想出一个四次方做法，原本以为是三次方可以过 2000 的，后面发现算错了，悲。

这个做法调了较长时间，大概已经半场了，怕 T1 写不完就先写 T1 了，很快写完了 n\log n 的做法，然后尝试编译。之前本地一共就测过一次 spj，交互题一次都没测过，所以在试了 30 min 无果后其实都已经崩溃了，当时暂时忘了可以把代码和交互库合二为一了，不过好在 30 min 后想到了，而且直接把我的代码复制粘贴进 grader 就可以直接编译运行。

接着调了很长时间并把 ABC 性质都写上，彻底调完时已经一点多了，此时感觉没时间写 T3 的一号测试点，准备等着结束收工呢，结果由于更改了两次题面，就加了 15 min，于是我就去补了一下，很快也补完了。当时看二号测试点，想着要求两条路径交集，赛后才发现他妈的两条路径本来就是重合的，怒。

T1 一直都有一个诡异问题，就是我 O(n) 时间跑不过 20000 个 push_back，等出分再看看吧，场上真的有点崩溃的，但是考虑到可能是机子和本地的问题，我就没怎么管，要是真过不去的话我就只有 30 pts 了，这里出成绩之后补充一下。

于是估分 60(+eps)+0+12，补充一下，T1 之所以没有去想太多就是因为首先我只很快想到了 n\log n 的做法，想了 30 min 都优化失败就放弃了，没有想过这个题实际上正解非常简单，毕竟我当时性质 B 也很快想了出来，只是推广了几分钟失败就没有再尝试了，主要是我意识里 Day2 难度一定是大于 Day1 的，觉得这题肯定是紫，所以就不想了，甚至当时觉得 60 分还是个比较不错的分数。

出考场后发现 T1 是蓝，就非常崩溃，也是这次最难受的地方了。

紧接着就发现我把性质 B 看错了，我误以为是前面后面都是递增，结果后面发现前面是递减，后面是递增，这个不影响我的思路的，痛失 10 pts，悲。

于是 Day2 拿下全校最低估分，跳了。

接着依旧依旧，没什么好说的，晚上耗费着假期时间补完了游记，还不快点赞？？？不过也由于是晚上赶工，所以很多有意思的细节也都忘了或者懒得写了，见谅。

这么看的话 D 大概就是没了吧，除非 Day1T1 64 以及 Day2T1 50 还有希望，祈祷 CCF，我爱你。

唉一年过去，学了很多新算法，到头来什么都没用上，按照这个趋势来看，确实该把绝大部分时间投入在思维上了，还是脑子不够好使，mex 的经典 trick 我也基本不知道。

下周末有好事情发生哦（保密），期待大家提前祝贺我。

本篇可以对比去年的游记看看变化，我有些刻意模仿的地方。

最后还是祈祷 CCF，但愿能在今年的 NOI 赛场上与你相见。