题解：CF2256B Domino Tiles

· · 题解

首先分析题面，不难发现如果第 i 项与第 i+2 项相等，无论中间如何一定不合法。

手玩几组样例，注意到其实答案只有四种取值：0、1、2、4

注意：哪怕奇偶性相同处出现了非问号，因为这是合法序列之一，所以答案也为 1。

Code:

#include <bits/stdc++.h>
using namespace std;
int f[200100];bool vis[200100];
int n;
signed main(){
    int T;cin>>T;
    while(T--){
        cin>>n;
    memset(f,0,sizeof f);memset(vis,0,sizeof vis);
        string s;bool flag=0;cin>>s;s=' '+s;
        for(int i=1;i<=n;i++){
            if(s[i]!='?'&&!vis[i]){int c=s[i]-'0';c^=1;
                for(int j=i+2;j<=n;j+=2,c^=1){
                    if(s[j]-'0'!=c&&s[j]!='?'){
                        flag=1;
                        break;
                    }else vis[j]=1;
                }if(flag)break;
            }
        }
        if(flag){puts("0");continue;}
        int ans1=1,ans2=1;
        for(int i=1;i<=n;i+=2){if(s[i]!='?'){ans1=0;break;}}
        for(int i=2;i<=n;i+=2){if(s[i]!='?'){ans2=0;break;}}
        cout<<max(ans1*2+ans2*2,1)<<endl;
    }
    return 0-0;
}
/*
手写的样例加强版
5
7
1?????1
2
??
5
0?1??
5
0?0??
8
00110011

ans: 0 4 2 0 1
*/