联合省选 2025 游记

$100 + 44 + 52 + 100 + 64 + 8 = 368$。

回四川过完一个开心的春节后来到南京集训。

在某核桃训练了一周左右，然后在南外待到省选前。

晚上没睡好，早上起来困似了，大概是靠咖啡清醒过来的。

进场。键盘怎么是跷跷板，赶紧换了一个。浏览了一下题面，看起来 T1 可能挺签到，T2 有点抽象，T3 看完感觉性质 C 有点头绪。

T1 很快发现中位数要尽可能多的选，然后两侧尽可能接近就行了。没花多少时间过了 T1。T2 首先不弱于 DAG 可达性阿，然后咋办来着。想了半天还是没什么进展，于是转战 T3。没过多少时间发现 T3 性质 C 好像不难，子树之间是非常独立的，那么显然就是按子树内编号最小的点排序之后做就完了。花了一点时间写了个链表状物过了大样例。然后森林那就是每次可以选一个序列完整地插入到另一个序列里，继续用链表维护就行了。中间写假了一次，最后没过多久通过了大样例。

尝试做 T3 更多的分，但是好像发现不了什么聪明的做法，权衡了一下选择了去做 T2。但是我 T2 真的啥也憋不出来啊/ll。最后写了一个稍微卡了一下的 bitset 暴力跑路。

相信明天。

起来还是有点困，继续喝咖啡。

进场。键盘咋又是跷跷板。浏览题面，T1 看完感觉直接贪全对吧，然后看到 T2 T3 两个计数感觉看到了希望。

T1 想了想实现发现可以 a[i] -= i，这样会好写一些，很快写完了。然后去想 T2 C 性质，很快发现可以用缩点后的 DAG 只有一个零度点来刻画原问题，那么直接求强连通子图是不是就行了，最后有一个容斥系数为 $(-1)^{i - 1}i$ 的容斥。写了一会儿调了一会儿就过了 C 性质。

然后接下来犯唐了，我以为一边容斥 DAG 一边还要保证最小外向生成树的大小正确是很难的事情，实际上只需要考虑从小到大加入所有的边，则每个连通块分别满足其缩点后 DAG 只有一个零度点，然后每一层都做一遍 C 性质，每次保留 DP 数组的相应项应该就 $\Theta(3^n \mathrm{poly}(n))$ 了。但是考场上还是倒在了这一步之前。经过无谓的挣扎，最后这题 $64$ 分收场了。

在给 T2 挣扎的过程中顺便做了下 T3，特殊性质 AB 我的刻画太笨了，同时因为我考场上有点红温所以这题最终 $8$ 分离场了。

感觉用一句话描述一下，我这次也只是做到了避免打出下限级发挥。不那么令人满意的地方在于，D1T2 大寄，D2T2 和 D2T3 两道擅长的题型也没发挥完全。D2T2 那个更进一步的性质，只是在考试结束后冷静了一会儿就成功想通了，如果考场上别那么急感觉还是有机会 $100$ 的。

在 SN 进个 A 队大概是没问题了，不过不管是从分数上看还是从发挥上看我离认知中的大神们还是有相当一段距离的。这段距离肯定是要付出相当量级的训练才足以弥补了，但是至少在 NOI 2025 之前，希望自己能够尽人事。

未来，会是什么样的呢？