题解 - Qingshan Loves Strings 2
算法竞赛题解 | 难度：普及
题目链接 - 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
1
2
3
4
5
6
7
8
9
10
11
12
13
6
2
01
3
000
4
1111
6
001110
10
0111001100
3
001
样例输出 #1
1
2
3
4
5
6
7
8
9
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}$移到最后面。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#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>