题解：AT_arc138_b [ARC138B] 01 Generation

Andy2011 · 2024-12-21 16:49:20 · 题解

AT_arc138_b [ARC138B] 01 Generation题解

思路

构造出两种 A B 的反向操作：

• A' 操作：将串中的每一位翻转，即 0 变成 1，1 变成 0，最后再在串的最前面删除一个 0。
• B' 操作：在串的最后面删除一个 0。

于是想到将原串逐步变为空串。

代码

双指针模拟头尾

#include <bits/stdc++.h>
using namespace std;
int a[200010];
int main(){
    //读入 
    int n;
    scanf("%d",&n);
    for (int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    int l=1,r=n;//l左指针 r右指针 
    int k=0;//k表示当前最后一位应为的状态
    while (l<=r){//左指针应当小等于右指针 
        //右指针a[r]为零 
        if (a[r]==k){
            //进行B'操作 
            r--;
        }
        //左指针a[l]为一 
        else if (a[l]!=k){
            //左右都为一，无法进行操作 
            printf("No\n");
            return 0;
        }
        //左指针a[l]为零 
        else if (a[l]==k){
            //进行A'操作 
            k^=1;//全部进行翻转，相当于将最后一位应为的状态翻转 
            l++;
        }
    }
    printf("Yes\n");
    return 0;
}