「集训队作业」IOI 2020 集训队作业小结 5

简介

本文包括 IOI 2020 集训队作业 31 ~ 35 题的题解，下面是题单：

• 31.「AGC 030D」Inversion Sum
• 32.「AGC 030E」Less than 3
• 33.「AGC 030F」Permutation and Minimum
• 34.「AGC 031D」A Sequence of Permutations
• 35.「AGC 031E」Snuke the Phantom Thief
• 36.「AGC 031F」Walk on Graph

Inversion Sum

$f(i, j)$ 表示 $a_i > a_j$ 的概率，直接转移即可，时间复杂度 $O(n (n + q))$。

#include <bits/stdc++.h>

Less than 3

在每个相邻的 01 之间插红色隔板，10 之间插蓝色隔板，左右两边补上无限个隔板。这样给一个数取反相当于将一个隔板移动一格，那么我们枚举隔板的一个匹配，显然移动步数的下界是隔板距离之和。发现下界可以取到，所以直接计算取最小值即可，时间复杂度 $O(n^2)$。

#include <bits/stdc++.h>

Permutation and Minimum

首先我们将每个不是 $-1$ 的 $p_i$ 变成 $2n - p_i + 1$ 方便处理。$(p_{2i - 1}, p_{2i})$ 可以分成三种情况：$(x, y), (x, -1), (-1, -1)$。$(x, y)$ 可以直接扔掉，我们先考虑不存在 $(x, -1)$ 的情况。可以看作是有 $2n$ 个点，将它们两两配对后右端点取值形成的集合的个数。考虑前 $i$ 个数，$i$ 可以匹配之前的某一个没选过的端点，或者自己暂时不选。发现方案数就是卡特兰数。当然对于一种匹配的方案，有 $n$ 对点，我们要把它分配到 $n$ 个位置，答案要额外地乘上 $n!$。

接下来考虑 $(x, -1)$，一个 $(x, -1)$ 就表示 $x$ 号点要匹配一个空的点，我们称 $x$ 为特殊点。记 $f(i, j, k)$ 表示考虑前 $i$ 个位置，有 $j$ 个未匹配的普通点，有 $k$ 个未匹配的特殊点。那么如果第 $i$ 个位置是特殊点，它要么暂时不选，要么匹配普通点。如果第 $i$ 个位置是普通点，它要么暂时不选，要么匹配普通点，要么匹配特殊点。注意匹配不同的特殊点时在原序列中的位置是不同的，所以方案数要乘上特殊点个数。那么最后的方案数就是 $f(n, 0, 0) \times c!$，$c$ 表示 $(-1, -1)$ 的对数。直接 dp，时间复杂度 $O(n^3)$。

#include <bits/stdc++.h>

A Sequence of Permutations

对于排列 $p, q$，定义 $pq$ 表示第 $i$ 位为 $p_{q_i}$ 的排列，$p^{-1}$ 表示第 $p_i$ 位为 $i$ 的排列，那么我们有 $(pq)^{-1} = q^{-1}p^{-1}$，$p^m p^n = p^{m + n}$，$(pq)r = p(qr)$，并且题目里的 $f(p, q) = qp^{-1}$。记 $g(p, q) = pqp^{-1}$，那么有：

$$\begin{split} a_1 & = p & = g(\varepsilon, p) \\ a_2 & = q & = g(\varepsilon, q) \\ a_3 & = qp^{-1} & = g(\varepsilon, qp^{-1}) \\ a_4 & = qp^{-1} q^{-1} & = g(q, p^{-1}) \\ a_5 & = qp^{-1} q^{-1} p q^{-1} & = g(qp^{-1}, q^{-1}) \\ a_6 & = qp^{-1} q^{-1} p^2 q^{-1} & = g(qp^{-1}, q^{-1}p)\\ a_7 & = qp^{-1} q^{-1} p q p q^{-1} = g(qp^{-1}q^{-1}, p) \ & = g(qp^{-1}q^{-1} p, p) \\ a_8 & = qp^{-1} q^{-1} p q p^{-1} q p q^{-1} & = g(qp^{-1}q^{-1}p, q) \\ a_9 & = qp^{-1} q^{-1} p q p^{-2} qp q^{-1} & = g(qp^{-1}q^{-1}p, qp^{-1}) \\ \end{split}$$

也就是 $g(r,p)$ 和 $g(r,q)$ 在 $6$ 次之后会变成 $g(rqp^{-1}q^{-1}p,p)$ 和 $g(rqp^{-1}q^{-1}p,q)$，所以只要求出 $(qp^{-1}q^{-1}p)^{\lfloor \frac{k - 1}{6} \rfloor}$ 即可，时间复杂度 $O(n \log k)$ 或 $O(n)$。

#include <bits/stdc++.h>

Snuke the Phantom Thief

首先枚举选的总个数 $T$，对于一种选的方案记 x 坐标从小到大为 $x_1, x_2, \cdots, x_T$。那么 L $a_i, b_i$ 的限制相当于强制 $x_{b_i + 1} \ge a_i + 1$，R $a_i, b_i$ 的限制相当于强制 $x_{T - b_i} \le a_i - 1$。我们可以给每个 $x_i$ 加一个限制 $l_i \le x_i \le r_i$，并满足 $l_i \le l_{i + 1}, r_i \le r_{i + 1}$。D, U 的限制同理，我们搞出 $d_i \le y_i \le u_i$。然后我们建图：

• 每个珠宝拆成 A 和 B，A 向 B 连边，容量为 $1$，费用为 $-v_i$。
• 源点连向每个 x 限制，容量为 $1$，费用为 $0$。
• 每个 x 限制向可行的珠宝 A 连边，容量为 $1$，费用为 $0$。
• 每个珠宝 B 向可行的 y 限制连边，容量为 $1$，费用为 $0$。
• 每个 y 限制连向汇点，容量为 $1$，费用为 $0$。

思考一下发现这样是对的，因为如果第 $i$ 个 x 限制选择的 x 坐标大于第 $i + 1$ 个 x 限制选择的 x 坐标的话一定是不优的。于是我们枚举 $T$，给每个费用预先加上 $10^{15}$，跑最小费用最大流，最后将答案减去 $10^{15}T$ 并取最小值即可。因为最大流的大小是 $O(n)$ 的，图的规模是 $O(n) - O(n^2)$ 的，我们还要跑 $n$ 遍这样的算法，所以时间复杂度为 $O(n^4)$。

#include <bits/stdc++.h>