CF1988B 题解

shiziyu111 · 2024-07-17 15:45:06 · 题解

题目大意

给定一个长度为 n 的字符串 a，每次可以选择一个 l 和 r，使得 a_l 到 a_r 的区间合并，合并操作如下：

记 c_0 为该区间中 0 的长度，c_1 为该区间中 1 的长度。

• 如果 c_0\ge c_1，则将区间合并成 0。
• 如果 c_0<c_1，则将区间合并成 1。

问能否使 a=[1]。

分析

如果要使 a=[1]，那么我们就要使 0 尽可能的少，所以先合并所有连在一起的 0。

我们再分析假如在合并后 c_0\ge c_1，那么再多的合并都无力回天，故输出 No。假如合并后 c_0<c_1，那么就简单了，把 a 整体合并就行了，故输出 Yes。

在知道这些后，就到了我们喜爱的：

我爱打代码

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int T;
    cin>>T;
    for(int i=1;i<=T;i++)
    {
        int n,c0=0,c1=0;;
        char a[200005];
        cin>>n;
        cin>>a;
        for(int i=0;i<n;i++)
        {
            if(a[i]=='1')
            {
                c1++;
            }
            else
            {
                if(a[i-1]=='1'||i==0)
                {
                    c0++;
                }
            }
        } 
        if(c0>=c1)
        {
            cout<<"No"<<endl;
        }
        else
        {
            cout<<"Yes"<<endl;
        }
    }
    return 0;
}

都看到这里了，还不点个赞。