SHOI2026 游记

· · 生活·游记

Day 0

怎么明天就省选了。我怎么连蓝题都不会做。

Day 1

我们机房的压缩包炸了，集体加时 20\rm{min}。

约 $08:53$ T1 方向差不多搞清楚了，开始推式子。 约 $09:25$ 差不多推清楚了，但是怎么要求 $O(n)$ 次 $O(n)$ 项的多项式乘法。啊？这能做？ 约 $09:27$ 继续推式子尝试找到优化。 约 $09:40$ 我怎么不会。完了。 约 $10:00$ 这怎么做。我不信 CCF 机子能 $O(tn^2 \log n)$ 跑过 $t=5,n=5000$。 约 $10:10$ 不管怎么说先把暴力代码写好了。 $10:30$ 认真分析时间复杂度，意识到暴力的代码实际复杂度 $O\left(\sum\limits_x\sum\limits_{i \in \mathrm{son}_x} \mathrm{size(subtree}_i) \times \left(\mathrm{size(subtree}_x)-\mathrm{size(subtree}_i)\right)\right)$ 实际上是 $O(n^2)$ 而不是 $O(n^3)$。 $10:32$ 开始调 T1 代码。 约 $11:15$ 终于调完了，我怎么代码编辑距离为 $4$ 但是莫名其妙调了这么久。 $11:20$ 比赛过半，我才 $100\mathrm{pts}$，没救了。决定去看看 T3。 约 $11:40$ 通过爆搜意识到 T3 等价于循环移位后将某些相邻段合并，但是不确定怎么合并。 约 $11:50$ 打表找规律无果，回去做 T2。 $13:10$ T2 随便写了 ABC 性质，但是怎么都快没时间了。我怎么还虚空调试了半小时，编辑距离为 $2$。D 性质怎么做。回去打 T3。 约 $13:30$ T3 再次找规律无果，开始写暴力。 $13:49$ 暴力写完。***预期***能过 $m=1$ 和 $n,m \le 16$。 $13:50$ 发现自己代码多打了两个字符，荣获 CE，同时比赛结束，死了。 $100+45+12=157 \to 100+45+0=145$。不管怎么说我都死了。操。 在考场猜测题目难度为绿紫黑并意识到我是傻逼。 ## Day 2 $08:30$ 开 A。 $08:31$ 意识到这场是构造专场，并发现怎么有函数式交互题。 $08:33$ 想到二分。 约 $08:50$ 研究性质，没研究出来。感觉二分是错的。 约 $09:25$ 意识到 mex 就是前后缀最小值。 约 $09:35$ ***决定用二分优化前后缀最小值。*** 约 $10:00$ ***二分写好，调完，发现随机数据过不去，开始乱搞。*** 约 $10:30$ ***乱搞通过了自己造的 hack，并通过了对拍。*** 约 $10:35$ 感觉 T2 太诡异，而且发现下发 PDF 上写着 T2 传统题。决定先想想 T3。 约 $11:10$ 不敢继续想 T3 了，发现太抽象，回去做 T2。 约 $11:15$ 发现 T2 和 $k$ 的奇偶性有关，但是不知道怎么办，试图骗分但是失败了。 约 $11:20$ 停止骗分，开始想正解。 后面我在认真构造所以我也不清楚什么时候想出来的了。 约 $13:23$ 快写完了但是还剩 $6\rm{min}$ 结束，心态崩了。此时突然因 T3 样例问题加时 $15\rm{min}$，爽！ $13:41$ 发现自己 $k=3$ 的情况炸了（样例 4），心态再次崩掉。 $13:44:46$ $3\rm{min}$ 疯狂写了 $1\rm{KB}$ 代码修复 $k=3$。 $13:44:57$ 样例 4 跑出来了，过了！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！ $13:45:00$ 比赛结束。 估分 $100+100+0$。 ## Day 2.5 真的吗？估分 $100+45+0+100+100+0=345$？ 真的吗？ 真的吗？ 卧槽我怎么 D2T1 假了。我为什么要用二分来***优化***，直接做明明是 $n$ 次操作我用二分变成了 $O(玄学)$。 看了一眼洛谷，我做出的 D1T1、D2T2 分别是紫、黑，而 D2T1 是蓝。 然后再看一眼我在赛前写在游记 Day 0 的那句话。 > 怎么明天就省选了。我怎么连蓝题都不会做。 操。 ## Day 3 我操。我是傻逼。我 D2T2 分讨太多结果漏了 $2 \nmid k,k=n-2$ 的最终调整。他妈的我要是因为这个炸了我就是纯傻逼。 注意到 $(3,u),(3,v),(3,w),(3,t)$ 可以调整 $(3,u),(u,w),(w,t),(t,3);(3,v),(v,u),(u,w),(w,3)$ 变为 $(u,v),(w,t)$。但是我他妈分讨的时候漏了这种情况。 操。