IOI2020 集训队作业

AGC029F

题意

给定 $n-1$ 个 $\{1,2,\cdots ,n\}$ 的大小至少为 $2$ 的子集 $S_i$，构造一种方案，使得从每个子集选两个点连边，最后生成一棵树。($1\le n\le {10}^5$，$\sum |S_i|\le 2\times {10}^5$)

题解

考虑一个必要条件：

建立一个二分图，左边是所有点，右边是 $n-1$ 个集合。

那么对于任意一个右边点的子集 $V$，左边与 $V$ 中点有边相邻的数量 $\ge |V|+1$。否则，考虑这些集合所组成的边，点数不超过 $V$，那么必然成环。

显然，由 Hall 定理，这个图的最大匹配为 $n-1$。

容易证明，这也是充分条件：

考虑如下类似 bfs 的操作：将与根节点相连的所有集合拿出来，各自找到其匹配点，将他们都当作根节点的儿子；接下来将这些点相连的且之前没被选过的集合拿出来，重复上述操作，再将各匹配点当作各自节点的儿子。

如果最终能遍历到所有点，则这是一个合法的构造方案。

否则，说明有些点遍历不到。注意到总点数左边比右边多一个，且遍历到的点也是左边比右边多一个，因此没遍历的点左右数量相同。选取右边的没遍历的点作为 $V$，则左边与 $V$ 中点有边相邻的数量 $=|V|$，矛盾。

跑 dinic 后求最大匹配，再进行上述所说的 bfs，如果能遍历所有点则合法，时间复杂度为 $O(\sum |S_i|\sqrt{n})$。

AGC030C

题意

构造一个 $n\times n$ 的矩阵，$1$ 到 $k$ 每个整数恰好出现了一次。整个矩阵是上下连通，左右连通的。对于相同的整数，它周围四个数的种类和数量必须相同（例如所有 $1$ 四周都有 $2$ 个 $2$ 和 $2$ 个 $3$，不需要每个方向上的数都完全相同），要求 $n\le 500$。($1\le k\le 1000$)

题解

考虑每行填相同的数，显然合法，但是 $n$ 最多只有 $500$。考虑选一些行交替填不同的数，这样就能达到 $1000$。

乍一看老对了，实则不然，考虑交替填数的行必然与只填一个数的行有相邻，那么只填一行数这一行上的数就不符合条件了。

正解为，改为一个对角线填一个数，然后再选一些对角线交替填两种数。这其实利用了 不需要每个方向上的数都完全相同 这一性质。

AGC030D

题意

给定一个长度为 $n$ 的序列 $a_1,a_2,\cdots ,a_n$。$q$ 次操作，第 $i$ 次操作有 ${\displaystyle \frac{1}{2}}$ 的概率交换 $a_{x_i}$ 和 $a_{y_i}$，求期望逆序对 个数。($1\le n,q\le 3000$)

题解

设 $f_{i,j}$ 为 $a_i<a_j$ 的概率，每次操作后进行更改： $$\begin{array}{rl}\frac{f_{x_i,j}+f_{y_i,j}}{2}& \to f_{x_i,j},f_{y_i,j},j\ne x_i\wedge j\ne y_i\\ \frac{f_{j,x_i}+f_{j,y_i}}{2}& \to f_{j,x_i},f_{j,y_i},j\ne x_i\wedge j\ne y_i\\ \frac{f_{x_i,y_i}+f_{y_i,x_i}}{2}& \to f_{x_i,y_i},f_{y_i,x_i}\end{array}$$ 每次转移量仅为 $O(n)$，总复杂度为 $O(qn)$。

AGC030E

题意

给定两个长度为 $n$ 的 $01$ 串，每次可以将第一个串的一个位置翻转，要求任意时刻不存在长度大于 $2$ 的连续 $0$ 或 $1$，求将第一个串变为第二个串的最少操作次数，保证给定的两个串满足上述条件。($1\le n\le 5000$)

题解

考虑对于一个符合条件的 $01$ 串，在相邻 $01$ 间连蓝边，相邻 $10$ 间连红边，则红蓝边交替且相邻两者距离不超过 $2$，否则就出现了 $3$ 个相同的字符了。

每次翻转一个字符等价于，移动一条边，或是将最左/最右的边删掉。

我们可以假设第一个字符左边和最后一个字符右侧还有无数条红蓝边，可以用一次操作将其移动到串上。那么枚举从左边移动出来多少条边，$O(n)$ 贪心匹配计算总移动次数即可，总时间复杂度为 $O(n^2)$。

很坑的一点，当 $n\le 2$ 时上述转化并不等价，因为不可能存在连续 $3$ 个一样的，所以直接改就可以，要特判。

AGC030F

题意

对于一个 $1$ 到 $2n$ 的排列 $a_1,a_2,\cdots ,a_{2n}$，一些位置已经钦定，剩下位置随便填，问序列 $b_i=min(a_{2i-1},a_{2i})$ 有多少种不同的可能。($1\le n\le 300$)

题解

设所有 $a_{2i-1}$ 和 $a_{2i}$ 都不确定的 $i$ 有 $m$ 个，显然最后 $b_i$ 中这些位置是可以任意交换的，因此可以先不考虑它们之间的位置关系，最后再乘以一个 $m!$。

考虑从大到小填每个数，这样每填一个数后状态是唯一确定的。设 $f_{i,j,k}$ 为填了 $[i,2n]$ 的所有数后，有 $j$ 个没被钦定位置也没有配对的数，有 $k$ 个被钦定位置但没有配对的数。

AGC031D

题意

题解

AGC031E

题意

题解

AGC031F

题意

题解

AGC032C

题意

题解