「学习总结」构造题选
构造题都是好题
构造题选
热身一
构造三个长度为 \(n\) ,的排列使得 \(a_i + b_i \equiv c_i \pmod n\) 无解输出 -1
对等式两边分别求和。当 \(n\) 为 偶数时，等式左边的值为 \(n(n-1) \equiv 0 \pmod n\) ，等式右边的值为 \(\frac{n(n-1)}{2} \equiv \frac{n}{2} \pmod n\) ，显然无解。\(n\) 为奇数时，直接取 \(a=b={0, 1, 2,\cdots n-1}\)
热身二
一个 \(2n\) 个点的完全图，把这些边分成 \(2n-1\) 组，每组 \(n\) 条边，且每组都是一个匹配。 （同一组内任意两条边没有公共点）。 \(n \le 1000\)
对于一条边 \((u, v)\) ，放入 第 \((u, v)\pmod {2n-1}\) 组即可。
热身三
一个 \(2^n - 1\) 个点的完全图，你需要找出尽量多的不交三元环。\(n\le 10\)
分析答案上界 \(\frac{(2^n-1)(2^n-2)}{6}\).发现是整数，应该能取到。
三元环可以用 \((u, v,w)\) 表示，枚举 \(u, v\) ，取出所有 \(u \oplus v\oplus w=0\) 的三元环即可。考虑这样算出的答案需要除以 \(3!\)。和上界相同，证明这种取法最优。
栗题一
给出一张大小为 \(n\le 1000\) 的完全图，给出一种方案，使得选出最多边互不相交的生成树.
分析答案上界为 \(\frac{n(n-1)}{2(n-1)} = \lfloor\frac{n}{2}\rfloor\)。
归纳构造：
- 假设 \(n=2k\)个点已经构造好了，考虑加入一个点 \(n=2k+1\)。这样就随便找 \(k\) 个点，然后分别在每个点中选出不同的 \(k\) 个树 和新点连边即可。
- 假设 \(n=2k\)个点已经构造好了，考虑加入两个点 \(n=2k+2\)，记作 \(a, b\)。考虑将 \(n\) 个点分为 \(A, B\) 两组，\(a\) 和 \(A\) 中的点，\(b\) 和 \(B\) 中的点分别连边，然后考虑上界多出了一颗树，这时就可以：\(a\) 连 \(b\) ，然后 \(a\) 连 \(B\) ，\(b\) 连 \(A\)。就多构造了一棵树。
栗题二
平面上有 \(n \le 100\) 个蓝色的点，需要加上 \(k\) 个红色的点，使得任意三个蓝点组成的三角形内部都必须至少有一个红点，红点必须在内部，不能在边上。最小化 \(k\) 的大小。
分析出答案下界为 \((2n-2-\text{凸包上的点数})\).
考虑到，一堆点，依次求出凸包，对于相邻两层凸包之间进行三角剖分，三角形个数为相邻两凸包点数和。最内层的凸包能划分出 \(n-2\) 个三角形，设 \(l_i\) 为从外到内第 \(i\) 层凸包上的点数。考虑到答案为 \((l_1+l_2) + (l_2+l_3)+(l_3+l_4) +\cdots+(l_{k-1}+l_k)+(l_k - 2)=2n-2-l_1\)。因为这样划分出来的三角形两两不交，所以这一定是答案的一个下界。
考虑如何构造能到达答案的下界。
随机一个向量\((x_0, y_0)\)，长度为无限小，在每一个点 \((x_i, y_i) \pm (x_0, y_0)\) 处放置两个红点，这样的答案是 \(2n\) 的，因为 三角形内角和为 \(180^o\) ，一个点和与其对应的两个红点构成的角，角度为 \(180^o\) ，在随机意义下，每个三角形内部必然有且仅有一个点。对于凸包外的点可以删除，易知，可删的点有 \(\text{凸包上的点数}-2\) 个。这样构造可以达到下界。
栗题三
给出一张 \(n\times n\) （\(n\le 40\)）的方格表，每个格子里面有一个字母。每次可以把某一行所有字母右循环平移若干格，某一列的所有字母下循环平移若干格。若某行有连续的三个字母 \(k, e, y\) 则形成一个键，在 \(10000\) 次操作中最大化键的数量。
- 当 \(3 \not | \ n\) 时，方法显然，每一行一定要形成 \(keykeykey\cdots\) 的形式，考虑像魔方一样的依次把每一列填成该填的字母，注意如果这一个格子无法填成想要的字母（后面没有这样的字母了），优先把后面与 \(k, e, y\) 不同的
垃圾字母填入。 - 当 \(3\ |\ n\) 时，前面的操作一样做，只需要特殊考虑最后一列怎么做，如果只剩下最后一列没有排好，相当于考虑如何交换最后一列的任意两个格子上的字母。考虑将倒数第二列的最后一行当作转移点，对最后一列执行交换操作，就跟某种排序算法一样即可。
栗题四
给定一个 \(1\) ~ \(n^2+n\) 的排列，选出一个长度为 \(2n\) 的子序列，使得子序列中 \(\forall k\in n\) 有第 \(2k\) 小的和 \(2k-1\) 小的数字相邻。
把排列分成 \(n\) 段，每段 \(n+1\) 个数字。依次求出每段里面最小和次小值。找到次小值最小的一段，把这一段的最小值和次小值放入答案序列，然后删除这一段。再把其他段中比这个次小值小的数字删除，重复上面的操作。可以证明，最后的删除操作，会在每一段中至多删去 \(1\) 个数字（由于选定的段是次小值最小的一段），所以保证答案存在。
栗题五
给出一个 \(2n\times m\) 的棋盘，有 \(n\times m\) 个红格子，有 \(n\times m\) 个蓝格子，保证右下角为蓝色，左上角为红色，任意两个同色的格子中心都有一条边。要求给每条边定向，需要保证最后所有边的矢量和为 \(0\).
- \(n\times m\) 为奇数，对蓝色和红色的连通块，分别跑欧拉回路。
- \(n\times m\) 为偶数，去掉左上和右下的格点，剩下的点跑欧拉回路，然后考虑所有端点为左上、右下格点的边的方向。依次考虑每一对关于棋盘中心对称的点对。
- 若两个点对颜色不同，分别和左上、右下的格点连边即可抵消
- 若两个点对颜色相同，则同时向自己颜色的格点连边。这样连边，两个向量和为指向这个颜色的顶点的对角线。易知这样的点对数量相同，所以最后也可以相互抵消。
栗题六
给定一个环，环上的每个点是三种颜色 (RGB) 之一，若一个点左右两边的点颜色不一样，就可以将这个点改变成任意颜色。给出两个环，问能否在 \(10n\) 次操作内把一个环变成另一个，给出方案 。 \(5 \le n \le 10^5\)。
一个经典套路就是，考虑到操作可逆，可以考虑如何把两个环同时操作，变成同一个。
先考虑把两个环变成 “每个位置都可以操作的形式”，从某个可操作的位置开始操作，让它变成与左右两边距离为 \(2\) 的点颜色不同的颜色。然后再操作左或右边的点，依次进行这样的操作，就可以把这个环变成“每个位置都可以操作的形式”。
然后依次考虑把其中一个环的每个位置变成另外一个环的对应位置的颜色。同时需要保证任意一个位置的颜色可变，即：保证任意距离为 2 的位置颜色不同。为了方便考虑，可以把一个环根据位置下标的奇偶拆成两个环，问题变成了修改一个位置的颜色后，和两边位置的颜色都不同，如果改后不能保证，可以先修改两边位置的颜色。由于目标环也保证了任意位置颜色可逆，所以对于当前环的这种策略的操作，一定存在合法地操作。
栗题七
nb 题目不做评价……
想办法每次把最大值放到右下角，每次从没排好序的最后一行开始，依次让每行的最后一列成为一行中的最大值，然后对最后一列当成行，把最大值移动到第一行的最后一列，然后转一圈，移动到没排好序的右下角。注意没有保证任意元素不同，判断比较麻烦。
栗题八
存在 \(n\) 个数字。给出 \(n\)，和 \(m\) 个限制，限制形如 \(a_i, a_j\) 两个数字的最大值或最小值为 \(w\)。构造一种合法的方案。 \(n \le 10^5\)。
根据每个限制，可以给每个数字确定一个上界和下界。一定存在一种赋值方案，使得每个变量要么取上界，要么取下界。因为如果一个数字取下界和上界构成的开区间中的值，这个数字没有贡献，所以取要么取上界要么取下界的方案一定合法。
直接 2-SAT，判断每个数值取上界还是下界。
栗题九
给出一张 DAG，保证每个点入度不超过 \(2\)，保证出度为 \(0\) 的点有且仅有一个。每个点都有一些权值，这些权值均为 (0 / 1)，初始时，每个入度为 \(0\) 的节点有一个权值，其他点的权值为其他两个子节点权值的与非（先取 and 再取 not）， 钦定一些入度为 \(0\) 的节点权值，使其满足如下条件。（设：叶子节点为入度为 0 的点，根节点为出度为 0 的点 233） - 没有钦定的叶子节点全取 \(1\) 时，和叶子节点全取 \(1\) 时，根节点取值相同。 - 没有钦定的叶子节点全取 \(0\) 时，和叶子节点全取 \(0\) 时，根节点取值相同。 构造一种钦定方案，使得钦定的点数量尽可能多。
首先确定一下：叶子节点全部取 \(0\) 时，根节点的取值 \(A\)。叶子节点全取 \(1\) 时，根点的取值 \(B\)。 - 如果 \(A = B\)，那么最优答案一定是钦定所有叶子节点为同一值。 - 如果 \(A\not = B\)，设 \(f(i)\) 表示，当编号小于等于 \(i\) 的叶子赋值为 \(1\) 其余的赋值为 \(0\) 时根节点的取值。试图确定一个 \(i\) 使得 \(f(i) = A\) 且 $ f(i + 1)=B$ 这时最优的方案就是钦定 \([1, i]\) 和 \([i + 2, n]\) 这些点，这样 钦定的点有 \(n - 1\) 个，已经取到了当前情况下的最优解。 - 讨论一下 \(i\) 的存在性，因为 \(f(0) \not = f(n)\) 所以一定存在一个 \(i\) 使得函数值发生改变。 - 考虑一下如何求这个 \(i\) 值，可以二分。虽然函数不满足单调性，但是我们也不关心某个极值，只是希望快速求一个拐点，根据二分值处的函数取值，一样能够确定拐点一定在区间的哪边。(界值定理)
栗题十
一个 \(n\) 个点的简单无向图（无重边，无自环但不一定联通），你可以询问若干次，每次询问一棵 \(n\) 个点的树，交互库会返回这棵树里面有多少边和无向图中的点有多少条边重合。
首先确定节点 \(1\) 和哪些节点有边相连，只需要构造一个除掉节点 \(1\) 的链，然后枚举 \(i\)，让节点 \(1\) 和 节点 \(i\) 连边， 查询答案，考虑这些答案的最大值和最小值，取到最大值的边存在，取到最小值的边不存在 （若最大值最小值相同，则边要么都存在，要么都不存在，问一个菊花即可确定）。
考虑确定剩下的点 \(i\) 和哪些点有连边，考虑像线段树一样查询 和下标为某一区间 \([l, r]\) 的点是否有边相连，直接向这些点 \([l, r]\) 连边，其余的点向 \(1\) 连边，由于 \(1\) 和哪些点有边相连是已知的，所以可以直接算出点 \(i\) 向 \([l, r]\) 中的点有无连边，依次递归即可。
栗题十一
栗题十一
需要值域分块学后待补。
栗题十二
「CF1364E」给定一个 \([0, n-1]\) 的排列 p，每次询问 \((i, j)\)返回 \(p_i | p_j\)，最多 \(4269\) 次询问，推出这个排列。 \(n\le 2048\)。
考虑到确定哪一个位置为 \(0\) 即可确定所有位置的数字。
做法一
随机选择一个数字，让它或上其他所有数字，显然它和 \(0\) 取或能够取到最小值。再随机一个数字让这个数字和这些上一次取到最小值的数字取或，继续找到最小值，重复以上操作，直到最小值唯一。 每次迭代，二进制中 \(1\) 的个数期望减半，花费大概是 \(\mathcal{O}(n+\sqrt n + \cdots)\) 常熟较大
做法二
从前往后扫一遍，同时维护两个位置 \(a, b\) 表示前缀中可能为 \(0\) 的位置为 \(a,b\)， 考虑加入一个数字 \(c\) 如何维护:
- \(a | c > a | b\) 则 \(c\) 不可能为 \(0\).
- \(a | c < a | b\) 则 \(b\) 不可能为 \(0\).
- \(a | c = a | b\) 则 \(a\) 不可能为 \(0\).
注意到其实前两种操作只需要询问一次，而后一种操作虽然需要询问多次，\(a|c = a|b\) 的概率非常小。 可以考虑 \(random\_shuffle\) 之后再做防止被卡。