Hack(?)

回复帖子

@Vocalise  2020-11-08 22:19 回复

应该有这种情况:!!!!!!!!!!!a

但是这份代码并没有考虑到,虽然是暴力,但是仍然没有 WA

如果剩下 TLE 的数据中有这种情况,望告知,然后我自裁

#include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>

const int N = 100001;
const int L = 1000001;

// -1 & // -2 | // -3 !
// 0 \n
inline int readx() {
    int x = 0; char ch = getchar();
    while(ch != 'x' && ch != '&' && ch != '|' && ch != '!' && ch != '\n') ch = getchar();
    if(ch == '\n') return 0;
    if(ch == '&') return -1;
    if(ch == '|') return -2;
    if(ch == '!') return -3;
    ch = getchar();
    while(ch >= '0' && ch <= '9') x = x * 10 + ch - 48, ch = getchar();
    return x;
}

inline int read() {
    int x = 0, f = 1; char ch = getchar();
    while(ch > '9' || ch < '0') { if(ch == '-') f = -1; ch = getchar(); }
    while(ch >= '0' && ch <= '9') x = x * 10 + ch - 48, ch = getchar();
    return x * f;
}

int n,map[N],st[N],tot;
int s[L],rev[L],lc[L],rc[L],fa[L],cnt;
int res[L];

void Dfs(int x) {
    if(!lc[x] && !rc[x]) return void(res[x] = s[x] ^ rev[x]);
    Dfs(lc[x]), Dfs(rc[x]);
    if(s[x] == -1) res[x] = res[lc[x]] & res[rc[x]];
    if(s[x] == -2) res[x] = res[lc[x]] | res[rc[x]];
    if(rev[x] == 1) res[x] ^= 1;
    // std::printf("%d ",res[x]);
}

void Change(int x) {
    res[map[x]] ^= 1;
    int p = fa[map[x]];
    while(p != st[tot]) {
        if(s[p] == -1) res[p] = res[lc[p]] & res[rc[p]];
        if(s[p] == -2) res[p] = res[lc[p]] | res[rc[p]];
        if(rev[p] == 1) res[p] ^= 1;
    p = fa[p];
    }
    if(s[p] == -1) res[p] = res[lc[p]] & res[rc[p]];
    if(s[p] == -2) res[p] = res[lc[p]] | res[rc[p]];
    if(rev[p] == 1) res[p] ^= 1;
    return;
}

int main() {
    freopen("expr.in","r",stdin);
    freopen("expr.out","w",stdout);
    int x;
    while(true) {
        x = readx();
    if(!x) break;
    if(x > 0) {
        st[++tot] = map[x] = ++cnt;
    } else if(x == -3) {
        rev[st[tot]] = true;
    } else {
        int b = st[tot--];
        int a = st[tot--];
        s[++cnt] = x;
        lc[cnt] = a, rc[cnt] = b;
        fa[a] = cnt, fa[b] = cnt;
        st[++tot] = cnt;
    }
    }
    n = read();
    for(int i = 1;i <= n;i++) s[map[i]] = read();
    Dfs(st[tot]);
    int q = read();
    while(q--) {
    int x = read();
    Change(x);
    std::printf("%d\n",res[st[tot]]);
    Change(x);
    }
    // std::puts("");
    return 0;
}
反馈
如果你认为某个帖子有问题,欢迎向洛谷反馈,以帮助更多的同学。



请具体说明理由,以增加反馈的可信度。