自动搬运

查看原文

来自洛谷，原作者为

	Karieciation cf:大1656 rating ，小1721 rating || 不爱打AT || 最后更新时间：2025.8.18 10:55 (UTC+08:00)——不保证及时更新

搬运于2025-08-24 22:03:39，当前版本为作者最后更新于2025-07-21 16:55:32，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目大意分析

题目描述说的一坨。简单分析一下可以将题目理解为在一个长为 $n$ 序列中加入 $k$ 个数，只要有两个相邻的数相等就将它们合成一个数，设这两个数是 $x$，合并后变为 $x+1$。最后我们希望加完 $k$ 个数之后使这个序列合并成 $[30]$。

AC之路（思路讲解）

这个题目一眼构造题，但是怎么构造正确序列呢？

不难看出这道题可以用单调栈构造。因为我们发现，如果有一个数无法合并，且左边和它紧邻的数和右边和它紧邻的数都比他大，这个数就没法合并了（还是很好看出来的）。我们可以假设自己只能在序列末放数，维护一个单调递减的栈，那就好维护啦（而且题目保证有解，我们只需要维护而不是纠错）。

既然我们设在序列末尾插入数，我们不妨设在以 $i$ 结尾时的序列末尾插入数，插入的数使用 vector 维护。

单调栈里只剩一个数了，但没到 $30$，此时我们只需要不断往后加数给它凑到 $30$，所以 $i=n$ 时特判！

它要求插入 $k$ 个数？那也没关系，我们可以使用递归把我们加入的数拆开输出，直到插够 $k$ 个数为止。

AC代码

写的一坨，将就看吧（其实我还有更丑的代码）。

#include<cstdio>
#include<vector>
#define LF putchar(10)
#define SP putchar(32)
const int N = 1e6 + 5;
template<typename T>void read(T& x) {
	x = 0;
	char ch = getchar();
	while (ch < 48 || ch > 57)ch = getchar();
	while (ch > 47 && ch < 58)x = (x << 3) + (x << 1) + (ch & 15), ch = getchar();
}
template<typename T, typename... Args>void read(T& x, Args&... args) {
	read(x);
	read(args...);
}
template<typename T>void write(T x) {
	if (x < 0) {
		putchar(45);
		x = -x;
	}
	if (x > 9)write(x / 10);
	putchar(x % 10 | 48);
}
int n, m, tp, sum;
int a[N], stk[N];
std::vector<int> G[N];
void f(int x) {
	if (x == 0) {
		putchar(48);
		SP;
	} else if (sum < m) {
		sum++;
		f(x - 1);
		f(x - 1);
	} else {
		write(x);
		SP;
	}
}
int main() {
	read(n, m);
	for (int i = 1; i <= n; i++) {
		read(a[i]);
		if (tp && a[i] == stk[tp]) {
			stk[tp]++;
			while (tp > 1 && stk[tp] == stk[tp - 1])
				stk[--tp]++;
		} else if (tp && a[i] > stk[tp]) {
			G[i - 1].push_back(stk[tp]);
			stk[tp]++;
			while (tp > 1 && stk[tp] == stk[tp - 1])
				stk[--tp]++;
			while (a[i] > stk[tp]) {
				G[i - 1].push_back(stk[tp]++);
				while (tp > 1 && stk[tp] == stk[tp - 1])
					stk[--tp]++;
			}
			stk[++tp] = a[i];
			while (tp > 1 && stk[tp] == stk[tp - 1])
				stk[--tp]++;
		} else
			stk[++tp] = a[i];
		if (i == n) {
			while (stk[tp] < 30) {
				while (tp > 1 && stk[tp] != stk[tp - 1] || (tp == 1 && stk[tp] < 30))
					G[n].push_back(stk[tp]++);
				while (tp > 1 && stk[tp] == stk[tp - 1])
					stk[--tp]++;
			}
		}
	}
	for (int i = 1; i <= n; i++)
		sum += G[i].size();
	for (int i = 1; i <= n; i++) {
		write(a[i]);
		SP;
		if (G[i].size())
			for (int p : G[i])
				f(p);
	}
	return 0;
}