P7734

RegisterFault · 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");
}