QOJ 2486 Build the String

考虑当字符串全为 \(\texttt{b}\) 时，可以通过 \(\text{copy}\) \(n - 1\) 次再 \(\text{fuse}\) \(n\) 次。
这启发从连续段来做，先按顺序构造出一个个连续段，最后 \(\text{fuse}\) 合为这个串。

若第一个连续段为 \(\texttt{a}\)，则可以通过 \(\text{swap}\) 事先交换 \(\texttt{ab}\)，于是就统一为了 \(\texttt{b}\) 开头。

令连续段个数为 \(m\)，第 \(i\) 段的长度为 \(len_i\)。
对于前 \(m - 2\) 段，因为当前连续段对应的字符在之后还要用到，所以需要多留一个这个字符，\(\text{copy}\) \(len_i\) 次，\(\text{fuse}\) \(len_i - 1\) 次。
此时这个栈顶是个 \(\texttt{a, b, bbbbb}\) 的形式，而下一个连续段需要的是 \(\texttt{a}\)，要放在开头，下下个连续段需要 \(\texttt{b}\)，要放在 \(\texttt{a}\) 后面像现在这样操作，所以 \(\text{swap, roll}\) 变为 \(\texttt{bbbbb, b, a}\) 的形式，这里有个剪枝，当 \(len_i = 1\) 时 \(\text{swap}\) 并没有效果，可以删去。
对于第 \(m - 1\) 段，其对应的字符后面已经不用了，可以直接合并上，\(\text{copy}\) \(len_{m - 1} - 1\) 次，\(\text{fuse}\) \(len_{m - 1} - 1\) 次，那么接下来直接 \(\text{swap}\) 即可把第 \(m\) 段的字符放在栈顶。
对于第 \(m\) 段类似 \(m - 1\) 段，\(\text{copy}\) \(len_{m} - 1\) 次，\(\text{fuse}\) \(len_{m} - 1\) 次。
最后考虑把这 \(m\) 段合并起来，\(\text{fuse}\) \(m - 1\) 次。

对于 \(m = 1\) 次数显然为 \([s_1 = \texttt{a}] + 2n - 1\)。
对于 \(m\ge 2\) 总的次数为 \([s_1 = \texttt{a}] + 2n + \sum\limits_{i = 1}^{m - 2}[len_i\ge 2] + m - 4\)，最坏情况即 \(s_1 = \texttt{a}, len_i = 1 + [i\le m - 2]\) 时总次数为 \(1 + 2n + \frac{n}{2} - 1 + \frac{n}{2} + 1 - 4 = 3n - 3\)。

#include<bits/stdc++.h>
const int maxn = 1e5 + 10;
char s[maxn];
int len[maxn];
std::vector<std::string> ans;
int main() {
	scanf("%s", s + 1);
	int n = strlen(s + 1);
	if (s[1] == 'a') {
		ans.push_back("swap");
		for (int i = 1; i <= n; i++) s[i] ^= 'a' ^ 'b';
	}
	int m = 0;
	for (int l = 1, r; l <= n; l = r) {
		for (r = l; r <= n && s[r] == s[l]; r++);
		len[++m] = r - l;
	}
	if (m == 1) {
		for (int i = 1; i < n; i++) ans.push_back("copy");
		for (int i = 1; i < n; i++) ans.push_back("fuse");
	} else {
		for (int i = 1; i <= m - 2; i++) {
			for (int j = 1; j <= len[i]; j++) ans.push_back("copy");
			for (int j = 1; j < len[i]; j++) ans.push_back("fuse");
			if (len[i] > 1) ans.push_back("swap");
			ans.push_back("roll");
		}
		for (int i = 1; i < len[m - 1]; i++) ans.push_back("copy");
		for (int i = 1; i < len[m - 1]; i++) ans.push_back("fuse");
		ans.push_back("swap");
		for (int i = 1; i < len[m]; i++) ans.push_back("copy");
		for (int i = 1; i < len[m]; i++) ans.push_back("fuse");
		for (int i = 1; i < m; i++) ans.push_back("fuse");
	}
	printf("%zu\n", ans.size());
	for (std::string a : ans) std::cout << a << '\n';
	return 0;
}