Problem: A题 Almost Correct

题意

• 给一个长度为n的未排序 ¹ 的$0101$串$ss$²
• 给一个操作：选中$0101$串中两个位置不同的数进行交换，如果这两个数位于前面的数不大于后面则不交换（即这次交换作废）
• 求如何操作可以使得除了题给字符串以外的所有长度为$nn$的字符串排序。（就是说一个怎样的操作序列可以使其他同长度的$0101$字符都被排序，但题给的不被排序）

思路

我们可以考虑给定字符串与其他字符串的不同之处，首先可以发现当前字符串与其他字符串肯定是存在某些地方$0101$不同，但这样的不同没有共性，我们想能不能把它给固定，使得给定字符串与其他字符串都有相同的不同之处。

首先我们考虑固定一个值，就是在一些操作后只有给定字符串的第一位为$11$，其他字符串第一位都是$00$，发现必然不能实现，因为想保持某一位为$11$，就只能让这一位对其前面数和后面的为$11$的位置操作，但必然有与给定字符串不同的字符串但是后面$11$的位置相同。

再考虑固定两个值，我们可以固定一个最左边的$11$（设该下标为$ll$），和最右边的$00$（设该下标为$rr$）。操作方式就是这个$11$与其他的$11$交换，$00$与其他的$00$进行交换。为什么可以$\mathrm{？}？$因为对于和给定字符串$11$位置相同$00$位置相同只能是给定字符串本身，其他的字符串一定有不同的地方，这个不同的地方就会导致这两个位置的与给定字符串不同。至此，我们发现了一个使给定字符串特殊于所有其他字符串的地方。

我们找到了不同，然后可以对除了$ll$和$rr$以外所位置进行排序，排完序后因为$ll$位置为$11$，$rr$位置为$00$（因为给定字符串本身保证未排序，所以)，给定字符串一定是未成功排序的。同时，其他字符串这两个位置一定最少有一个是被成功排序的。我们取$l0l0$为给定字符串中0的个数（)，发现给定字符串的$0101$分界线一定再$l0l0$和$l0+1l0\; +\; 1$之间，而其他的未排序成功的字符串$0101$分界线一定向左向右有所偏移。因此，只要将$ll$和$[1,l0][1,l0]$内交换，r和$[l0+1,n][l0\; +\; 1,\; n]$交换即可。

解题方法

按照思路中来：

1. 将最左边$11$和所有$11$来一遍交换，最右边$00$和所有$00$交换。
2. 将除了$l\mathrm{，}rl，r$以外位置排序，因为操作的性质，导致所有$11$一定是向后移动，$00$向前。所以只要对每个位置和后面所有位置实施交换即可。
3. 将$ll$和$[1,l0][1,\; l0]$内交换，注意先和最远处交换，即先和$l0l0$,再$l0-\mathrm{1...}l0\; -\; 1...$，先$11$，再$\mathrm{2...}\mathrm{，}r2...，r$和$[l0+1,n][l0\; +\; 1,\; n]$交换同理。

复杂度

• 时间复杂度:

每次操作是 $n-2+(n-2)\ast (n-3)\mathrm{/}2+n-2n\; -\; 2\; +\; (n\; -\; 2)\; *\; (n\; -\; 3)\; /\; 2\; +\; n\; -\; 2$，最多为$119119$，大概是$O(n^2)O(n^2)$。

• 空间复杂度:

开了个数组存每次操作，是$O(n^2)O(n^2)$

Code

#include <bits/stdc++.h>

#pragma GCC optimize(2)
using namespace std;

#define endl "\n"
#define ll long long
#define pii pair<int, int>

void solve()
{
	int n;
	string s;
	cin >> n >> s;

  	//操作1
	vector<int> S0, S1;
	for(int i = 0; i < n; i++){
		if(s[i] == '0') S0.emplace_back(i + 1);
		else S1.emplace_back(i + 1);
	}

	int l = S1.front(), r = S0.back(), l0 = S0.size(), l1 = S1.size();
	vector<pii> res;
	for(int i = 1; i < l1; i++) res.emplace_back(make_pair(l, S1[i]));
	for(int i = 0; i < l0 - 1; i++) res.emplace_back(make_pair(S0[i], r));
  
  	//操作2
	for(int i = 1; i <= n; i++){
		if(i == l || i == r) continue;

		for(int j = i + 1; j <= n; j++){
			if(j == l || j == r) continue;
			
			res.emplace_back(make_pair(i, j));
		}
	}

  	//操作3
	for(int i = 1; i < l; i++) res.emplace_back(make_pair(i, l));
	for(int i = l0; i > l; i--) res.emplace_back(make_pair(l, i));
	for(int i = l0 + 1; i < r; i++) res.emplace_back(make_pair(i, r));
	for(int i = n; i > r; i--) res.emplace_back(make_pair(r, i));

  	//输出
	cout << res.size() << endl;
	for(auto [x, y] : res) cout << x << ' ' << y << endl;
}

int main()
{
	cout.tie(nullptr);
	cin.tie(nullptr);
	ios::sync_with_stdio(false);

	int _ = 1;
	cin >> _;

	while (_--)
		solve();

	return 0;
}

PS：如果有不足之处，欢迎大家批评指正