题解 – [CF1890C/CF1889A]Qingshan Loves Strings 2

53次阅读
没有评论

题目链接 – 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>
正文完
 0
THEzsc
版权声明:本站原创文章,由 THEzsc 于2023-10-29发表,共计1753字。
转载说明:除特殊说明外本站文章皆由CC-4.0协议发布,转载请注明出处。
评论(没有评论)
Index