2022 年牛客多校第九场 E 题题解

E Longest Increasing Subsequence

题意：构造一个长度不超过 $100100$ 的排列，使得其最长上升子序列个数恰好为 $mm$ 个。$m\le 1\times 10^{9}m\; \backslash leq\; 1\backslash times\; 10^9$。

解法：为了保证 LIS 的个数，一个基础的构造是 $2,1,4,3,6,5\cdots ,2n,2n-12,1,4,3,6,5\backslash cdots,2n,2n-1$，这样可以使得 LIS 的个数为 $2^{n}2^n$。同时此时的 LIS 序列长度为 $nn$。最后添加一个最大值，作为全部 LIS 的终止。接下来考虑利用二进制拆分，如何填补更小的 $2^{i}2^i$。

一个可行的操作是，从大到小的考虑 $2^{i}2^i$，从后往前的往初始序列中插入。在第 $2i+12i+1$ 个数字的前面插入一个比 $2n2n$ 大的数字，记为 $xx$，这样就可以让该数字可以在前面有 $2^{i}2^i$ 种选择，同时若选择了新加入的数字，则后面只能选最大值。但是选择到了这里 LIS 的长度不够，所以需要在 $xx$ 的往后增补一些数字。注意到对于 $2^{j}2^j$ 的考虑，一定是在 $2^i,i>j2^i,i>j$ 之后考虑的。因而 $2^{j}2^j$ 这里的 LIS 长度增补可以利用后面增补的数字，只需要增补到 $nn$ 的长度即可。因而若 $2^{i}2^i$ 这里已经加了 $xx$ 个数字，$2^{j}2^j$ 这里只需要额外增补 $n-j-xn-j-x$ 个数字即可。

例如，考虑 $(100101{)}_2(100101)\_2$，那么首先构造 $2,1,4,3,6,5,8,7,10,9,12,112,1,4,3,6,5,8,7,10,9,12,11$。首先插入一个最大的：$2,1,4,3,6,5,8,7,10,9,12,11,1002,1,4,3,6,5,8,7,10,9,12,11,100$，考虑 $2^{2}2^2$，因而在 $66$ 前面插入一个比最大值小的数字，例如 $9999$。但是这样取到 $9999$ LIS 长度不足，因而还需要增补四个数字（为了全部整数因而要将 $9999$ 适当下调为 $9696$）：$2,1,4,3,(\underset{‾}{96},97,98,99),6,5,8,7,10,9,12,11,1002,1,4,3,(\backslash underline\{96\},97,98,99),6,5,8,7,10,9,12,11,100$。最后的 $2^{0}2^0$ 需要在序列的开头增补一个数字，同时为了满足 LIS 的长度， 因而需要开头加入两个数字：$(\underset{‾}{94},95),2,1,4,3,(\underset{‾}{96},97,98,99),6,5,8,7,10,9,12,11,100(\backslash underline\{94\},95),2,1,4,3,(\backslash underline\{96\},97,98,99),6,5,8,7,10,9,12,11,100$。最后再离散化一下就可以得到最终的排列。

这样的排列长度为：$2\times 30+30=902\backslash times\; 30+30=90$，满足条件，因为总的添加数字个数仅为 LIS 的长度。

#include <bits/stdc++.h>
using namespace std;
int main()
{
	int t, m;
	scanf("%d", &t);
	while(t--)
	{
		scanf("%d", &m);
		int len = 30;
		while (!(m >> len & 1))
			len--;
		vector<int> add(len, 0);
		int cnt = 0;
		for (int i = len - 1; i >= 0;i--)
			if (m >> i & 1)
			{
				add[i] = len - i - cnt;
				cnt += add[i];
			}
		printf("%d\n", 2 * len + cnt + 1);
		int base = 2 * len;
		for (int i = 0; i < len;i++)
		{
			while (add[i] && add[i]--)
				printf("%d ", ++base);
			printf("%d %d ", 2 * i + 2, 2 * i + 1);
		}
		printf("%d\n", 2 * len + cnt + 1);
	}
	return 0;
}