CF1890B Qingshan Loves Strings题解

题意简述#

给定两个01字符串 $s,t$ ，你需要在 $s$ 之中插入任意个字符串 $t$ ，使得新的字符串 $s$ 中相邻的两个数都不同。

题意分析#

由于字符串只有 $0$ 和 $1$ ，所以最终的字符串一定是 01010101 或 10101010 的形式。而插入的字符串是固定的，所以首先考虑字符串 $s$ ，如果一个字符串中同时出现 11 和 00 时，字符串一定不能“变好”。

然后我们考虑字符串 $t$ 的形式，如果字符串 $t$ 本身就不符合 $t_i \ne t_{i+1}$ 的话，也是不可以的。

如果都字符串都符合的情况下，不难发现，我们只需要记录字符串 $s$ 中包括 00 还是 11，然后与字符串 $t$ 的两边判断，如果不同，就可以构成。具体判断见代码。

Code#

1
#include <bits/stdc++.h>
2
using namespace std;
3
#define ll long long
4
#define int ll
5
const int MaxN = 1e6 + 100;
6
const int INF = 1e9;
7
int T=1, N, M;
8
template<class T>
9
inline void qread(T &sum)
10
{
11
  sum=0;int boo=1;
12
  char x=getchar();
13
  while(x<'0'||x>'9'){if(x=='-')boo=-1;x=getchar();}
14
  while(x>='0'&&x<='9'){sum=(sum<<1)+(sum<<3)+x-'0';x=getchar();}
15
  sum*=boo;
16
}
17
template<class T>
18
void qput(T x)
19
{
20
  if(x<0){
21
    x=-x;
22
    putchar('-');}
23
  if(x>9)
24
    qput(x/10);
25
  putchar(x%10+48);
26
}
27
inline void Solve()
28
{
29
  int n,m;
30
  cin>>n>>m;
31

32
  string s,t;
33
  cin>>s>>t;
34

35
  bool flag=0;
36
  int cnt=-1;
37
  for(int i=0;i<n;i++){
38
    if(s[i]==s[i+1]){
39
      if(s[i]-'0'!=cnt&&cnt!=-1){
40
        puts("No");//字符串s
41
        //cout<<cnt;
42
        return;
43
      }
44
      cnt=s[i]-'0';
45
      flag=1;
46

47
    }
48
  }
49

50
  if(flag==0){
51
    puts("Yes");
52
    return;
53
  }
54
  for(int i=0;i<t.size();i++){
55
    if(t[i]==t[i+1]){
56
      puts("No");//字符串t
57
      return;
58
    }
59
  }
60
  if(t[0]-'0'!=cnt&&t[m-1]-'0'!=cnt){
61
    puts("Yes");//字符串s和t判断
62
    //cout<<cnt
63
  }
64
  else{
65
    puts("No");
66
  }
67
}
68
signed main()
69
{
70
  //freopen(".in", "r", stdin);
71
  //freopen(".out", "w", stdout);
72
  ios::sync_with_stdio(0);
73
  //cin.tie(0);
74
  cin >> T;
75
  while (T--)
76
    Solve();
77
  //fclose(stdin);
78
  //fclose(stdout);
79
  return 0;
80
}