ZJOI 2026游记

还是认真写一下游记罢。

前情提要：NOIP 164 炸完了。抱着陪跑的心态来打我的第一次省选。

Day 0

与 @fush 和 @AvisD 前往杭师大，路上与 @wmrqwq 汇合。

在酒店与 @yaotianhao 面了。后来又见到了一些人。

八点被教练强制集合了，开了个神秘短会。开会前还遇到了 jzc。社牛 wmr 前去严肃拍摄。

省流：期间 @QwQ_lopgov_QwQ 的小手机真好玩。

摆到不知道 10 点还是 11 点，困了就睡了。

七点起来吃早饭。

大概八点多到考场门口，看见了很多著名选手。

彩蛋：某个女选手跑过来并对 dly 说“你就是 dly 吧，久仰大名”云云，明星选手实锤了。

竟然还有 dly&yqf 面基环节！磕爆了，可惜没拍上照。

入场之后发现我和 bd，lrh 三点一线，天象凶兆（咦

看了一眼题目，T1 怎么是树剖相关，T2 字符串，T3 序列相关。似乎全是考前觉得会考但没复习的东西。这不炸了。

T1 我一开始还以为可以 O(n) 做，大概是维护每条边是重链的概率以及每个点的期望重链长度，然后直接推。

之后才发现期望除以期望是什么鬼。有点搞笑。

推了推然后随便写了个背包状物，大概就是 dp_{i,j} 是 i 节点重链长度为 j 的情况，然后对 x 的每个儿子，对除他之外的所有东西做背包，after that 再转移。

复杂度有点爆啊！不过怎么过了 48pts 的包了。（而且我写的东西好像是 O(n^3) 及以上的？）

最大点好像要跑十几秒的样子来着，盲猜正解是要 n^2。但瞪不出来有啥能优化的？不管了。

T2 神秘构造，拼了 30pts 就跑了。（事实证明我是不是应该观察下大样例

T3 写了爆搜和 m=1 的分，m=2 的会了但没调出来。

感觉是 48+30+12。抑郁症了。

同学咋都过 T1 了！羡慕小常数选手。成功在 Day 1 垫底。

下午+晚上一群人在房间里颓神秘东西。奶了一口明天有交互题。

睡的不算很晚。

早点来到了考场。成功拍下了 dly&yqf 同框照/cb

怎么 T1 和 T2 都是函数式交互啊？哦 T2 是假的，那就是 1.5 个。奶成功了，我是奶龙（？

好像就是如果 \textrm{mex}_{l,r} 和 \textrm{mex}_{l,r+1} 不一样的话就可以推出来 p_{r+1} 了，其他都一样。

弱智的是我拼完所有特殊性质后写了一个每次二分找数位置的东西……并且写这个东西还是在我写完 p_0=1 的部分分之后。其实你判断完下一个数在哪里之后均摊 O(n) 推过去就好了。因为二分尽管随机数据表现很好，但对很近的数需要的操作次数很多。

完全没有长进啊（确信

T2 我好像会 k=3，就是每次操作三元环可以看作类似缩边的操作，然后直接能缩就缩应该就对了。

搞笑的是题目要求最终的边最多，我写了个边最少，彻底倒闭了。12 \to 0。

T3 滚木套滚木我能做啥？（事实证明读懂题面花费了半小时）4pts 跑路。

估分 [48,70]+(12\to 0) + 4。

出考场 5min 就会 T1 了，我要抑郁了。

还没赶上火车，幸好改签了，不然真抑郁了。

出分：

寄寄