构造及类构造例题

构造是一种常用的思想，其范围十分广泛，难以简单概括。下面列举几道我做过的体验感比较好的题。

CODE FESTIVAL 2017 Final F

你要选择一个正整数 $n(10^3 \le n\le 2\times 10^3)$ 和 $k$，使得存在 $\{1,2,...,n\}$ 的子集 $S_1,S_2,...,S_n$ 满足：

• $|S_i|=k$，
• $\forall i\in [1,n]$， $i$ 在所有集合中出现过 $k$ 次。
• $\forall 1\le i< j\le n, |S_i \cap S_j|=1$。

并求出一种方案。（提交答案题）

观察 $\sum \limits_{i=1}^n \sum \limits_{j=i+1}^n |S_i \cap S_j|$，因为每个值都会恰好出现 $k$ 次，每个值会恰好贡献 $\binom{k}{2}$ 个二元组。因此有 $\frac{n(n-1)}{2}=\frac{nk(k-1)}{2}$，化简得 $n=k^2-k+1$。

当 $(k-1)$ 为质数时会有一个合法的方案。将元素写为下面的形式（$n=13,k=4$）：$\begin{matrix} 1 & 2 & 3 & 4\\-& 5 & 6 & 7 \\ - & 8 & 9 & 10 \\ - & 11 & 12 & 13\end{matrix}$ 对于 $1$ 能先取每一行，对于第一行的其他元素，构造一个“步长”相等的序列（例： 2 5 8 1,2 6 9 12,2 7 10 13, 3 5 9 13,3 6 19 11,3 7 8 12,4 5 10 12,4 6 8 13,4 7 9 11），即构造完了这组解。

P3524

给定一张 $n$ 个点 $m$ 条边的图，保证有 $\frac{2n}{3}$ 个点的团，需要找到一个 $\frac{n}{3}$ 个点的团。 $n\le 3000$。

考虑每次删两个不连通的点，因为这两个点至多有一个在团里，因此删完所有不连通的点后至少会有一个 $\frac{n}{3}$ 的团。

CF1365G

有数组 $A$，$P_i= \operatorname{OR}\limits_{j \neq i} A_j$，你每次可以给出一个集合并询问集合内下标元素的或，要使用至多 $13$ 次询问求出 $P$。$n\le 10^3,A_i\le 2^{63}$。

考虑将所有数按照 $13$ 位编码，并强制每个编码都有 $6$ 个 $1$。（因为 $\binom{13}{6}\ge 1000$，所以这是可以做到的）每次询问第 $1,2,...,13$ 位是 $1$ 的所有数的集合，并将其他位是 $0$ 的或上这个答案。因为任意两个集合之间没有包含关系，可以保证每个数都被其他数或过至少一次，所以即可获得答案。

AGC050A

你有 $n$ 个点，对于每个点你可以向外面连两条单向边，构造一个方案使得任意两点间存在一条路径经过不超过 $10$ 条边。$n\le 1000$。

对于每个点 $i$ 连边 $2i \bmod n$ 与 $(2i+1) \bmod n$（ $0$ 开始编号）。走十条边后可以抵达 $1024i\sim 1024i+1023 \pmod n$，故一定有解。

QOJ8130

给定两颗有根树，保证这两棵树有且仅有 $1,2,...,k$ 号点是叶子。将每个叶子染成红色或者蓝色，使得对于每棵树，每个子树中红叶子和蓝叶子的数量相差不超过 $1$。 $n\le 10^5$。

对每棵树从下到上递归，对于每棵树，要是存在两个没有连过边的叶子连边，要求这两个叶子颜色不同。可以验证最后一定是若干偶环和链，故一定有解。

AGC066A

给定矩阵 $A$ 与正整数 $d$，求一个矩阵 $B$ 满足 $\forall i\in [1,n-1],j\in [1,n],|B_{i,j}-B_{i+1,j}\ge d,|B_{j,i}-B_{j,i+1}|\ge d$。要求 $\sum |A_{i,j}-B_{i,j}|\le \frac{dn^2}{2},n\le 1000$。

考虑 $d=1$ 时，给网格黑白染色，黑色填奇数，白色填偶数，这样做最大代价是 $dn^2$。考虑反过来填这两种方案的和是 $dn^2$，因此一定有一种方案满足条件。$d$ 更大时，黑色填 $\bmod 2d=d$，白色 $\bmod 2d=0$ （或反过来）即可。

Ex

构造 $10^4$ 个 $a_i$，使得 $a_i+a_j$ 互不相同且 $a_i\le 5\times 10^8$。

选取一个比 $n$ 略大的质数 $p$，构造 $a_i= 2ip+(i^2\bmod p)$。

$a_i+a_j= 2(i+j)p +(i^2\bmod p)+(j^2 \bmod p)$ 总是唯一的。