联合省选 2025

· · 生活·游记

day 0

前往北碚，试机。

发现有许多的键盘都是跷跷板，有一些是可以修复的，还有一些是不可修复的（（

然后回家摆，板子是不会复习的，CCF 比赛的模板含量越来越少了。

选择了在健康的时间睡觉

day 1

上来 t1，观察到了离散化，观察到了枚举中位数，并没有观察到 所有 l_{i,1}\leq x\leq r_{i,1} 都必须选 x 这个搞笑性质！于是开局 15\text{ min} 才开写！并没有复刻 noip 2024 的唐诗经历（

然后是 t2，这不是我们 DAG 可达性判断吗？这不是我们 O(n^2/\omega) 巨大空间吗（，然后开始思考特殊性质，发现没有修改的情况还是比较简单的，可以直接分块，然后突然发现欸我再套上一个定期重构不就没了？然后敲了下计算器发现这个做法重度卡常！但是依旧能获得比较多的分数于是开写。

写完发现要跑 12s 直接爆炸，但是别急，首先将原 DAG 直接拆成边集来跑（10s），然后将定期重构跟分块的块长拆开（9s），然后进行一堆玄学卡常与调参（7s）。

最关键的一步：回到虚拟机外面进行测试，获得了 5.7s 的好成绩，不想继续卡了于是先看 t3

t3 观察到 B 性质是容易构造的，A 性质可以直接将所有连通块的方案进行贪心拼接，于是开始查看 C 性质！

首先通过观察大样例可以得知一个连通块的 \min 是一定可以排在最开头的，不妨设其为根，那么接下来每一个子树都会占领答案序列的一个区间段，直接求出每个子树中最小值然后排序填入即可！

然后考虑出题人都这样给特殊性质了那我们考虑前向边带来的影响，大致是说一个路径 u\to k_1\to k_2\to\cdots\to k_m\to v，如果有 u\to v 这条前向边，则 k_1\to k_2\to\cdots\to k_m\to v 这所有的边，要么全部都在父亲处排列在第一个位置，要么是全部最后一个位置！

那么我们怎么知道这个性质是否正确呢？观察到数据保证有解，我们直接把样例拿过来 assert 一下就行了（

但是考虑有特判，当你一个节点有 \geq 2 个儿子有排列需求的时候需要保证这些节点不能同时最左或最右。

但是考虑还有特判，当你出现类似这样的路径时：u_1\to\cdots\to u_2\to v_1\to\cdots v_2 的时候（u_1\to v_1,u_2\to v_2），看似会有前向边交叉的情况，但是根据超级良心小样例我们得知存在构造方案：u_1,\cdots,u_2,v_2,\cdots,v_1，容易观察到这个构造方案需要保证 u_2\to v_1 这条边与后方的边方向相反，而且也观察到当前向边交叉的长度太长的时候是无解的，于是这就成为了唯一一个特判了！

最终写法可以直接写扩域并查集与树形 dp 维护当指定一条边方向时子树的最优方案（的第一个数），比较难写。但最终还是有惊无险调出来了。还剩 30\text{ min}。

测了几发极端情况就去卡 t2 常，然而非常遗憾的是并没有找到跑得更快的写法。

day 2

开 t1，观察到 abc g，遂写了个线段树，20\text{ min}，鉴定为 d2t1 < d1t1 < noipt1！

然后开 t2，发现最小树形图，但是发现求最小树形图的算法根本套不上去，然后暴力 A 性质把 m\leq6 看漏了以为自己暴力都不会写，半个小时过去了于是先看眼 t3。

t3 考虑反向操作是完全没有前途的，于是先考虑每一次都把第一个数挪到最后，形成一个序列，然后在这个序列上计数，那么除了每一个可以达成的区间需要算入答案，每一个区间还可以选一个子集算入答案，感觉 n\leq18 稳了啊，于是回去看 t2 了。

t2 经过了若干尝试终于发现了有向图缩点后是一个只有唯一一个根的 DAG 这个关键性质！那这不是我们主旋律吗？然后计算答案只需要枚举根强连通分量，然后只需要保证其他的强连通分量都有入度即可，直接算一下就是 O(3^n)，获得 C 性质。B 性质的外向树只有 n 直接容斥但实际上点边容斥即可，但是到现在还是不会 A，比较迷惑，去看 t3。

然后观察到，如果固定区间，一个选数集合是合法的，当且仅当所有的没有被选的数，要么是区间开头连续的 1（可以任意删去），要么其不属于最开始的数组（根本删不掉）并且该数后方第一个选择的数是严格大于它的。然后模拟一下第三个样例，发现怎么直接算对了？？？？？？？？然后仔细分析发现如果考虑所有方案的单调数据结构，可以发现所有的区间的这个结构都是不同的，所以所有的方案都是不同的？？？？？？？？？然后写了个 O(n^4) 发现直接过完大样例了？？？？？？？前缀和优化下变 O(n^3) 直接获得大把分数了，不是那我问你中间那么多点拿来干啥用的？？？？？？？？？？？

有点抽象，查看 t2，发现 m\leq6，然后就是纯粹暴力了。然后就写了下 t2 的 AB，再补了 t3 的 B，但现在时间不多了，t2 的最小生成树计数状物不像是能写出来的了，然后 t3 企图使用若干方法优化无果，然后就结束了。

day 3~5

欸这个 whk 怎么这么坏的啊（

day 6

小挂了 12pts，赢。