【笔记】构造题
听说多做构造题长脑子，至少能让我从机械性的考试里清醒一点吧
递归子问题
剔除问题边缘
例题 🔗，容易想到排序，接下来要考虑最大最小值（即所谓问题边缘）的特征，剔除之，递归子问题。
奇偶性划分
例题 🔗
给定一个数组 \(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