CF1988B#

题目分析#

根据题意，每次操作可以将 $[l,r]$ 区间的数变为 $1$ 个多数，要求能否转化为 $a=[1]$ 。不难想出，我们应该将序列中 $0$ 的个数降为最低，所以可以将每一段连续的 $0$ 都进行操作使得最后的时候序列中所包含的 $0$ 最少，然后只需要遍历序列统计 $c_0$ 和 $c_1$ 的个数，比较两数，如果 $c_1>c_0$ 则为Yes。

Code#

1
//#pragma GCC optimize(1, 2, 3, "Ofast", "inline")
2
#include <bits/stdc++.h>
3
using namespace std;
4
#define ll long long
5
#define int ll
6
#define ONLINE_JUDGE
7
#define MULTI_CASES
8
const int MaxN = 2e5+100;
9
const int INF = 1e9;
10
int T=1, N, M;
11
int a[MaxN];
12
inline void Solve()
13
{
14
  int N;
15
  cin>>N;
16
  string s;
17
  cin>>s;
18
  int xx[MaxN],n=0;
19
//  memset(xx,0,sizeof xx);
20
  bool f=0;
21
  for(int i=0;i<N;i++){
22
//    cout<<f<<endl;
23
//    cout<<s[i];
24
    if(s[i]=='0'&&!f){
25
      xx[n++]=0;//尽可能减少0的数量
26
      f=1;
27
    }
28
    else{
29
      if(s[i]!='1'){
30
        continue;
31
      }
32
      f=0;
33
      xx[n++]=1;
34
    }
35
//    cout<<xx[n-1];
36
  }
37
  int sum0=0,sum1=0;
38
  for(int i=0;i<n;i++){
39
    if(xx[i]==1){
40
      sum1++;
41
    }
42
    else{
43
      sum0++;
44
    }
45
  }
46
//  cout<<sum0<<" "<<sum1<<endl;
47
  if(sum0>=sum1){
48
    puts("No");
49
  }
50
  else{
51
    puts("Yes");
52
  }
53
}
54
signed main()
55
{
56
#ifndef ONLINE_JUDGE
57
  freopen(".in", "r", stdin);
58
  freopen(".out", "w", stdout);
59
#endif
60
  ios::sync_with_stdio(0);
61
  cin.tie(0),cout.tie(0);
62

63
#ifdef MULTI_CASES
64
  cin >> T;
65
  while (T--)
66
#endif
67
    Solve();
68
  //fclose(stdin);
69
  //fclose(stdout);
70
  return 0;
71
}