牛客练习赛106题解

（代发，原出题人：yingluosanqian ）

赛况

• A题：1116/1164 通过率：95.88%
• B题：909/1164 通过率：78.09%
• C题：747/1164 通过率：64.18%
• D题：306/1164 通过率：26.29%
• E题：96/1164 通过率：8.25%
• F题：103/1164 通过率：8.85%
• G题：35/1164 通过率：3.01%

A 三子棋

题面简述

给定一个 $3\times 33\; \backslash times\; 3$ 的棋盘，共有 $3\times 3=93\; \backslash times\; 3\; =\; 9$ 个格子，初始时每个格子均没有放置棋子。

A 和 B 轮流行动，每次行动的人，必须在当前棋盘上选择一个没有放置棋子的格子，然后在该格子放置一个棋子。

若某棋手放置一个棋子后，该棋子与另外两个棋子（不论是谁放置的都可以）达成三子连珠（即三个棋子连成一条线，水平、垂直、主副对角线均可），则该棋手获胜。

A 总是先手。

请判断，若 A 将第一个棋子放置于格子 $(x,y)(x,\; y)$ 后，是否 A 最终会获胜（A，B 总是采取最优策略）。

下标从 1 开始，处在第 $xx$ 行、第 $yy$ 列的格子坐标为 $(x,y)(x,\; y)$。

题解

简单博弈。

我们称 ”A 将第一个棋子放置于格子 $(x,y)(x,\; y)$ 后，A 最终会获胜“ 这样的格子 $(x,y)(x,~y)$ 为 ”先手必胜的“。

手玩后发现，每一个格子都先手必胜。

首先，显然中间格子先手必胜。

接下来说明四个角也是先手必胜的：

不失一般性，设 A 先在左上角落子，接下来，倘若 B 在上图中淡红色位置落子，那么 A 必然可以下一步达成三点共线，因此 B 只能于其中一处淡蓝色位置落子，紧接着 A 在另一处落子则可获胜。

接下来说明四个边上的点也是先手必胜的：

不失一般性，设 A 现在第一行第二列落子，接下来，B 只能在 X，Y，P，Q 处四选一落子。若 B 在 X 处落子，则 A 接着在 Y 处落子则获胜，反之亦然，P，Q 同理。

代码

#include<bits/stdc++.h>

using namespace std;

int main() {
	
	cout << "YES\n";
	
	return 0;
}

B 药丸

题面简述

牛牛有 $nn$ 个属性，第 $ii$ 个属性的初始值为 $a_{i}a\_i$ ，牛牛想把第 $ii$ 个属性的值变为目标值 $b_{i}b\_i$。

现在牛牛 $2\times n2\; \backslash times\; n$ 种不同颜色的药丸，吃一个药丸会产生一个效果。同种颜色的药丸效果相同，不同颜色的药丸效果不同。

每种颜色的药丸对应以下效果之一：

• 第 1 个属性值 + 1
• 第 1 个属性值 - 1
• 第 2 个属性值 + 1
• 第 2 个属性值 - 1
• ......
• 第 n 个属性值 + 1
• 第 n 个属性值 - 1

以上描述了 $2\times n2\; \backslash times\; n$ 种效果，它们与 $2\times n2\; \backslash times\; n$ 种颜色的药丸一一对应。

开始时牛牛并不知道药丸颜色与药丸效果的对应关系。若牛牛吃一个药丸，则会获得该颜色药丸对应的效果，并且知道该颜色的药丸对应的效果。

牛牛通过吃药丸来改变自己的属性值。求在最坏的情况下，牛牛要吃多少药丸才能将所有属性从初始值变为目标值。

题解

思维。

若 $aa$ 数组与 $bb$ 数组相同，则输出 0。

否则，牛牛每想要让一个属性往某个方向变换（增大或减小），在最坏的情况下，牛牛吃到的前 $nn$ 个不同的药丸都将它的属性初始值往目标值的反方向变化（若初始值与目标值相等则往任意方向变化），但至此牛牛就再也不会去吃这些负面作用的药丸了，接下来的每个药丸都是有用的，因此答案为 $\sum _i(\mathrm{\mid }{a}_i-b_i\mathrm{\mid }+2)\backslash sum\backslash limits\_i(|a\_i\; -\; b\_i|\; +\; 2)$。

上式子中的 + 2 表示最坏情况下，牛牛的属性值被远离目标值后，需要额外 1 个药丸“补”回来。

代码

代码 - XLor Paste

C 01树-简单版本

题面简述

注意，本题的简单版本与困难版本的区别在于，简单版本中 $nn$ 为偶数，要求 0 和 1 的数量相等，而困难版本中 $nn$ 为奇数，要求 0 和 1 的数量相差不超过 1。

现有一个 $n\times nn\; \backslash times\; n$ 的方格，保证 $nn$ 为偶数，初始时方格的每个格点都为空，你需要在方格的每个格点都填上 0、1 其中一个数字，然后考虑这样一张图：

• 方格中的每一个格点视为一个点。
• 两个数字相同的、以边相邻的方格之间视为存在一条边。

你需要构造一个填数方案并输出该 01 方格，满足：

1. 这张图中，所有 0 所在格点相互连通，但不能出现环；所有 1 所在格点相互连通，但不能出现环。
2. 方格中 0 的数量与方格中 1 的数量相等。

可以证明，对于任意合法的输入均保证有解。

题解

构造，实现。

思考题目条件，可以想到应该可以构造一个对称的结构，以下两种做法都基于对称的角度解题。

做法 1：构造一个类似于两把刷子镶嵌的结构：

做法 2：构造一个螺旋的结构：

接下来要做的事情就是实现这样一个图形的输出。

可以看到，对于做法 1，只需要逐行输出即可，首尾行全是 0 或 1，中间 01 交错。

对于做法 2，我们如果把图中的同色色块视为点的运动轨迹，则会发现这个点从左上角出发，先向右移动 $nn$ 步，顺时针转 90° 后向下移动 $n-2n\; -\; 2$ 步，顺时针转 90° 后向下移动 $n-2n\; -\; 2$ 步，顺时针转 90° 后向下移动 $n-4n\; -\; 4$ 步，顺时针转 90° 后向下移动 $n-4n\; -\; 4$ 步......把规律观察出来后依旧不难实现。

代码

以下代码输出的图形和图示图形同构。

做法 1：

代码 - XLor Paste

做法 2：

代码 - XLor Paste

D 01树-困难版本

题面简述

注意，本题的简单版本与困难版本的区别在于，简单版本中 $nn$ 为偶数，要求 0 和 1 的数量相等，而困难版本中 $nn$ 为奇数，要求 0 和 1 的数量相差不超过 1。

现有一个 $n\times nn\; \backslash times\; n$ 的方格，保证 $nn$ 为奇数，初始时方格的每个格点都为空，你需要在方格的每个格点都填上 0、1 其中一个数字，然后考虑这样一张图：

• 方格中的每一个格点视为一个点。
• 两个数字相同的、以边相邻的方格之间视为存在一条边。

你需要构造一个填数方案并输出该 01 方格，满足：

1. 这张图中，所有 0 所在格点相互连通，但不能出现环；所有 1 所在格点相互连通，但不能出现环。
2. 方格中 0 的数量与方格中 1 的数量相差不超过1。

可以证明，对于任意合法的输入均保证有解。

题解

构造，实现。

首先，我们还是可以从对称的角度出发思考这个问题，但是不经修改地搬用简单版本中的做法已经无法解题。

对于此类构造题，另一个入手的角度是，先构造出小样例的情况，然后再推广至大的样例。基于此，以下给出 3 种做法：

做法 1：

还是从对称性入手，但是先把中间的格点遮蔽，然后画一个螺旋，发现好像有点问题，中间格点放什么颜色都不行，但是稍微改一改就行了（把绿色格点取反，然后再考虑黑色格点应该染成什么色）。

做法 2：

手玩 $5\times 55\; \backslash times\; 5$ 的情况后得到启发，做出了类似如下结构的东西（做成 $7\times 77\; \backslash times\; 7$ 方便观察），可以发现它是通用的：

做法 3：

比较神奇，来源于有验题人提出了一个神奇的图案，然后发现可以拓展：

（放两张图意会一下）

代码

做法1：

代码 - XLor Paste

做法 2：

代码 - XLor Paste

做法 3：

代码 - XLor Paste

E 奇环

题面简述

初始时有一张 $nn$ 个点的无向完全图，从中删除 $mm$ 条边，删除的第 $ii$ 条边为 $u_i,v_{i}u\_i,\; v\_i$，判断删完边的图中是否存在奇环。

$\sum n,m\le 2\times 10^5\backslash sum\; n,m\; \backslash leq\; 2\; \backslash times\; 10\; ^\; 5$。

题解

二分图，鸽巢原理。

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

假设一个图没有奇环，那么将它视为二分图，并分为左部右部，假设左部 $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 座位

题面简述

房间内有 $nn$ 张椅子从 1 至 $nn$ 标号，有 $nn$ 个人从 1 至 $nn$ 标号，他们按标号 $1\to n1\; \backslash to\; n$ 的顺序进入房间选位置坐。当第 $ii$ 个人坐下后，第 $i+1i\; +\; 1$ 个人才会进入房间选位置坐。

第 $ii$ 个人会在标号在区间 $[1,\min (n,i+1)][1,~\; \backslash min(n,\; ~i\; +\; 1)]$ 范围内的椅子等概率随机选一张没有人坐的椅子坐下。

最终有 $xx$ 人，他们自身的标号与他们所坐椅子的标号相同，求 $xx$ 的期望，对 998244353 取模。

题解

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

做法 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\}$。

补充说明：可能有读者会疑惑上式如何化简，如下给出推导： $d{p}_i=\frac{1}{2}(1+d{p}_{i-1})+{\sum }_{j=2}^{i-1}\frac{1}{2^j}d{p}_{i-j}=\frac{1}{2}+{\sum }_{j=1}^{i-1}{2}^{j-i}d{p}_j=\frac{1}{2}+2^{-i}{\sum }_{j=1}^{i-1}{2}^{j}d{p}_j=\frac{1}{2}+2^{-i}{\sum }_{j=1}^{i-2}{2}^{j}d{p}_j+\frac{1}{2}d{p}_{i-1}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\}\; \backslash \backslash \; =\; \backslash frac\{1\}\{2\}\; +\; \backslash sum\backslash limits\_\{j\; =\; 1\}^\{i\; -\; 1\}\; 2\; ^\; \{j\; -\; i\}\; dp\_j\; \backslash \backslash \; =\; \backslash frac\{1\}\{2\}\; +\; 2^\{-i\}\backslash sum\backslash limits\_\{j\; =\; 1\}^\{i\; -\; 1\}\; 2\; ^\; j\; dp\_j\; \backslash \backslash \; =\; \backslash frac\{1\}\{2\}\; +\; 2^\{-i\}\backslash sum\backslash limits\_\{j\; =\; 1\}^\{i\; -\; 2\}\; 2\; ^\; j\; dp\_j\; +\; \backslash frac\{1\}\{2\}dp\_\{i\; -\; 1\}$

$d{p}_{i-1}=\frac{1}{2}+2^{-(i-1)}{\sum }_{j=1}^{(i-1)-1}{2}^{j}d{p}_j=\frac{1}{2}+2\times 2^{-i}{\sum }_{j=1}^{i-2}{2}^{j}d{p}_{j}dp\_\{i\; -\; 1\}\; =\; \backslash frac\{1\}\{2\}\; +\; 2^\{-(i\; -\; 1)\}\backslash sum\backslash limits\_\{j\; =\; 1\}^\{(i-1)\; -\; 1\}\; 2\; ^\; j\; dp\_j\backslash \backslash \; =\; \backslash frac\{1\}\{2\}\; +\; 2\backslash times\; 2^\{-i\}\backslash sum\backslash limits\_\{j\; =\; 1\}^\{i\; -\; 2\}\; 2\; ^\; j\; dp\_j\backslash \backslash$

结合以上两式子的最后的形式（具体地，把 $d{p}_{i}dp\_i$ 的第二部分用 $d{p}_{i-1}dp\_\{i\; -\; 1\}$ 替换），得到： $d{p}_i=\frac{1}{2}+(d{p}_{i-1}-\frac{1}{2})\times \frac{1}{2}+\frac{1}{2}d{p}_{i-1}=d{p}_{i-1}+\frac{1}{4}dp\_i\; =\; \backslash frac\{1\}\{2\}\; +\; (dp\_\{i\; -\; 1\}\; -\; \backslash frac\{1\}\{2\})\; \backslash times\; \backslash frac\{1\}\{2\}\; +\; \backslash frac\{1\}\{2\}\; dp\_\{i\; -\; 1\}\backslash \backslash \; =\; dp\_\{i\; -\; 1\}\; +\; \backslash frac\{1\}\{4\}$

代码

代码 - XLor Paste

G 交换

题面简述

给定一个长度为 $nn$ 的 01 序列 $SS$，现在要进行若干次操作，每次操作可以选择一个 $i\in [1,n-1]i\; \backslash in\; [1,\; ~n\; -\; 1]$ ，然后交换 $S_{i}S\_i$ 与 $S_{i+1}S\_\{i\; +\; 1\}$。

求最少需要多少次操作能使得最终得到的 01 序列不存在两个相邻位置值都为 1。

若无解则输出 -1。

题解

本题在赛时出现了比原题解做法更优秀的 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}=\min (f_{i-1,j-1,0})f\_\{i,j,1\}\; =\; \backslash min(f\_\{i\; -\; 1,j\; -\; 1,0\})$。
• 不放：则有 $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$ 的边。

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

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

代码

代码 - XLor Paste