B – 01 Generation

题目描述：

最开始存在一个空序列，你有两种操作，问能不能凑出给定的01序列

• 反转序列的每个数，在开头添个0
• 在序列最后面添个0

思路：

直接模拟

可以先将01串根据0和1分成若干块

看当前串的开头

• 如果开头是0，则看最后一块

  • 如果最后一块是0，则先删掉这块0，再反转剩下的所有块
  • 如果最后一块不是0，就直接反转剩下的所有块

• 如果开头是1，则一定是NO，因为两种操作都不能在开头造个1

为了防止TLE，我们不能真的去反转所有的块，只需要用一个01变量来记录即可，用的时候就异或一下

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod7 1000000007
#define mod9 998244353
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define debug(a) cout << "Debuging...|" << #a << ": " << a << "\n";
typedef long long ll;
typedef pair <int,int> pii;

#define MAX 300000 + 50
int n, m, k, x;
int tr[MAX];
struct ran{
    int l, r, x;
};

void work(){
    cin >> n;
    for(int i = 1; i <= n; ++i)cin >> tr[i];
    vector<ran>v;
    for(int l = 1, r = 0; l <= n; l = r + 1, r = l){
        while (r + 1 <= n && tr[r + 1] == tr[l]) {
            ++r;
        }
        v.push_back({l, r, tr[l]});
    }
    int l = 0, r = (int)v.size() - 1;
    int num = 0;
    while (l != r) {
        int x = v[l].x ^ num;
        int len = v[l].r - v[l].l + 1;
        int y = v[r].x ^ num;
        if(x == 1){
            cout << "No\n";
            return;
        }
        num ^= 1;
        if(y == 0)--r;
        if(len == 1)++l;
        else ++v[l].l;
    }
    if(v[l].x ^ num)cout << "No\n";
    else cout << "Yes\n";
}


int main(){
    io;
    work();
    return 0;
}