题解 | #平衡的字符串#

D题题解

思路

k为奇数时显然无解，所以k只能为偶数 
k为偶数时，若满足题意则有：
对于 s[1]~s[k] num[0]=num[1]=k/2;
对于 s[2]~s[k+1] num[0]=num[1]=k/2
所以 s[1]=s[k+1]
 => s[i] 应该等于 s[i+k] , i+k<=n  (字符串下标从1开始)

所以我们让i%k，余数相同的为一组，共由k组（余数:1~k-1或0）.显然同一组内不可以同时出现字符0和字符1
若出现了这种情况则无解.

继续对一组内不同时出现字符0和字符1的情况 进行分析：
若一组内，有一个字符为0则该组的字符全部变为0，若1则全变1
把能确定的字符 全部确定后，我们检查一下s[1]~s[k] 是否满足题意、
注意：此时的s[1]~s[k] 仍然可能存在字符'?'
情况1：不存在字符'?'  => num[0]=num[1]=k/2 时有解
情况2：存在字符'?'  => num[0]<=k/2&&num[1]<=k/2 时有解
综合两种情况，即满足 num[0]<=k/2&&num[1]<=k/2 时有解

综上，Code如下

Code

#include  <iostream>
#include  <algorithm>
#include  <cstring>

using namespace std;

const int N=1000010;

int n,k;
int x0,x1,x2;
bool st[N][2];
char s[N];

int main(){
    cin>>n>>k>>s+1;
    if(k&1) cout<<"No"<<endl;
    else{

        int flag=0;
        for(int i=1;i<=n;i++){
           int t=i%k;
           if(s[i]=='0') st[t][0]=true;
           else if(s[i]=='1') st[t][1]=true;
           if(st[t][0]==true&&st[t][1]==true) flag=1;
        }
        if(flag) cout<<"No"<<endl;  
        else{

            for(int i=1;i<=n;i++){
                int t=i%k;
                if(st[t][0]==true) s[i]='0';
                if(st[t][1]==true) s[i]='1';
            }

            for(int i=1;i<=k;i++){
                if(s[i]=='0') x0++;
                else if(s[i]=='1') x1++;
                else x2++;
            }
            if(x0<=k/2&&x1<=k/2) cout<<"Yes"<<endl;
            else cout<<"No"<<endl;
        }

    }

    return 0;
}