牛牛的构造
链接：https://ac.nowcoder.com/acm/contest/49888/E
来源：牛客网
题意：
构造一个长度为 n 的排列，使得这个排列恰好存在 k 个二元组 [i, j] ，满足 1 ≤ i < j ≤ n && ai − aj = \(2 ^ x\) (x∈N)
如果不存在一个数组满足条件，输出 -1，如果存在多个数组都满足条件，输出任意一个数组即可
分析：
先考虑不能构造的情况：
对较小的数考虑：
n = 5 时，排列中所有可能的数对：
n = 6 时，排列中所有可能的数对：
\[\begin{array}{|c|c|c|} \hline 6&->&2\\ \hline 6&->&4\\ \hline 6&->&5\\ \hline 5&->&1\\ \hline 5&->&3\\ \hline 5&->&4\\ \hline 4&->&2\\ \hline 4&->&3\\ \hline 3&->&1\\ \hline 3&->&2\\ \hline 2&->&1\\ \hline \end{array} \]n == 9时，排列中所有可能的数对：
\[\begin{array}{|c|c|c|} \hline 9&->&1\\ \hline 9&->&5\\ \hline 9&->&7\\ \hline 9&->&8\\ \hline 8&->&4\\ \hline 8&->&6\\ \hline 8&->&7\\ \hline 7&->&3\\ \hline 7&->&5\\ \hline 7&->&6\\ \hline ...&...&...\\ \hline \end{array} \]可以发现只有当 n 取到 \(2 ^ k + 1\) 时，才会对数对的数量贡献值改变，由此计算每个 i 贡献值为：
add[i] = $\lfloor $log2(i - 1) \(\rfloor\) + 1
相加之后即为 n 个数能够造出的最多的满足条件的个数，大于直接"NO"
对与能构造出的情况，由于 i 的贡献值范围为 [1, add[n]]，所以用类似于整数拼凑的方法必能选出若干个数递减放置得到答案，对于没有被选择的数，在最后递增输出就不会对答案产生影响
void solve()
{
int sum = 0;
cin >> n >> k;
for (int i = 2; i <= n; i++)
{
add[i] = floor(log2(i - 1)) + 1;
sum += add[i];
}
if (sum < k)
cout << "-1" << endl;
else
{
for (int i = n; i >= 2; i--)
{
if (k >= add[i])
{
st[i] = true;
cout << i << " ";
k -= add[i];
}
if (k <= 0)
break;
}
for (int i = 1; i <= n; i++)
{
if (!st[i])
cout << i << " ";
}
cout << endl;
}
}