初一彩笔大战 SHOI2025 拼尽全力无法战胜，后面忘了

· · 生活·游记

前情提要：NOIP 有一等，终于可以混个省选打了。

幽默模拟赛。成功在信心赛中打出了比平时还低的分，呃呃呃。

学长在社团课讲了主旋律但是我没听。（埋下伏笔）

极限在开场几分钟之前到。提前 3min 发了试题。

看了看 t1，感觉极其可做。主要是怎么判定一个数能否成为中位数。这个随便做一做即可。甚至意识到了答案是连续区间，但是我的做法除开离散化已经是线性的了。

写了写，微量调试后直接过了所有样例。比较唐的是我这么简单的东西用了接近 1hr。/wul

开 t2 感到一股 Ynoi 的味道。首先有向图可达性问题只会让你在考场上做出两种选择：挑战图灵奖；或者老老实实 \dfrac{n^2}{w}。明显我选择后者。

然后继续考虑。想到可以用限制层数的线段树合并做个 nq 除以不知道多少。但是当时的我开始作死，写了一个 nq 的东西上去。由于大量使用假做法冲 Ynoi 题的经历，我选择把这个分成三块处理。前两块分别对应了 [l,r] 很小的情况和联通数很小的情况，最后一块用了随机均摊极快的倒着扫的策略。极限大概是 \dfrac{nq}8，搞笑的是这个东西的极限反而是随机图。发现跑不过 10^5。改了一会做到了 8\times10^4 跑了 5s，感觉可以扔掉了。

留了 1hr 想 t3，但是此时精神状态极其差。于是连树都没想出来，怒砍 8pts。检查了一下文件就滚了。

t1 也是签，直接 1hr 做完就扔掉了。

然后开 t2，发现只用判定是否存在的 C 给了很多分。然后想了想根据生成树的特点可以按边权拆开，和 C 性质是一样的。

然后开始思考 C 性质。完了不会啊。

于是先把 t3 中有序的点写了，再写了实测跑得飞快的 n \le 18。

回来想 t2。把这个图按强连通拆开，不是就要求外面的是 dag 吗。这不就是主旋律。

woc，但是我想不出来主旋律怎么写了。糖糖糖糖糖。

想了半天，最终打了 24pts 遗憾离场。

成绩极差，回归 whk。

upd：疑似是 SHrk15~16，寄了。

upd on 3.6：d1t2 lg 过了，鱼鱼乐

擦线进了 E，抽象。