cf 1405 C Balanced Bitstring 思維-有解無憂

傳送門

題意：給一個01串，其中有些字符為 $^{'} ?^{'}'?'$ ， $^{'} ?^{'}'?'$ 可以當做 $00$ 或 $11$ ，給定一個 $k k$ ，問能否給 $^{'} ?^{'}'?'$ 賦上特定值后，其所有長度為k的字串0和1數量都相等，
我們用兩個指標來維護長度為k的區間，假設當前區間符合條件，當 $r + 1 r+1$ , $l + 1 l+1$ 的時候，可以發現必須要 $s [l] = s [r + 1] s[l]=s[r+1]$ 才可以滿足條件，那么就可以轉換成 $s [i] = s [j ? m o d ? k] s[i]=s[j\bmod k]$ ，當 $s [j ? m o d ? k] s[j\bmod k]$ 是 $^{'} ?^{'}'?'$ 的時候顯然需要賦成 $s [i] s[i]$ ，當不是的時候只需要看看是否相等，答案只需要檢查 $[0, k ? 1] [0,k-1]$ 是否符合即可，

#pragma GCC optimize(2)
#include<cstdio>
#include<iostream>
#include<string>
#include<cstring>
#include<map>
#include<cmath>
#include<cctype>
#include<vector>
#include<set>
#include<queue>
#include<algorithm>
#include<sstream>
#include<ctime>
#include<cstdlib>
#define X first
#define Y second
#define L (u<<1)
#define R (u<<1|1)
#define pb push_back
#define mk make_pair
#define Mid (tr[u].l+tr[u].r>>1)
#define Len(u) (tr[u].r-tr[u].l+1)
#define random(a,b) ((a)+rand()%((b)-(a)+1))
using namespace std;

void rd_cre() { freopen("d://dp//data.txt","w",stdout); srand(time(NULL)); }
void rd_ac() { freopen("d://dp//data.txt","r",stdin); freopen("d://dp//AC.txt","w",stdout); }
void rd_wa() { freopen("d://dp//data.txt","r",stdin); freopen("d://dp//WA.txt","w",stdout); }

typedef long long LL;
typedef pair<int,int> PII;

const int N=300010,mod=1e9+7,INF=0x3f3f3f3f;
const double eps=1e-6;

int n,k;
char s[N];

bool check(int a,int b,int c)
{
    int d=abs(a-b);
    if(c<d) return true;
    c-=d; 
    if(c&1) return true;
    return false;
}

int main()
{
//	ios::sync_with_stdio(false);
//	cin.tie(0);

    int _; scanf("%d",&_);
    while(_--)
    {
        scanf("%d%d%s",&n,&k,s);
        int a,b,c; a=b=c=0;
        int len=strlen(s),st=0;
        bool f=true;
        for(int i=0;i<n;i++)
        {
            if(s[i%k]!=s[i])
            {
                if(s[i]!='?'&&s[i%k]=='?') s[i%k]=s[i];
                else if(s[i]=='?') continue;
                else f=false;
            }
        }
        for(int i=0;i<k;i++)
        {
            if(s[i]=='1') a++;
            else if(s[i]=='0') b++;
            else if(s[i]=='?') c++;
        }
        //  cout<<a<<' '<<b<<' '<<c<<endl;
        if(check(a,b,c)) f=false;
        if(!f) puts("NO");
        else puts("YES");
    }




	return 0;
}
/*

*/

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/1297.html

標籤：其他

上一篇：Android 繪制同心圓 (2個圓疊加在一起)

下一篇：Android 天氣APP（二十八）地圖搜索定位