联合省选 2026 游记

· · 生活·游记

Day -?

紧急加训哈集幂。今年是不是还要考啊。

Day 1

开题。T1 是期望题，这么恐怖。T2 是串串题……构造？恰好 k 个？什么玩意儿。T3 也是构造题，判是否有解有一半分。

看一眼三题的数据范围……5000，200/3000，250？都是高次 poly 复杂度啊。感觉不太妙。

然后立刻注意到 recollecter 有 recoll 前缀。这时，我想，看起来今年省选 Day 1 没有 bitset 题了吧，那就好。

做 T1。期望应该有线性性吧，但是这个正比于重链长度怎么处理？只能背包吧。我设计一个 DP 试试。

中间改了几次状态后，终于发现可以设 p_{i,L} 为 i 所在重链长为 L 的概率，e_{i,L} 表示此时 i\to fa_i 为重边的概率，在 i 处计算儿子的 e 值就行了。写之。

欸，我的背包怎么需要支持删除？撤销背包嘛……怎么写来着？发现原来是多项式除法，暴力除的复杂度是多少？是 siz_i\times \sum_{s\in son_i} siz_{s}=siz_i^2，那一个链不就把我卡成 O(n^3) 了？不对啊，若真的是一条链，背包撤销后根本就没有物品了，怎么会卡出 O(n^3) 呢……

不对，多项式除法的复杂度是 O(m(n-m))！我再算算……\sum siz_s(siz_i-siz_s)，就是 siz_i^2-\sum siz_s^2……欸，那总复杂度不就是 O(n^2) 吗！

这么巧妙。继续写代码，写完没怎么调就过了。这时 77min。

于是我需要选择 T2 和 T3 中的一个。瞪着 T2 的恰好 k 个，没有任何头绪，遂决定开 T3。欸 m=1 不是送的吗，写掉，获得 4\text{pts}。

然后呢？我决定开 B 性质。发现问题相当于，有一个环，一个指针，每次可以让指针移动两格，并合并经过的两个数。显然要刻画怎样的合并是可以做到的，而 B 和 C 性质相当于断环为链。我猜这个刻画是 DP。

手玩了很久，发现似乎和段长模 3 有点关系，胡了一个 B 性质的看起来很好写的做法，然后发现 C 性质咋一点思路没有。

决定等会儿再写，先看 T2，观察了一下特殊性质，做法不是很显然啊。这时忽然意识到需要 DP，大概就是考虑在原串的基础上加字符，用 dp_{pre,suf,cnt} 表示在某个前缀和后缀的状态时，有 cnt 个串的字典序 <s 是否可行。这样状态数是 O(n^2k) 的，不过似乎还需要记录串长？那是 O(n^3k)，过不去呀……等等。

我的 DP 数组的值好像都是 \color{red}{0/1}？！转移好像很规整？

bitset？！

「请注意本题特殊的时空限制。」

一个声音在我脑海里回荡。我立刻翻到题面第一页……

联合省选 2026 D1T2 摩卡串 3.00\text{s} \color{red}{2.00\text{G}}

好嘛！recall！那时我感觉 bitset 优化 DP 对完了。于是开始仔细刻画这个 DP。这时意识到 Day 1 有 3 个 DP 题，被吓到了。

中间修修补补很多次，转移愣是没弄清楚。改着改着，我发现状态数变成 O(n^2k^2) 了，过不去。这时还有 2h，时间不多了，我决定先把 T3 的 B 性质写掉。

刚准备开始写，突然感觉我的做法哪里不太对。两分钟后，我造了组数据把自己的 B 性质做法叉掉了。

坏了！ 20\text{pts} 没了！紧急思考正确的 B 性质的做法，却什么也想不出来。还有 110min，有点红温了。

搏一把！我决定 All in T2。继续修 T2 的 DP，把它优化到了 O(nk^2)，又可以 bitset 了，很好。还有 60min，开写！好难写。

欸？有多测，bitset 怎么 O(\frac{N}{\omega}) 清空来着？我试试，啊，原来 =0 就好了。

写到还有 20min，发现这题需要构造方案！赶紧想了个从 DP 数组推出构造的办法，却发现来不及写了。

这下遗憾离场了。只得打了一个 15\text{pts} 的暴力枚举，就这个也花了我 11min 的时间。

--- 下午，看题解，发现 T2 有 $O(nk^{1.5})$ 做法，很厉害啊。但是 $O(\frac{nk^2}{\omega})$ 肯定也能过呀。 ## Day $2

开题。先看数据范围，我猜 T2 是 n\le 15。

T1……交互？？仔细一看，居然不是披着交互外壳的传统题，就是正经交互。T2，图上操作，翻转团内的边……感觉很能状压 DP 一类的，不会数据范围真的是 15 吧！好吧原来是 n\le 500。

T3，像是数据结构题，数据范围 10^5 还有 4.00\text{s}，这不是我们駄作吗。这个工业系统到底在干什么？一个点把后代的输出拼成一个可重集作为自己的输出，还要比较输出的大小，这是一个自底向上递推的过程。等等，这可重集里，到底有些什么元素？这个递推的边界是什么？……对于叶结点 a_p=\color{red}\varnothing……？！

等等。

我迅速翻到样例解释。

完了！最长待机加强版！这种集合套集合套集合套……比较大小，好嘛！ 那今天的题可做在哪里呀？ 先看 T1 吧。我猜要先确定 $0$ 的位置，再确定 $1$ 的位置，再……那，倍增？二分？看一眼评分参数。$n$ 次询问？不好啊。 接着刻画了一些没用的性质。到了 40min 时，突然想起，$p$ 是排列，区间 mex 等于补集 min，就是前缀 min 和后缀 min 的较小值！那我只需要让前后缀 min 正确不就行了？直接问出来，再构造就行，于是会了 $2n$ 次询问。过了一会儿改成 $n+\log_2 n$，马上又改成了 $n$。这就过了 T1，此时 70min。 和 Day 1 的节奏很像啊！我又要决定开 T2 还是 T3 了……还用想吗？T3 那个集合套来套去，里面全是空集，我才不想研究它呢。开 T2。 --- 欸，T2 怎么首先需要最终边数最大化？这怎么算。手玩 1min 发现 $4$ 次操作可以翻转一个四元环，我猜答案和 $n(n-1)/2$ 差距不超过 $4$。看一眼大样例，不对啊。 怎么回事。这时想到奇偶性是个关键不变量，限制了最后的边数。如果 $k\bmod 4=0,1$，那么总边数的奇偶性不会变。如果 $k\bmod 2=1$，那么每个点的度数都不会变。 不妙，要对 $k\bmod 4$ 分讨！部分分里又没有 $k\bmod 4=r$ 的特殊性质啊（除了 $k=3$）！那很恶心。 先算答案。有两个限制，一个是全局边数的 $n(n-1)/2$ 减掉 $0/1$，一个是点度奇偶的 $n(n-1)/2$ 可能减去 $cnt/2$（$cnt$ 是度数与 $n-1$ 奇偶性不同的点数）。两者取较小值，是不是就对了？写，发现过不去样例 $2$。 想了一下，点度奇偶的限制如果较紧，这时要是还有全局边数的奇偶限制，答案可能要再减一。改一改，发现最后一组数据过不去，$n=18$，答案 $150$ 我输出 $152$。 哦，我知道了。当全局边数奇偶性与 $n(n-1)/2$ 不同时，会强制少 $1$ 条边。这时如果还有点度限制，要求是所有点度数奇偶与 $n-1$ 相同，那么点度限制虽然给出的边数上界是 $n(n-1)/2$，但是少 $1$ 条边取不到上界时，就至少要少 $3$ 条边。 再改。这次过了所有样例，看来我的结论应该对了，得到 $25\text{pts}$。这时比赛过去了 100min。 于是开始尝试构造。感觉 $p=n(n-1)/2$ 的限制好严格啊。但是没有这个限制，我也不会构造，怎么回事呢？ 很久没有任何进展，比赛来到 150min。这时我觉得不能再无谓的浪费时间了。我决定和 T3 的集合套硬刚。 --- 一上来当然还是挑软柿子捏，先做特殊性质。B 是树随机啊，那肯定要做 A 性质，菊花图。想来应该是个分讨，分讨规模未知。$m=1$ 估计也不难，$m=2$ 我就不清楚了。 不过还是要搞清楚，这个集合，或者说树，是怎么比大小的？递归定义真的很恶心不是吗。 那我从简单的开始，最小的树是什么？很快就发现了，是一个结点的树。第二小的呢？应该是长度为 $2$ 的链。简单证明了一下自己的结论。 这时我突然想到，深度较大的树，其集合是不是一定更大？感觉很对，我很快给出了一个归纳证明。看着草稿纸上一行又一行工工整整的性质、结论，我感到安心多了——**分析在稳步推进着**。 继续分析，如果两棵树深度相等，如何判断哪棵树更大？思考了一会儿，发现这就很麻烦了。分析到这里卡住了，我找不到合理的刻画。时间还剩约 2h。 我决定先拿点分使自己冷静下来。先前分析的性质让我立刻看到 $m=1$ 就是送分。显然根节点一定是最大的子树，所以答案是 $|X\cap Y|$，$X,Y$ 都是树上路径，那我直接重剖……等等，$X,Y$ 的 $s,t$ 是同一组？那不就是两点间距离嘛。但是我还是写了树剖求 LCA。$4\text{pts}$。 然后是菊花图。分讨并不复杂，很快我又拿到 $4\text{pts}$。 做完这部分，当我继续回头研究树的比大小时，我突然想：既然我找到了最小、第二小的树，何不看看第 $3$ 小、第 $4$ 小的树是什么？ 边想着，我翻动题面 PDF，试图通过样例解释找找灵感。突然，我仿佛看到了什么怪物，全身突然僵住了，眼睛直瞪着那一大堆 $\varnothing$—— $a_{1,1}=\{\varnothing,\{\varnothing\}\}$？ 不应该是 $a_{1,1}=\{a_{1,2}\}=\{\{\varnothing\}\}$ 吗？$1$ 的所有后代是 $2,3$？等等。 欸？我**读错题**了！是**所有后代**，不是**所有儿子**，组成的可重集！！ 不妙。转念一想，刚才我不是过了测试点 $1,2$ 的样例吗？我用正确的定义去修正先前分析出的结果，发现没有什么需要修改的地方。 这时，我做出了一个非常大胆的猜测：如果把设备生成产物的定义中，**所有后代**改成**所有儿子**，那么子树比大小的结果应当**没有任何影响**。 约 5min 后，我（不甚严谨的）证明了这是正确的。情况逐渐明朗起来。 这时我却发现样例 $2$ 中的 $a_{1,1}$ 和 $a_{1,3}$ 和我算出的不一样。反复确认题意后，我估计是题面出现了错误，决定不再管它。 --- 回到分析的正途。第 $3$ 小、第 $4$ 小的树是什么？原来是一个结点挂有 $2,3$ 个儿子。那第 $k$ 小的树就是一个结点挂 $k-1$ 个儿子。很快我也证明这是对的。这时我想，考虑一个长为 $3$ 的链，她是第几小的树？显然她比所有深度为 $2$ 的树都要大。 我知道了——她是第 $\color{red}\omega$ 小的树。 最长待机，正式开始了。接下来的事情将十分烧脑，但我已经准备好了。 继续画深度为 $3$ 的树。在第 $\omega$ 小的树的根旁边挂一个结点得到 $\omega+1$，挂 $k$ 个结点得到 $\omega+k$。一个结点挂两个长为 $2$ 的链得到 $2\omega$，同理生成 $m\omega+k$。有一棵树形如 $(1,2),(2,3),(2,4)$，$1$ 为根，我意识到，她是 $\omega^2$。 增长速度远比我想象的快啊。不久我就搞定了 $\text{poly}(\omega)$ 的刻画，然后发现，长为 $4$ 的链，她是 $\omega^{\omega}$。 这就糟了。原来在根上方加一个点，就是 $x\to \omega^{x}$。如果要存下每个子树代表的 $\omega$ 的式子，是非常困难的。 好在我只需要比大小。我发现，如果 $x<y$，她们被放到 $\omega$ 的指数上去后，$x$ 就再没有超越 $y$ 的机会了。这时我又提出一个猜想：不需要存式子，只需存深度相同的结点的排名。 这样就好做了！产物的大小比较可以简单的用 $(len,rnk)$ 对，$len$ 是深度，$rnk$ 是排名。很快我意识到，单次询问可以做到 $O(n\log n)$ 了，有 $16\text{pts}$。 D2T3 的 $16\text{pts}$ 是多么珍贵！立刻开写。写代码过程中，样例 $2$ 被勘误了，那个 $a_{1,1}$ 和 $a_{1,3}$，题面果然写错了。 不算难写，调了调也就对了。这时还有不到 1h，我该干什么？尝试优化这个 T3 的暴力，却发现过于困难。回头看 T2。感觉我已经燃尽了，还有分可拿吗？ 最后半小时，突然想到，可以递归构造，每次完成一个点，将其从图里去除即可，不过很多细节我想不清楚，而且操作次数似乎太多了。但是我注意到 $k=3$ 是容易写的，于是又获得 $9\text{pts}$。 只有 15min 了，恐怕真的结束了吧。什么？ 加时 15min？！ 这下又有劲了。想了一会儿，我认为自己找到了 T2 $2n^2+o(n^2)$ 次操作的构造。由于需要对 $k\bmod 4$ 分讨，代码十分难写，并且我发现，暴力维护 $O(n^2)$ 对点对之间是否有边，会 TLE 呀？怎么办。看了一眼 grader…… **bitset？！** 又来！可惜最后还是写不完了。 $100+34+24=158$。 ## 后续 Day $2$ 下午，看到了 D1T3 的题解，学习之。 确实是个 DP……什么？ **bitset？！**