IOI2021 集训队作业（一）

发表于 2020-10-19 更新于 2021-03-29 分类于整理阅读次数：

有生之年。

233. Rubik's Rectangle

给定一个 $H \times W$ 的网格，每个网格有个数字，每次操作可以翻转某行或某列，求一组合法操作使得该网格的数字排好序。

时间复杂度：$O(HW(H+W))$ 。

题解

不妨假设 n, m 都是偶数（如果是奇数那么中间的一行或列可以独立）。

可以发现可以把格子染色，每种颜色恰好四个格子，满足任意翻转操作后颜色矩阵不变。

不妨假设每个数字在正确的颜色位置上。考虑每个颜色内的四个点，可以发现如果这些点构成偶排列那么就总可以在不影响其他颜色的前提下把这四个点排好序，如果是奇排列则总是不能。称每个颜色的左上角的点为代表点，把颜色的排列奇偶性作为标记放到代表点上，对于代表点标记构成的 01 矩阵 A ，如果 A 是全 0 矩阵自然是有解的。

而每次翻转对 A 的影响就是讲某一行或某一列的 01 给全部反转，因此只要能通过这个操作把 A 弄成 01 矩阵就能得到解，这就是个很 simple 的贪心了。

数据

~~这 spj 真难写。~~

不难想到如果随机选择一个排列放到网格上，那么极大的概率是无解。采用逆推的方式，从一个排好序的网格随机执行若干次操作得到一个打乱的网格，这样就可以保证数据有解。在此基础上加上一些扰动改变一些代表点的奇偶性即可得到强度较大的无解数据。

234. Hiking in the Hills

在三维空间上给定一个曲面，该曲面由 $n$ 个三角形构成，在曲面上给出两个点，求曲面上连接两点的一条折线使得折线上的最高的点的高度最小（高度指 z 轴坐标）。

保证任意直线 $x=x_0, y=y_0$ 与该曲面的交点至多只有一个。

时间复杂度：$O(n \log n)$ 。

题解

容易发现这条折线可以只走三角形端点，把三角形端点和起点终点拿出来建图然后把点按高度排序，用个并查集维护即可。

数据

~~这 spj 真难写。~~

这题造数据比写标程难。先确定所有三角形端点，再构造三角形，把端点投影到 xy 平面上，那么构造三角形就是在平面上求一组三角剖分。

235. Single Cut of Failure

有一个矩形，称一条端点落在矩形的不同的两条边的线段为合法线段。给定 $n$ 条合法线段，要求添加最少的合法线段使得每条给定的合法线段与至少一条添加的合法线段有交。

时间复杂度：$O(n \log n)$ 。

题解

比较降智的一点是，添加两条对角线总是满足条件的。那么我们只需要关注是否可以找到一条合法线段与所有给定线段有交。

把矩形的边展开为一个数轴，每个给定线段对应数轴上一段区间，那么目标是选两个点满足它们所在的区间的集合的不交并是全集。假设区间没有包含关系，排个序后枚举一个点双指针处理另一个点即可。对于有包含关系的区间，稍加特殊处理就可以合并为一个区间。

数据

~~这 spj 真难写。~~

不难想到如果在矩形内随机给出 $n$ 条合法线段，那么有极大的概率不存在一条线段的解。不妨先确定最后需要添加的线段，然后给出 $n$ 条与之有交的合法线段。

121. Bipartite Blanket

给定一个二分图，左右分别 $n, m$ 个点，点有点权，称一个点集是合法的当且仅当存在一组匹配是该点集的父集，求有多少合法点集的点权和不小于 $t$ 。

时间复杂度：$O(n 2^n + m 2^m)$ 。

题解

对于点集 $S$ 考虑判断是否存在匹配覆盖了 $S$ 。如果 $S$ 只包含左边的点或者只包含右边的点，容易发现用 Hall 定理就能判断。否则设 $S = X \cup Y, X \cap Y = \emptyset$ ，其中 $X, Y$ 分别是左右边集。那么可以证明，存在匹配覆盖 $S$ 当且仅当存在匹配覆盖 $X$ 且存在匹配覆盖 $Y$ 。

必要性很显然，证明充分性，假设已知一个覆盖 $X$ 的匹配和一个覆盖 $Y$ 的匹配，考虑取构造一个覆盖 $S$ 的匹配，首先把覆盖 $X$ 的匹配作为初始匹配，然后逐个加入 $Y$ 中的点和对应的匹配点，分类讨论不难得到一个简单的构造方法。

那么把两边的能被匹配覆盖的点集分别处理出来排个序然后双指针即可。

122. Intellectual Property

有三个三元组 $(1, 2, 3), (4, 5, 6), (7, 8, 9)$ ，对数独定义若干操作：

选择两个数字 $x, y$ 并把所有 $x$ 变为 $y$ ，把所有 $y$ 变为 $x$ 。
选择同一三元组的两行交换。
交换两个三元组对应的行。
选择同一三元组的两列交换。
交换两个三元组对应的列。
沿左上-右下对角线翻折。

给定 $n$ 个数独，对于每两个数独求出一组操作序列使得一个数独操作后与另一个相同或输出无解。

时间复杂度：$O(1296 (9^2 n + n^2))$ 。

题解

容易发现由于存在三元组的限制，行和列的置换数都是 $1296$ 而非 $9!$ 。对于两个待检查的数独 $a$ 和 $b$ ，朴素的想法是在 $a$ 上枚举所有行的置换和所有列的置换然后比对，但是由于行列之间不影响，不难想到折半，在 $a$ 上枚举所有行的置换，然后在 $b$ 上枚举所有列的置换，在两边检查有没有相同的数独即可。

对角线翻折操作最多只进行一次，并且如果需要进行的话可以在任意时刻进行，因此如果需要这个操作不妨假定它在最后，额外检查一次即可。

123. Gem Island

以前做过，略。

134. J

给定一个长为 $L$ 的表达式。表达式对向量和标量进行运算，有加法减法乘法取反自平方和折叠共六个运算，其中折叠是对一个向量求各个分量的和。表达式中会出现各种标量，但出现的向量仅有 $X$ 。给定 $X$ 求表达式的值。

特别地，每个子表达式中关于 $X$ 的复杂度不超过 $X^K$ 。

时间复杂度：$O(|X| K + L K^2)$ 。

题解

直接把向量拿进去模拟运算的话瓶颈复杂度 $O(L |X|)$ 无法接受。但是注意到表达式中出现的向量仅有 $X$ ，并且折叠操作对加法有分配率，那么总可以用一个关于 $X$ 的多项式来表示一个表达式的值，并且题目中的限制保证了这个多项式的次数不超过 $K$ 。

146. Tile Cutting

对于一个 $n \times m$ 的网格矩形 $M$ ，称一个平行四边形 $A$ 被 $M$ 包裹当且仅当：

$AS$ 的四个顶点分别落在 $M$ 的四条边上。
$AS$ 的四个顶点恰好落在格点上。

设 $f(S)$ 表示满足以下限制的二元组 $(M, A)$ 的数目：

$A$ 被 $M$ 包裹。
$A$ 的面积恰为 $S$ 。

$Q$ 次询问，每次给定区间 $[l, r]$ 求 $S \in [l, r]$ 时 $f(S)$ 的最大值。保证 $r \le V$ 。

时间复杂度：$O((V + Q) \log V)$ 。

题解

把面积关于平行四边形的位置的式子写出来，稍加整理，不难发现 $f(S)$ 就是满足 $ab + cd = S$ 的正整数四元组 $(a, b, c, d)$ 的数量：

\[ f(S) = \sum_{x+y=S} \sum_{a,b} [ab = x] \sum_{c,d} [cd = y] = \sum_{x+y=S} d(x) d(y) \]

FFT 即可。

153. Fygon 2.0

给定一个 $m$ 层嵌套 for 循环，循环的左边界要么是前文出现过的循环变量要么是 $1$ ，右边界要么是前文出现过的循环变量要么是常数 $n$ 。求该循环最后的语句的执行次数的渐进复杂度 $C n^K% 。

时间复杂度：$O(m^3 + m 2^m)$ 。

题解

首先不难注意到一个 for 循环就是一个形如 $l \le i \le r$ 的不等式，最后的语句的运行次数实际上是满足所有不等式的循环变量组数。

按不等关系连边，显然 SCC 内的值要相同，缩点得到一张新图 $G$ 。不难想到 $K$ 就是 $G$ 的点数，接下来着重考虑计算渐进复杂度的常数。

由于渐进复杂度是在 $n$ 趋于正无穷时体现出来的，不妨假定 $n$ 为正无穷，那么每个变量的取值范围就是整个正整数域，不妨钦定 $G$ 内循环变量的取值是两两不同的，考虑每个变量随机取值，满足所有限制的概率。事实上这个概率就是我们要计算的系数 $C$ 。

由于我们只关心变量之间的大小关系，按变量从小到大得到排列 $p$ ，每个排列 $p$ 的出现概率都是 $\dfrac{1}{K!}$ 。假设合法的排列数量是 $x$ ，那么要计算的系数就是 $\dfrac{x}{K!}$ 。于是问题转换为求合法的排列数，也就是拓扑排序的方案数，用状压 DP 可以很好解决。

173. Equal Numbers

给定长为 $n$ 的值不超过 $V$ 的正整数数列 $a$ ，可以执行的操作是选择 $i, x$ 令 $a_i \leftarrow x \times a_i$ 。

对于每个 $k \in [0, n]$ 计算执行 $k$ 次操作能得到的数字种类数的最小值。

时间复杂度：$O(n + V \log V)$ 。

题解

设 $X$ 是 $1$ 到 $V$ 的 lcm ，不难想到操作只有两种情况：

选 $k$ 个数修改为 $X$ 。
选 $k$ 个数修改为已经在数列中存在的数。

分别考虑两种情况。对于情况 1 ，贪心从出现次数最少的数开始修改即可。对于情况 2 ，把能够修改的数拿出来按情况 1 的方法贪心即可。

133. Chain & Co.

在三维空间上给定 $n$ 个四条边都与轴线平行的矩形，称两个矩形是连接的，当且仅当一个矩形总是无法在不穿过另一个矩形的前提下平移到某个指定位置。把矩阵分为两组，使得两组非空且任意不同组的两个矩形都是连接的。

时间复杂度：$O(n \log n)$ 。

题解

首先矩形一定平行于某个轴平面，两个矩形连接的一个必要条件是它们平行的轴平面不同。那么所平行的轴平面相同的矩形必须分在同一组。由于轴平面只有三个，那么分组的方式只有三种，枚举三种情况，问题转换为判断两组矩形是否两两连接。

不妨假设一组矩形全部平行于 x-y 平面（称为 A 组，另一组为 B 组），那么 B 组的矩形在 x-y 平面上的投影总是一个线段。考虑 B 组的矩形的 z 轴坐标要满足什么限制，显然每个 B 组矩形的 z 轴坐标范围内要包含所有 A 组矩形的 z 轴坐标，这个很好判断，接下来的问题忽略 z 轴而转换为二维平面上的问题。

现在的问题是，对于每个线段，判断其是否与每个矩形都连接，这里线段和矩形连接当且仅当线段一个端点在矩形内另一个端点在矩形外。不妨假设这些线段都是平行于 x 轴的，同样地我们可以先考虑 y 轴上的限制，和 z 轴的判定类似，接下来问题可以进一步放到数轴上。在数轴上问题最终转换为有 C, D 两组线段判断是否存在一个 C 组线段完全包含一个 D 组线段，排个序双指针即可。

145. Cow Confinement

在平面上给定 $f$ 个矩形，$n$ 头牛和 $m$ 朵花的位置，对于每头牛求如果它只往 x, y 轴正方向走，不越过任何矩形的前提下有多少花是可以到达的。保证矩形两两之间没有交点且都与坐标轴平行。

时间复杂度：$O((n + m + t) \log)$ 。

题解

很佩服官方题解，全文一句话也没有说，仅仅通过几张示意图就把核心思想描述地很清楚，剩下的部分就是简单的数据结构。

假设没有矩形的阻挡，那么问题就是查询矩形内的花的数量，但还可以这样描述，把花看做向 y 负方向的射线，把牛看做向 x 正方向的射线，那么牛能到的花的数量就对应于射线的交点数量。

考虑矩形的阻挡，如果牛的射线经过一个矩形，那么事实上的影响就是把当前射线分成两部分，经过矩形前是一个线段，经过矩形后是一个新的射线，新的射线沿着矩形边想 y 正方向移动。特别地，如果触碰到的矩形边是矩形内的话，就不会有新的射线。同理处理花的射线，但是注意到花的射线拆分后一个花可能对一头牛贡献多次。把花的射线拆分归则稍加修改即可。

爬两张官方题解的图，其中 A, B 分别是牛和花，蓝色的即牛对应的射线，红色的即花对应的射线。

总而言之，矩形的影响就是让经过它的射线发生“偏移”，最后转换的问题仍然是有若干横向射线，若干纵向射线，求每个横向射线与多少纵向射线有交点这样的问题。扫描线加树状数组即可。

255. Money for Nothing

在二维平面上给定 $n$ 个白点和 $m$ 个黑点，求一个面积最大的矩形满足左下角是黑点右上角是白点。

时间复杂度：$O((n + m) \log)$ 。

题解

不妨假设白点和黑点都是横纵坐标同时单调递减的（否则的话一定存在一个点可以完全替代另一个点）。

然后考虑对于每个白点求对应的最优的黑点，不难想到是最优黑点是单调的，因此决策单调分治处理即可。

特别地，有些白点压根没有合法的黑点与它构成矩形，这种情况需要稍加处理。

293. Weather Report

给所有长度为 $n$ 的四进制数一个二进制编码，要求编码之间两两没有前缀关系。以 $\prod_{i=1}^n P_{a_i}$ 的概率选中四进制数 $a$ ，其中 $a_i$ 表示 $a$ 的第 $i$ 个数位的值。$P_0, P_1, P_2, P_3$ 给定且和为 $1$ 。

最小化选中的四进制数的编码的长度的数学期望。

时间复杂度：$O((\dfrac{n}{w}) n^4 \log n)$

题解

把所有四进制数的编码建 Trie ，由于编码之间两两没有前缀关系，那么 Trie 的单词节点两两没有祖先关系。一个 Trie （即编码方式）的代价就是每个叶子的权值（对应的四进制数的出现概率）乘上其深度的和。

而最小化这个 Trie 的代价是很简单的，每次贪心选两个最小的叶子合并即可。

唯一的问题在于节点数 $4^n$ 太多，不过许多都是权值相同的，爆搜四种天气的数量，用组合数算一类权值的节点的数量，将它们作为整体应用到贪心算法即可。

这个最优编码就是 Huffman 编码，上文的 Trie 树就是 Huffman 树，上文的贪心算法就是构建 Huffman 树的一个常用算法。

事实上，由于需要记录一类权值的数量，而这个数量 $t$ 的值是 $O(4^n)$ 的（上确界应该是 $\dfrac{n!}{(\frac{n}{4}!)^4}$ ），因此这个数值的运算复杂度是 $O(\dfrac{n}{w})$ ，然后一类数量为 $t$ 的权值最多被重复取出 $\log t$ 次，也就是 $O(n)$ 次，这样算下来就得到了上述的复杂度上界（可能未必是上确界）。

如果数量 $t$ 用整数记录的话，有 $n < w$ ，这个 $n$ 实际上是不大的。

101. Correcting Curiosity

给定两个不相等的非空串 $s$ 和 $t$ ，要求找到两个串 $A$, $B$ 使得在 Vim 内对 $s$ 执行 s/A/B/g 命令后得到的串恰为 $t$ ，并使得 $|A| + |B|$ 最小。

时间复杂度：$O(|s|^2 + |t|)$ 。

题解

直接从 $s$ 的所有子串中枚举 $A$ ，不难发现只要确定了 $A$ 就可以唯一确定 $B$ ，然后在 $s$ 上模拟替换命令，这样的复杂度是三次方的。

预处理 $s$, $t$ 的哈希值，就可以做到单次替换 $O(1)$ ，总复杂度就是平方了。

102. Replicate Replicate Rfplicbte

对于一个无限大的 01 矩阵，每一次变化定义为依次执行两个操作：

把每个位置变成操作前其相邻共九个位置的异或和。
选择至多一个位置将其取反。

定义一个无限大的 01 矩阵的大小为，能包含所有 1 的子矩阵的面积的最小值。

现给出一个矩阵 $A$ ，大小为 $n \times m$ ，求一个大小最小的能通过若干次变化变成 $A$ 的矩阵。

时间复杂度：$O(nm(n+m))$ 。

题解

首先注意到，无论有没有二操作，每一次变化后，矩阵的“边界”都会想上下左右四个方向个扩展至少一格。

通过这一点，如果没有二操作，对于一个矩阵 $A$ ，我们可以唯一确定能一次变化到 $A$ 的矩阵 $B$ ，或判断不存在这样的 $B$ 。

具体方法就是递推，把 $B$ 的每个位置看做变量，$A$ 的每个位置就是异或方程，但是由于可以确定 $B$ 的边界至少向内缩一格，也就可以确定在 $A$ 的外侧的位置上 $B$ 都是 0 。

考虑如果有二操作，怎么找到二操作的执行位置。

假设我们逐行递推，那么每一行只有 $n-2$ 个变量但有 $n$ 个方程。找到第一个方程组无解的行，那么如果有二操作，二操作的执行位置一定在该行。同理我们可以确定列，进而得到二操作的位置，然后还原二操作再检验即可。