题解 | #E-G#

出题人题解 Part II(E-G)

E 奇环

题解

二分图，鸽巢原理。

没有奇环的图被称为二分图。

假设一个图没有奇环，那么将它视为二分图，并分为左部右部，假设左部 $n_{1}n\_1$ 个点，右部 $n_{2}n\_2$ 个点，那么它最多有 $n_1\times n_{2}n\_1\; \backslash times\; n\_2$ 条边。

若题目中给定的图没有奇环，应满足：

• $n_1+n_2=nn\_1\; +\; n\_2\; =\; n$
• $\frac{n\times (n-1)}{2}-m\le n_1\times n_2\backslash frac\{n\; \backslash times\; (n\; -\; 1)\}\{2\}\; -\; m\; \backslash leq\; n\_1\; \backslash times\; n\_2$

结合基本不等式，解得 $m\ge \frac{n^2}{4}-\frac{n}{2}m\; \backslash geq\; \backslash frac\{n\; ^\; 2\}\{4\}\; -\; \backslash frac\{n\}\{2\}$，再结合题中的数据范围，当 $n\ge 896n\; \backslash geq\; 896$ 时，由于 $m\le 2\times 10^{5}m\; \backslash leq\; 2\; \backslash times\; 10\; ^\; 5$，该不等式无法满足，即图中必然存在奇环。

否则，当 $n\le 895n\; \backslash leq\; 895$ 时，使用一个经典的 DFS/BFS 染色算法即可在 $O(n+m)O(n\; +\; m)$ 的时间内完成奇环的判定。

代码

代码 - XLor Paste

F 座位

题解

有两种做法，第一种做法基于期望的线性性质，第二种做法基于动态规划。

做法 1：

首先需要观察一下这件事情的规律，我们考虑第 $ii$ 个人进来时的情况：

1. 前 $i-1i\; -\; 1$ 个人坐在了前 $i-1i\; -\; 1$ 个椅子上，此时 $ii$ 可选的位置是 $ii$ 和 $i+1i\; +\; 1$。
2. 第 $i-1i\; -\; 1$ 个人坐在了第 $ii$ 个位置上，此时 $ii$ 可选的位置是 $1\to i-11\; \backslash rightarrow\; i-1$ 中的某个位置和第 $i+1i\; +\; 1$ 个位置。

不论是以上哪一种情况，如果第 $ii$ 个人不选择坐在第 $i+1i\; +\; 1$ 个位置上，那么 $ii$ 坐下之后前 $ii$ 个人就将坐在前 $ii$ 个椅子上，这件事发生的概率是 0.5。

考虑第 $i(2\le i<n)i(2\backslash le\; i\; \backslash lt\; n)$ 个人坐在第 $ii$ 个位置上的概率，是前 $i-1i\; -\; 1$ 个人坐在前 $i-1i-1$ 个位置上的概率，乘上，第 $ii$ 个人选择第 $ii$​ 个位置的概率，等于 0.25。$i=1\mathrm{、}ni\; =\; 1、n$ 情况特殊，特别考虑，它们坐在自己位置上的概率是 0.5。

根据期望的线性性质，答案 $E(x)={\sum }_{i=1}^{n}E(x_i)E(x)\; =\; \backslash sum\backslash limits\_\{i\; =\; 1\}^n\; E(x\_i)$，其中 $E(x_i)E(x\_i)$ 表示第 $ii$ 个人坐在第 $ii$ 个椅子上的数量期望。

因此答案为即 $\frac{1}{2}+\frac{n-2}{4}+\frac{1}{2}\backslash frac\{1\}\{2\}\; +\; \backslash frac\{n\; -\; 2\}\{4\}\; +\; \backslash frac\{1\}\{2\}$，$n=1n\; =\; 1$ 时特判输出 1。

补充说明：可能有读者会疑惑为什么 $E(x_i)E(x\_i)$ 表示第 $ii$ 个人坐在第 $ii$ 个椅子上的数量期望，却在数值上等于第 $ii$ 个人坐在第 $ii$ 个椅子上的概率，因为：

做法 2：

考虑动态规划，$d{p}_{i}dp\_i$ 表示 $n=in\; =\; i$ 时的答案。

考虑 $d{p}_{i}dp\_i$ 从何转移而来，一个经典的想法是：枚举 $ii$ 所在的环的大小 $jj$。

因为 $ii$ 是最后一个人，所以它的位置是唯一确定的，不失一般性考虑 $j=2j\; =\; 2$ 的情况：

如果 $j=2j\; =\; 2$，那么说明第 $i-2i\; -\; 2$ 个人走进来坐在了 $[1,i][1,\; i]$ 某个位置上，终止了它所在的环，这件事的概率是 $\frac{1}{2}\backslash frac\{1\}\{2\}$。第 $i-1i\; -\; 1$ 个人走进来坐在了第 $ii$ 个位置上，这件事发生的概率也是 $\frac{1}{2}\backslash frac\{1\}\{2\}$。这样，第 $ii$ 个人就坐在了第 $i-1i\; -\; 1$ 个位置上，与第 $i-1i\; -\; 1$ 个人形成了大小为 $j=2j\; =\; 2$ 的环。

我们得到了一个转移 $d{p}_i\leftarrow \frac{1}{4}d{p}_{i-2}dp\_i\; \backslash leftarrow\; \backslash frac\{1\}\{4\}\; dp\_\{i\; -\; 2\}$。

类似地把 $j=1\to i-1j\; =\; 1\; \backslash to\; i\; -\; 1$ 都考虑进来，就会得到 $d{p}_i=\frac{1}{2}(1+d{p}_{i-1})+{\sum }_{j=2}^{i-1}\frac{1}{2^j}d{p}_{i-j}dp\_i\; =\; \backslash frac\{1\}\{2\}(1\; +\; dp\_\{i\; -\; 1\})\; +\; \backslash sum\backslash limits\_\{j\; =\; 2\}^\{i\; -\; 1\}\; \backslash frac\{1\}\{2\; ^\; \{j\}\}\; dp\_\{i\; -\; j\}$。

观察这个和式，$d{p}_{i}dp\_i$ 可以从 $d{p}_{i-1}dp\_\{i\; -\; 1\}$ $O(1)O(1)$ 地转移过来，因此做到了线性的复杂度。

具体地，会推出当 $i\ge 2i\; \backslash ge\; 2$ 时，$d{p}_i=d{p}_{i-1}+\frac{1}{4}dp\_i\; =\; dp\_\{i\; -\; 1\}\; +\; \backslash frac\{1\}\{4\}$。

补充说明：可能有读者会疑惑上式如何化简，如下给出推导：

G

题解

本题在赛时出现了比原题解做法更优秀的 DP 做法，于是先放上 DP 做法。

做法1：

对于操作，我们会发现如果交换两个 0 或者交换两个 1 是没有意义的，因此一定是交换 01 或者 10，也可以视为某一个 1 在 01 序列中移动了一个单位距离。

转换一下题意，考虑将所有 1 分配到 $nn$ 个位置中的若干个位置，使得分配的位置不存在相邻的情况。

那么可以考虑如下 DP，$f_{i,j,0\mathrm{/}1}f\_\{i,j,0/1\}$ 表示考虑了前 $ii$ 个位置已经放了 $jj$ 个 1，第 $ii$ 个位置放的是 0/1。

那么考虑 DP 的转移：第 $jj$ 个 1 是否放在第 $ii$ 个位置（记第 $jj$ 个 1 的位置为 $po{s}_{j}pos\_j$）。

• 放：则从第 $jj$ 个 1 所在的位置移动到 $ii$，需要的交换次数为 $\mathrm{\mid }po{s}_j-i\mathrm{\mid }|pos\_j\; -\; i|$。有 $f_{i,j,1}=f_{i-1,j-1,0}+\mathrm{\mid }po{s}_j-i\mathrm{\mid }f\_\{i,j,1\}\; =\; f\_\{i\; -\; 1,j\; -\; 1,0\}\; +\; |pos\_j\; -\; i|$。
• 不放：则有 $f_{i,j,0}=\min (f_{i-1,j,0},f_{i-1,j,1})f\_\{i,j,0\}\; =\; \backslash min(f\_\{i\; -\; 1,\; j,\; 0\},f\_\{i\; -\; 1,\; j,1\})$。

复杂度为 $O(n^2)O(n^2)$。

做法2：

费用流。

换一个视角看这个问题，把 0 看成水，1 看成装水的容器壁（先不考虑最左、最右边的 0）如下图表示 10011001 的视角。

那么不存在两个相邻的 1 即可被视为不存在某个容器里面没有水（蓝色的 0 表示水，黑色的 1 表示容器壁）。

对于操作，我们会发现如果交换两个 0 或者交换两个 1 是没有意义的，因此一定是交换 01 或者 10。在这个视角下，交换 01 或者 10 即将一个水从一个容器，移动到一个相邻的容器。

对此我们建立费用流模型，每个容器视为图的一个节点，设第 $ii$ 个容器初始时有 $v_{i}v\_i$ 的水，总共有 $VV$ 的水（即 01 序列总共有 $VV$ 个 0）。

• 超级源点指向第 $ii$ 个容器连一条容量为 $v_{i}v\_i$、单位费用为 0 的边。
• 第 $ii$ 个容器指向超级汇点，连一条容量为 1、单位费用为 0 的边。
• 第 $ii$ 个容器分别向第 $i-1,i+1i\; -\; 1,~i\; +\; 1$ 个容器连一条容量为 $VV$、单位费用为 $11$ 的边。

这样，在最大流基础上得到的最小费用，就是本题的答案。

若 SSP 算法求解，使用 Bellman-Ford 算法寻找最短路，那么可以得到一个最坏复杂度 $O(nmf)O(nmf)$，在本题为 $O(n^3)O(n^3)$，但远远跑不满。

代码

代码 - XLor Paste