100分,但是后面有3个点TLE了求助
查看原帖
100分,但是后面有3个点TLE了求助
697945
Tian36309楼主2023/10/2 20:02
#include<bits/stdc++.h>
using namespace std;
string s;
int y_d,h_d,cnt;
int root;
int zhan[1000005],c;
struct tree{
    char p; // '0' '1' '&' '|'
    int l;
    int r;
}a[1000005];
int match[1000005];
int build(int l,int r){
    int x;
    if(r == l and (s[l] == '0' or s[l] == '1')){
        x = ++cnt;
        a[x].p = s[l];
        a[x].l = -1;
        a[x].r = -1;
        return x;
    }
    for(int i=r;i>=l;i--){
        if(s[i] == ')')i = match[i];
        if(s[i] == '|'){
            x = ++cnt;
            a[x].p = '|';
            a[x].l = build(l,i-1);
            a[x].r = build(i+1,r);
            return x;
        }
    }
    for(int i=r;i>=l;i--){
        if(s[i] == ')')i = match[i];
        if(s[i] == '&'){
            x = ++cnt;
            a[x].p = '&';
            a[x].l = build(l,i-1);
            a[x].r = build(i+1,r);
            return x;
        }
    }
    return build(l+1,r-1);
}
bool findans(int x){
    if(a[x].p == '0' or a[x].p == '1') return a[x].p - '0';
    bool left = findans(a[x].l);
    if(a[x].p == '&' and !left){
        y_d++;
        return false;
    }
    if(a[x].p == '|' and left){
        h_d++;
        return true;
    }
    else return findans(a[x].r);
}
int main(){
    cin >> s;
    for(int i=0;i<=s.length();i++){
        if(s[i] == '(')zhan[++c] = i;
        if(s[i] == ')'){
            match[i] = zhan[c];
            c--;
        }
    }
    root = build(0,s.length()-1);
    int ans = findans(root) ? 1:0;
    printf("%d\n",ans);
    printf("%d %d",y_d,h_d);
    return 0;
}
2023/10/2 20:02
加载中...