CF2092B Lady Bug

題目描述

當 Dasha Purova 剛越過法國邊境時，反派 Markaron 綁架了她并將她關押在其城堡下的監獄中。幸運的是，神奇的 Lady Bug 得知 Dasha 的消息后立即趕往 Markaron 的城堡營救她。然而，她需要破解一個復雜密碼才能進入。

該密碼由兩個長度為 \(n\) 的比特字符串 \(a\) 和 \(b\) 組成。Lady Bug 在一次操作中可以選擇任意索引 \(2 \leq i \leq n\) 并執行以下兩種操作之一：

1. 交換 \((a_i\), \(b_{i-1})\)。
2. 交換 \((b_i\), \(a_{i-1})\)。

Lady Bug 可以進行任意次數的操作。若她能使第一個字符串 \(a\) 僅由 \(0\) 組成，則視為密碼破解成功。請幫助她判斷是否能成功營救 Dasha。

Solution

將這兩個操作翻譯一下就是可以走蛇形路徑上的數隨意交換。即 \(a\) 第一個和 \(b\) 第二個和 \(a\) 第三個等等可以隨便交換。\(b\) 第一個和 \(a\) 第二個和 \(b\) 第三個等等可以隨便交換。容易知道我們可以將其中一條路徑上的所有 \(0\) 交換到 \(a\) 數組上面。那么我們只需要統計每一條路徑上 \(0\) 的個數能否覆蓋所需地方即可。

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+10;
int t,n;
string a,b;
int main(){
    cin>>t;
    while(t--){
        cin>>n>>a>>b;
        a=" "+a,b=" "+b;
        int cnt=0,k=0;
        for(int i=1;i<=n;++i){
            if(i%2==0){
                cnt+=(b[i]=='0');
            }else{
                cnt+=(a[i]=='0');
                ++k;
            }
        }
        if(cnt<k){
            puts("NO");
        }else{
            cnt=0,k=0;
            for(int i=1;i<=n;++i){
                if(i%2==0){
                    cnt+=(a[i]=='0');
                    ++k;
                }else{
                    cnt+=(b[i]=='0');
                }
            }
            if(cnt<k){
                puts("NO");
            }else{
                puts("YES");
            }
        }
    }
    return 0;
}