自动搬运

查看原文

来自洛谷，原作者为

	RegisterFault **

搬运于2025-08-24 22:32:35，当前版本为作者最后更新于2024-05-25 17:29:18，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

提供一个高级一点的乱搞。

首先发现我们可以利用题目的操作实现这样一个东西：对于 $u < v - 1$，可以做到交换 $s_u, s_v$，同时交换 $s_{u +1}, s_{v +1}$。实现这个交换只需要花费三步。

做法很简单。首先把 $u, u + 1$ 挪到空位上，把 $v, v +1$ 挪到原来 $u, u +1$ 所在的位置上（这里现在是空位）。最后在把 $u, u + 1$ 挪到空位。

具体的，假设现在有串 123456__。需要交换 $(1, 2)$ 和 $(5, 6)$。首先把 $(1, 2)$ 同时挪到最后，变成 __345612。然后把 $(5, 6)$ 挪到空位，变成 5634__12。最后把 $(1, 2)$ 挪回去，变成 563412__。

从前往后构造。我们构造目标序列 $t = \texttt{0000...1111...}$。对于 $a_i \ne t_i$ 的位置，我们暴力找到后面的位置 $j$ 满足 $a_j = t_i$，然后交换一下 $i$ 和 $j$。

由于上述构造中空位的位置不变，因此实现起来非常简单。然后你发现你被卡了。当然这是一个假贪心，很容易被卡掉。

接下来是本文精华。我们随机一个排列 $p$，先构造方案使得 $a \rightarrow p$，再构造排列使得 $p \rightarrow t$。由于交换的代价为 $3$，而一个序列变换成另一个序列需要的步数最多为 $3n$，所以这个做法步数是 $6n$ 级别的。由于排列是随机的，答案远远小于这个量级。

对着这个做法卡个五十次就过了。注意 $n \le 10$ 可能被出题人刻意卡了，需要爆搜一下。

下面是没写爆搜的代码。

const int N = 2010;
int a[N], tmp[N], t[N], n, m;
char s[N];
vector<pair<int, int>> path;
void Swap(int u, int v) {
	swap(a[u], a[v]); swap(a[u + 1], a[v + 1]);
	path.push_back({u, m + 1});
	path.push_back({v, u});
	path.push_back({m + 1, v});
}
void Construct() {
	int s0 = 0, s1 = 0;
	memcpy(tmp, a, sizeof tmp);
	rep(i, 1, m) a[i] == 0 ? s0 ++ : s1 ++ ;
	rep(i, 1, s0) t[i] = 0; rep(i, s0 + 1, m) t[i] = 1;
	random_shuffle(t + 1, t + m + 1); path.clear();
	rep(i, 1, m) if (a[i] != t[i]) {
		bool flg = 0;
		rep(j, i + 2, m - 1) if (a[j] == t[i]) {
			flg = 1; Swap(i, j); break;
		} if (!flg) { memcpy(a, tmp, sizeof a); return; }
	}
	rep(i, 1, s0) t[i] = 0; rep(i, s0 + 1, m) t[i] = 1;
	rep(i, 1, m) if (a[i] != t[i]) {
		bool flg = 0;
		rep(j, i + 2, m - 1) if (a[j] == t[i]) {
			flg = 1; Swap(i, j); break;
		} if (!flg) { memcpy(a, tmp, sizeof a); return; }
	}
	printf("%d\n", (int)path.size());
	for (auto i : path) printf("%d %d\n", i.first, i.second);
	exit(0);
}
int main() {
	srand(998244353);
	scanf("%s", s + 1); n = strlen(s + 1);
	m = n - 2; rep(i, 1, m) a[i] = s[i] - '0';
	rep(i, 1, 100) Construct(); puts("-1");
}