构造题选讲

A 组

A1

给出$n$，问是否存在三个$n$的排列$a,b,c$使得$\forall 1\le i\le n, \; a_i+b_i=c_i\pmod n$。

如果有解，给出构造。

当$n$是偶数时，左边的和是$(n-1)n$，右边的和是$\frac{1}{2}n(n-1)$，不同余，因此无解。

当$n$是奇数时，令$a$和$b$都是$[1,2\ldots,n]$即可。

A2

给出一个$n=2^m-1$个点的无向完全图$G$，从中找出尽量多的不交的三元环。$m\le 10$。

$G$的边数是$3$的倍数，因此猜测是可以取完所有边的。

我们考虑对每条边$(x,y)$，找到它所属的三元环。

如果将边按照$(x+y)\bmod n$分类，会有冲突。

将边按照$x\oplus y$分类即可（假设点的编号是$1,\ldots,2^m-1$）。

取出所有$x\oplus y\oplus z = 0$的三元环$(x,y,z)$即可。

任意两个三元环互不冲突是显然的。

如果$x\ne y$且$x,y,z$非$0$，则一定有$z\ne x$且$z\ne y$，这也显然。

因此我们可以取完所有三元环，且这些三元环互不冲突，且没有不合法的情况。

A3

一个$2n$个点的无向完全图，你需要把这些边分成$2n-1$组，每组$n$条边，且每组都是一个匹配。$n\le 1000$。

考虑按照模数分类。

先不考虑与点$2n$相邻的边，我们将边$(x,y)$按照$(x+y)\bmod (2n-1)$分类。

容易发现每个类都是一个$n-1$条边的匹配。

对于$(x+y)\equiv z\pmod {2n-1}$的类，我们给他分配$(2n,k)$这条边，其中$2k\equiv z \pmod {2n-1}$即可。

A4

一个$n$个点的完全图，你需要从中选出尽量多的不交的$n$个点的树。$n\le 1000$。

考虑$n$是偶数的情况。上界是$\frac{n}{2}$个树。

考虑序列$a_x = [x,x+1,x-1,x+2,x-2,\ldots, x+\frac n2-1, x-(\frac n2-1),x+\frac n2]\pmod n$。则$(a_{x,i},a_{x,i+1})$这$n-1$条边构成一条链，也就是树。

容易发现$a_x$和$a_y$（$x\not\equiv y\pmod {\frac n2}$）构成的树是不相交的。因此我们构造出了达到上界的方案。

考虑$n$是奇数的情况。上界是$\frac{n-1}{2}$。

则我们先对前$n-1$个点按偶数的方式构造，然后让每个$x$连一条边到$n$即可。

B 组

B1

NFLSPC #3 G

平面上有$n$个不三点共线蓝色的点，你需要加上$k$个红色的点，使得任意三个蓝点组成的三角形内部都必须至少有一个红点。注意红点必须在三角形内部，不能在边上。

你需要最小化$k$的大小。$n\le 100$。

考虑答案的下界。

考虑这个$n$个点构成的凸包，假设凸包上点数是$m$。对这$n$个点三角剖分，会有$2n-m-2$个互不相交的三角形。这是因为，把凸包三角剖分有$m-2$个三角形，而在凸包内每加一个点，就会多$2$个三角形，所以总数是$(m-2)+2(n-m) = 2n-m-2$。

三角形内角和是平角。

考虑把整个平面随机旋转一个角度，使得任意两个蓝点的连线都不水平。对于每个蓝点$(x,y)$，我们在$(x-\Delta,y)$和$(x+\Delta,y)$的位置各放一个红点。$\Delta$是一个极小的值。

根据抽屉原理，三角形三个角平移一下可以拼成平角。因此每个三角形里都有至少一个红点，构造是合法的。这个构造用了$2n$个红点。

容易发现，凸包外面的红点是没用，这部分红点有$m+2$个（最高的点和最低的点左右两边的红点都是没用的）。去掉它们，刚好达到下界。因此这是最优构造。

B2

给定一个$n^2+n$的排列，你需要从中选出一个长度为$2n$的子序列使得子序列中第$2k$和第$2k-1$大的数相邻。

试构造出一个子序列，或说明不可能。$n\le 1000$。

把序列分成$n$段，每段$n+1$个数。

设第$i$段的最小值和次小值分别是$A(i),B(i)$。

每次我们找到$B(i)$最小的段$i$，然后取出$A(i),B(i)$，然后删除这一段，然后把其他段$\le B(i)$的数删除。容易发现，其他段最多被删掉一个数。

做$n$次得到一个长度为$2n$的序列，即可。

B3

有个$2n\times m$的棋盘，有$nm$个红格子和$nm$个蓝格子。保证棋盘的左上角是红色，右下角是蓝色。你需要把蓝色格点中心两两连出一个向量，红色格子中心两两连出一个向量，你需要让这些向量之和为$0$。

当$nm$是奇数时，分别连欧拉回路即可，或者分解为几个环也行。

当$nm$是偶数时，去掉棋盘左上角的红色和右下角的蓝色，可以按照偶数的方法做。然后把所有红点连一个向量到左上角，蓝点连一个向量到右下角即可。

证明：交换两个红蓝格子（不是左上角或者右下角的），向量和不变。

B4

给定一个环，环上每个点是三种颜色（RGB）之一，若一个点左右两边点的颜色不一样，你就可以任意改变这个点的颜色。

问能否在$10n$次操作内，把一个环变成另一个。如果能，给出构造。$5\le n\le 10^5$。

首先注意到，本题操作可逆。

如果这个环一个修改都做不了，那就是 trival 情况。

否则我们可以想办法把这个环变成：任意两个距离为$2$的点异色的环。

然后让两个环走到中间状态就行。

C 组

Robot Arms

规定一个机械臂是$m$段臂，第$i$段长度为$d_i$。其中一端连在$(0,0)$的位置。机械臂只允许平行于坐标轴（上下左右）放置。

二维平面给你$n$个点$(x_i,y_i)$。要求你构造一个$m\le 40$的机械臂（长度自定），使得机械臂的另一端可以通过恰当的放置来分别落在这$n$个点上（$n$个方案）。要求给出构造方案，以及落在这$n$个点上的方案。

$|x_i|,|y_i|\le 10^9$。

如果$(x_i+y_i)$的奇偶性都一样，才可能有解。

容易想到二进制构造。设$d_i=2^{m-i}$，则可以归纳法证明，满足$|x_i|+|y_i|<2^m$的点都可以落到。

如果$(x_i+y_2)\bmod 2=0$，需要在开头加一段长度为$1$的臂。

至于落在一个点上的方案，可以递归构造。

时间复杂度很小。

代码

Not Same

大小为$n$的序列$a_1, a_2,\cdots, a_n$，满足$1 \le a_i \le n$。每次你可以选择一个子集的元素并且把这个子集的元素都$-1$，你需要在至多$n + 1$次操作之内把所有数变成$0$。每次选择的子集不能相同。

$1 \le n \le 1000$。

按降序排序，考虑这样构造：

复杂度$O(n^2)$。

Inverse of Rows and Columns

给定一个$n \times m$的$01$矩阵$A$，你可以选择任意行翻转、任意列翻转。问能否使得$A_{11},A_{12},\cdots,A_{1m},A_{21},\cdots,A_{2m},\cdots,A_{n1},\cdots,A_{nm}$变成非降序列。

$1\le n,m\le 200$。

特判$n=1$的情况。

容易发现，我们最终的方案，要么第一行全 0，要么最后一行全 1。而这样就可以确定列的选择。然后再判一下选择行是否有解即可。

时间复杂度$O(nm)$。

代码

Construct the Binary Tree

给定$n,d$，构造一个$n$个点的二叉树，满足所有节点的深度之和等于$d$。$1000$组询问。

$n,d\le 5000$。

先考虑构造一棵完全二叉树。然后我们每次让总深度加 1。

方法很简单。固定一条最长的链。 每次选择一个深度最深不在链上的点，把它往下移一个位置，或者接在链上在往下移一个位置即可。合理安排顺序以避免 3 叉的情况。

时间复杂度$O(nT)$。

代码

Skolem XOR Tree

给定$n$，构造一棵$2n$个节点的树，其中点权$v_i = v_{n+i} = i$，要求$i$和$i + n$路径上所有点权的异或和恰好是$i$（包含端点）。

$1 \le n \le 10^5$。

如果$n=2^k$则无解。

考虑到$2k\oplus(2k+1)=1$，因此我们想办法围着$1$构造菊花。对于$k(1\le 2k<n)$，我们构造

$${\color{blue}2k}-{\color{red}2k+1}-1-{\color{blue}2k}-{\color{red}2k+1}$$

的链。这样$2k$和$2k+1$的条件就同时满足了。

对于$1$的条件，则构造${\color{red}1}-2-3-{\color{blue}1}$即可。

这样对于$n$的奇数的情况是适用的。对于$n$是偶数的情况，我们要再加一对$n$的点进去。

那么我们找到$1\le x,y<n,x\oplus 1\oplus y=n$的两个数$x,y$（可以证明一定存在），然后构造${\color{red}n}-x-1-y-{\color{blue}n}$即可。

时间复杂度$O(n)$。

代码