SXOI 2026 游记

· · 生活·游记

省流：赛季报销。

Day 1

队长说可能会有通信交互，害怕。

门口跟 xsy 说：我以前进场都是打 modint 的，这次不打了，要取模的肯定做不出来，打线段树（伏笔）

进场打缺省源，然后看压缩包，被 379k 吓哭 /ll

严肃打完 modint 以后再打线段树。

T1：这啥？？？完了我总共做过 \epsilon 个期望题。

T2：这啥？？？恰好 k 次咋处理？？？

T3：这啥？？？为啥部分分与 V 无关。

通读题面以后口胡了 28 + 15 + 8，然后对着 T1 做。

设 f_{u,d} 表示 u 到根节点的轻边数为 d 的概率，转移为 f_{u,d} \to f_{v,d} 和 f_{u,d} \to f_{v,d+1}，乘一个选 v 为重儿子的系数，不对这玩意咋确定。

设 g_{u,d} 表示 u 处重链长为 d 的概率，哎咋处理这个转移，只会 DFS 每个儿子挂的链长。

这啥，不会多项式复杂度有救吗。

后注：根本不知道期望线性性是可以倒着用的，拆贡献就不对，何意味。

对着 T2B 做，大样例是这样的：

0000...000010001

正常人类的拆法：

0000...00001  |   0001

我的拆法：

0000...000010001
           ^   ^

然后就一直在想咋定 1 的位置。不过这个是不是也可以完全背包做来着。还是太菜了导致的。

此时是 10: 30，用了 30min 左右实现 28 + 15。

看 T3，哦必要条件是异或和相等，获得 12pts。

对着 3 \mid n, m=2 做了半天，没有任何进展。

对着 T1 做了半天，声称得到了一个 O(n^3) 式子，不过现在看好像是假的。

出场发现大家都会 T1 三次方，T2B 有一万个人会，这咋办。 下午摆，然后简单调整了一下心态。反正 noip 已经爆了，本来也翻不了。 dcj 说明天考 mex 咋办，我说凉拌。 ## Day 2 谴责 SXU 机子不保留昨天打的缺省源。tywz 是保留的。 仍然打了相同的东西。 看 T1，为啥真有交互？？？为啥真是 mex？？？严肃追忆了一下极小 mex 区间是啥，定义忘了，证明忘了，求法忘了，唯一记得的是有 $O(n)$ 个。现在就是后悔，非常后悔。 看 T2。？？？ 看 T3，算了题面一坨不想看，先做 T1。 做 T1 的第一反应是 $\log n$ 地找到 $0$，后面忘了。稍微观察一下发现第一个数和最后一个数容易确定，那么 $n \le 10$ 就存在一个 $8! \times 8^3$ 的做法，先写一下。 怎么一直写挂，调出来怎么 9: 30 了。 注意到 B 性质，是不是可以二分谷点。哦哦哦 mex 等于补集 min，直接找前后缀最小值就行了。 那这个做法是不是可以一般化，$2n$ 次询问以后剩下的贪心填。稍微调了一下并且拼了部分分，10: 00 获得 $75$ pts。 去上了个 WC，回来的时候突然发现直接二分找 $0$ 好像就可以省去一些询问，这是 $n + \log n$。 根本不用二分啊我在干什么。直接扫前缀扫到 $0$ 就好了，$n$ 次询问，10: 30 获得声称 $100$ pts。 反应过来 T1 好像是简单题，估计会有一车人过，看 T3，然后飞速实现 $r=1$。 仔细观察一下字典序的定义，哦题目描述需要中译中。是不是可以对树编码，但尝试了一会无果。于是直接暴力比较，获得一个 $O(n^2 H)$ 的算法，在随机数据下跑的飞快。 做了一下菊花图，分讨一下就好了，到 12:30 获得 $24$ pts。 做 T2，感觉图没用（这个是错的），转邻接矩阵，会了一个 $2^{C_n^{n/2}}$ 的做法，可以获得 $0$ pts。 尝试去重无果。到 12:50 决定不能再摆了，至少要有代码。 宣布考试延时 15min。原来 T3 样例解释是错的吗，我咋没发现。 将 $\binom{n}{k}$ 种选择搜出来，然后随机化选一堆，不管了写写写。魔改一下 checker，到 13:20 过了两个小样例和自己造的一组数据。 获得声称 $8$ pts。 出来声称获得了 $100+8+24=132$。 回来发现 T1 没判 $0$ 在首尾的情况，这下 $[25,100]$ 了。 场上造了 $2000$ 组 $n=100$ 能过，顺序倒序也能过，算了不想了，反正挂不挂分都翻不了。 最后 $75+32+8+30+28+15+12+[25,100]+[0,8]+24$。把同校估分导入 excel 算了一下。已严肃翻盘失败。 ysy 好像翻了。？！强强！？ lyh 是不是获得了 $0.4+0.3+0.3=1$ 的标准分 /bx/bx/bx 感觉这次最大的问题是 d1t1 没做出来正解，也没做出高分 dp。 之后严肃停课到 5 月，脱产 whk 进行知识点大学习。