题解 – [CF1890C/CF1889A]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

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>