题解：AT_arc190_e [ARC190E] Gaps of 1 or 2

· · 题解

目前两篇题解各有一些比较含糊的地方，我融合了一下。

一般图最大匹配有个类似 Hall 定理的结论。

定义 o(V) 表示子图 V 中连通块大小为 奇数 的连通块个数。

对于图 G(V,E)，最大匹配能如下表示：

\dfrac{1}{2}\left(|V|-\max\limits_{S\sube V} (o(V\backslash S)-|S|)\right)

被称作 Tutte–Berge 公式 。

发现形式和 tuttle 矩阵很像，于是证明大概是 tuttle 矩阵那套，但是我不太会，可以查看上述链接。

先做全局，建立图论模型：把一个点拆成 a_i 个点，然后距离 \le 2 的所有连边，答案是最大匹配。

套用结论，分析 S。

发现对于一个 i，看着 a_i 要么全在 S，要么全不在。

证明是若选了 1\le x<a_i 个在 S 中，少掉一个能使 -|S| 增加 1。

并且 o(V\backslash S) 最多减少 1，于是选 x-1 个一定不劣。

若 x=a_i 则 x-1 会影响连通性，对 o(V\backslash S) 的影响就不一定了。

于是我们考虑 01 序列 s，s_i=0/1 表示位置 i 全不选或全选。

则答案为奇 0 连通块个数减所有 1 位置的 a 的和，要找这个的 \max。

发现可以设计 dp。请注意我下面当前和钦定的用词。

设第 i 位的状态 f_{i,0/1/2/3/4} 分别是：

当前单 1 能转移到当前多 1，但是钦定单 0 无法转移到钦定多 0。

这是为了算贡献方便。

你发现不如把它变成 000。

因为 -|S| 增加 a_i，奇连通块个数最多减少 1 个。

若 a_i=0，则奇无法拆成两个偶，于是恰好减少 0 个。

否则 a_i\ge 1，一定不劣。

于是你就可以设计转移矩阵了，矩阵乘法是 (\max,+)，转移要分 a_i 奇偶讨论。

若 2\mid a_i：

[f_0 , f_1 , f_2 , f_3 , f_4]\begin{bmatrix} -\infty & -a_i & -\infty & -\infty & -\infty \\ -\infty & -a_i & a_i & 0 & -\infty \\ -a_i & -\infty & -\infty & -\infty & -\infty \\ -a_i & -\infty & -\infty & 0 & -\infty \\ -a_i & -\infty & -\infty & -\infty & 0 \end{bmatrix} = [f'_0 , f'_1 , f'_2 , f'_3 , f'_4]

若 2\nmid a_i：

[f_0 , f_1 , f_2 , f_3 , f_4] \begin{bmatrix} -\infty & -a_i & -\infty & -\infty & -\infty \\ -\infty & -a_i & a_i & -\infty & 1 \\ -a_i & -\infty & -\infty & -\infty & -\infty \\ -a_i & -\infty & -\infty & -\infty & 1 \\ -a_i & -\infty & -1 & -\infty & -\infty \end{bmatrix} = [f'_0 , f'_1 , f'_2 , f'_3 , f'_4]

初始钦定 l 左边有 \infty 个 1，不影响答案。

于是初始 f=[-\infty,0,-\infty,-\infty,-\infty]。

线段树维护区间矩阵乘积，总复杂度 \mathcal{O}(k^3 (n+q \log n))。

但是发现查询的时候只需维护向量乘矩阵，于是复杂度变成 \mathcal{O}(nk^3+qk^2 \log n)。

代码跑挺快的。

\bf{record}