听说多做构造题长脑子，至少能让我从机械性的考试里清醒一点吧
递归子问题
剔除问题边缘
例题 ?，容易想到排序，接下来要考虑最大最小值（即所谓问题边缘）的特征，剔除之，递归子问题。
奇偶性划分
例题 ?
给定一个数组 \(A\)，判断能否将 \(A\) 进行重新排序得到 \(B\)，使得 \(B\) 不存在三个位置，其形成等差；给出一个解。
首先，猜想对于任意 \(n\)，序列 \(1,2,...,n\) 有解，打表能验证；既然有解，那么其中取一些数字肯定也有解，只要每个数字出现次数不超过 2
其次，对序列 \(n\)，怎么构造呢？对于一个等差数列，考虑奇偶位置，分成 \(135\dotsb|246\dotsb\)，对于左右两半部分，不存在一边取2个一边取1个构成答案的情况，然后递归两边的子问题。
Exactly Equal \(k\)
构造某个序列/树/图之类，其某个特征值恰等于某个数字 \(k\)。
二进制拆分
可以考虑从 \(k\) 的二进制拆分下手，看看能不能构造出每个幂，以及怎么组合。
例题 ?
构造一个 \(1,2,...,?\) 的排列，使其恰好有 \(?\) 个不同的最长上升子序列。\(?≤10^9\)，要求 \(?≤100\)。
题解：记 \(?\) 的二进制表示为 \(?_? ?_{?−1}...?_0\)，其中 \(?_?=1，?_?∈{0,1}\)。
先做出最高位，构造 \(2,1,4,3,6,5,...,2?,2?−1\)，然后低到高依次考虑 \(?\) 的二进制位。
如果 \(?_?=1\)，就在第 \(2?\) 个数之后插入一个大于 \(2?\) 的数字 \(?_?\)，适当取值使得这些 \(?_?\) 是递增的。
这样原序列的 LIS 长度会是 \(?+1\)，包含 \(?_? (?<?)\) 的上升序列长度可能不够。
只需要紧接着每个 \(?_? (?<?)\) 再插入一些递增的数字，并重新调整每个 \(?_?\) 的取值即可。容易发现 \(?_? (?<?)\) 后边需要插入的数字个数就是 \(?\) 的二进制表示下第 ? 位往上连续 0 的个数。
这样构造出来的排列长度不超过 \(3⌊\log_2?⌋+1\)。
m = 19 = 1+2+16
2 1 4 3 6 5 8 7
9 2 1 10 4 3 6 5 8 7 11
9 2 1 10 11 12 4 3 6 5 8 7 13