题目链接 – CF1890C题目链接 – CF1889A （洛谷）
题意描述
我们称长度为 k 的01串 a 是好的且仅当
$\forall i \in \left [ 1,k \right ], ai \ne a{k-i+1}比如，\texttt{10},\texttt{1010},\texttt{111000}是好的，而\texttt{11},\texttt{101},\texttt{001},\texttt{001100}不是好的。
现在给你一个01串 s，你可以执行不多于 300 次以下操作使得 s 变为好的（次数可以为 0）：
- 插入 \texttt{01}到 s的任意位置
请你判断是否有解，并在有解的情况下输出操作次数和每个操作的插入位置。
输出格式
对于每组数据，如果无法使 s 变好，输出一行一个 -1。
否则，输出 p ( 0 \le p \le 300 ) 表示操作总数。
接下来，输出 p 个整数 x_i ( 0 \le x_i \le n+2i-2 ) 表示操作位置。当 x_i = 0 时表示插入\texttt{01}到 s 开头，否则表示插入到 s 的第 x_i 项后面。
可以证明，在此问题的约束下，如果有答案存在，那么总有一个答案仅需要 300 次以下的操作数便可以完成。
样例 #1
样例输入 #1
6
2
01
3
000
4
1111
6
001110
10
0111001100
3
001
样例输出 #1
0
-1
-1
2
6 7
1
10
-1
前置条件
如果这个字符串是对称的，那么\texttt{0}和\texttt{1}的数量应是一样的。从这里可以直接判断答案是否存在。
做法一
赛场上想到的做法 我们将串中的所有\texttt{01}都去除，最后剩下若干\texttt{10}，且只可能有一种放法。 往这些\texttt{10}中插入\texttt{01}，只要保证插入的顺序是对称的，序列就是好的。
做法二
订正做法 思路或许是差不多的，但是明显这个方法实现更快更好。 建立头指针、尾指针，如果头尾不同，可以忽略这对，如果头尾相同且为\texttt{0}，在尾处加上\texttt{01}，如果头尾相同且为\texttt{1}，在头处加上\texttt{01}，头指针递增，尾指针递减。
分析
检测到的\texttt{0}和\texttt{1}有一个是\texttt{10}中的，手模一下样例，就会发现需要添加\texttt{01}了。 对于算法，实际上等价于将最后的\texttt{1}移到最前面，或将最前面的\texttt{0}移到最后面。
代码
#include<bits>
using namespace std;
typedef long long ll;
#define maxd(x, y) ((x) > (y) ? (x) : (y))
#define mind(x, y) ((x) < (y) ? (x) : (y))
int T;
const int MAXN = 2e5 + 10;
int n;
string s;
int main()
{
// freopen(C.in, r, stdin);
scanf(%d, &T);
while(T--) {
scanf(%d, &n);
cin >> s;
int flag = 1;
//判断-1
int cnt0 = 0, cnt1 = 0;
for(int i = 0; i < n; i++) {
if(s[i] == '0') cnt0++;
else cnt1++;
}
if(cnt0 != cnt1) {
printf(-1\n);
continue;
}
//计算正常情况
vector<int> ans;
int i = 0, j = n - 1;
while(i <= j) {
if(s[i] != s[j]) {
s.pop_back();
i++, j--;
} else if(s[i] == '0') {
s += 01;
ans.emplace_back(j + 1);
j += 2;
} else if(s[i] == '1') {
s.insert(s.begin() + i, '1');
s.insert(s.begin() + i, '0');
ans.emplace_back(i);
j += 2;
}
}
printf(%d\n, ans.size());
for(auto i : ans) printf(%d , i);
printf(\n);
}
return 0;
}</int></bits>
