构造题做题记录

更新中。

加训构造。/fendou

CF1917E

发现我们如果把一个 \(2\times2\) 的矩阵填满 \(1\)，不会有影响。

当 \(k\) 为 \(4\) 的倍数，直接填就可以了。

当 \(k\) 为奇数显然无解，因为你无法让每行奇偶性相同。

当 \(k\) 除 \(4\) 余 \(2\)，如果 \(k\) 为 \(2\) 或 \(n\times n-2\) 时无解。

不然的话，我们可以在一个 \(4\times4\) 的矩形里把 \((1,1)\)，\((1,2)\)，\((2,1)\)，\((2,3)\)，\((3,2)\)，\((3,3)\) 填 \(1\)，剩下直接填。

注意到 \(k=n\times n-6\) 时这时爆的。我们可以在 \(4\times4\) 的矩形里多填 \((1,3)\)，\((1,4)\)，\((4,3)\)，\((4,4)\)。

ATarc122e

题意其实就是每位填的数要保证 \(\gcd(\text{lcm}_{j<i}(x_j),x_i) \ne x_i\)。

考虑从后往前填数，每次只要把任意满足条件的填入即可。

注意到 \(\gcd(\text{lcm}_{j<i}(x_j),x_i)\) 其实相当于 \(\text{lcm}_{j<i}(\gcd(x_j,x_i))\)，然后就可以直接枚举做了。

CF1667C

假如我们放 \(k\) 个后，假设放在左上角，使得右下只有 \((n-k)\times(n-k)\) 个格子没被覆盖，我们要用对角线去覆盖它们。

\((n-k)\times(n-k)\) 个格子有 \(2\times(n-k)-1\) 条对角线，所以 \(k \ge 2\times(n-k)-1\)，即 \(k \ge \lfloor \frac{2n+1}{3} \rfloor\)。

当 \(k=\lfloor \frac{2n+1}{3} \rfloor\)，我们可以考虑先在 \((1,1)\) 放一个后，然后横坐标 \(+1\)，纵坐标 \(+2\)，再放一个后，不停地放，直到出右上角的 \(k\times k\) 的矩形为止。然后我们再横坐标 \(+1\)，纵坐标为 \(2\) 的点开始用同样的方式放。

为什么这是对的？我们不妨给对角线标号，令 \((k+1,k+1)\) 所在的对角线为 \(0\)，它左边的对角线分别为 \(-1,-2\dots\)，右边的对角线分别为 \(1,2\dots\)，我们第一个在 \((1,1)\) 的后覆盖了对角线 \(0\)，后面每次的后覆盖了上一条 \(-1\) 的对角线。而在 \((\lfloor \frac{k}{2} \rfloor+1,2)\) 的点覆盖了对角线 \(n-k-1\)，后面每条覆盖了上一条 \(-1\) 的对角线。

AThitachi2020c

首先，只有当两个数模 \(3\) 都为 \(1\) 或都为 \(2\) 时才可能不合法。

我们将这棵树黑白染色，两个点相距为 \(3\) 必定一个为黑点一个为白点。

当黑点和白点数量都大于 \(\lceil \frac{n}{3} \rceil\)，我们可以模 \(3\) 余 \(1\) 全填黑点，模 \(3\) 余 \(2\) 全填白点，剩下随便填。

当黑点和白点数量中有一个小于 \(\lceil \frac{n}{3} \rceil\)，不妨假设时黑点。我们可以把黑点用模 \(3\) 余 \(1\) 的数填满，剩下全填白点。

CF297C

有一个比较牛的构造。

考虑将序列 \(s\) 排序后平均分为 \(3\) 段。

• 对于第 \(1\) 段，构造 \(a_i=i\)，\(b_i=s_i-a_i\)。

• 对于第 \(2\) 段，构造 \(b_i=i\)，\(a_i=s_i-b_i\)。

• 对于第 \(3\) 段，构造 \(b_i=n-i\)，\(a_i=s_i-b_i\)。

解释一下为什么这是对的。

对于 \(b\)，显然第 \(2\) 段和第 \(3\) 段的是两两不同的，符合要求。

对于 \(a\)，第 \(1\) 段和第 \(3\) 段内部一定是单调递增的，而第 \(3\) 段所有数一定大于第 \(1\) 段，所以两两不同，符合要求。

CF1028E

有一个简单的想法是构造一个序列满足 \(a_i<a_{i+1}\) 且 \(a_{i+1}-a_i=b_i\)。容易想到构造 \(a_i=\sum_{j=i}^{n}b_i\)。

但如果存在 \(a_{i+1}|a_i\) 是会爆。所以我们可以把 \(b\) 中的最大值移到 \(b_n\) 的位置，同时要满足 \(b_{n-1}\neq b_n\)，这样就能保证不存在整除关系。

如果 \(b_1=b_2=...=b_{n-1}=0\) 是会爆，因为 \(b_n \mod b_1=0\)。所以我们让 \(a_i=(\sum_{j=i}^{n}b_i)+b_n\)，\(a_n=b_n\) 就行了。

但当所有 \(b\) 相等时不存在一个这么一个最大值。可以证明，只有 \(b_1=b_2=...=b_n=0\) 时才有解。

如果 \(b_1=b_2=...=b_n=x\)（\(x\) 不为 \(0\)），一定存在 \(a_i<a_{i+1}\)，即 \(a_i=x\)，那所以 \(a_j\) 必为 \(x\) 的倍数，则必有 \(a_i \mod a_{i+1}=0\)，所以不成立。