题解：P7073 [CSP-J2020] 表达式

xmy201315 · 2024-12-28 16:02:06 · 题解

这道题是一道非常难的关于树的题目。

前置芝士

思路

我们要先字符串处理（也就是输入，预处理等事情。较简单，不在此描述了）。接着，我们在建一颗表达式树。我们假设在每次询问时，都修改表达式树，然后算出结果。这时我们会发现 TLE 了，因为每次遍历都是 \mathcal O(n q)，所以我们用到了树形 DP。大多数题目树形 DP 都是从下往上做，但是这道题得从上往下做。然后我们假设 u 这个节点发生了变化，我们要看它的父亲节点是否有变化。如果没有，最后结果不变；如果父亲节点的值变了，就看这个父亲节点是否会导致父亲节点的父亲的值改变，然后一直做这个操作。最后我们把答案都预处理出来就好啦！

还有很多细节，看代码吧！

AC code:

#include <bits/stdc++.h>
using namespace std;
const int N=1010000;
struct node{
    int l,r;
    int type;
    int val;
    bool dp;
}a[N];
stack <int> s;
int n,m,q;
int p[N];
void dfs1(int u){
    if(a[u].type>0)return;
    if(a[u].type==-1){
        dfs1(a[u].l);
        a[u].val= !a[a[u].l].val;
    }else{
        dfs1(a[u].l);
        dfs1(a[u].r);
        if(a[u].type==-2)
            a[u].val=a[a[u].l].val & a[a[u].r].val;
        else
            a[u].val=a[a[u].l].val | a[a[u].r].val;
    }
}
void dfs2(int u){
    if(a[u].type>0)return;
    int L=a[u].l,R=a[u].r;
    if(a[u].type==-1){
        a[L].dp=a[u].dp;
        dfs2(L);
    }else{
        if(a[u].type==-2){
            if(a[R].val==0)a[L].dp=false;
            else a[L].dp=a[u].dp;
            if(a[L].val==0)a[R].dp=false;
            else a[R].dp=a[u].dp;
        }else{
            if(a[R].val==1)a[L].dp=false;
            else a[L].dp=a[u].dp;
            if(a[L].val==1)a[R].dp=false;
            else a[R].dp=a[u].dp;
        }
        dfs2(L);
        dfs2(R);
    }
}
int main(){
    while(true){
        char ch; 
        scanf("%c",&ch);
        if(ch=='x'){
            ++n;
            int id=0;
            while(true){
                scanf("%c",&ch);
                if(ch>='0'&&ch<='9')
                    id=id*10+ch-'0';
                else break;
            }
            a[n].type=id;
            p[id]=n;
            s.push(n);
        }else{
            assert((ch=='|')||(ch=='&')||(ch=='!'));
            if(ch=='|'||ch=='&'){
                ++n;
                int r=s.top();s.pop();
                int l=s.top();s.pop();
                a[n].l=l;a[n].r=r;
                if(ch=='|')a[n].type=-3;
                else a[n].type=-2;
                s.push(n);
            }
            else{
                ++n;
                int l=s.top();s.pop();
                a[n].l=l;
                a[n].type=-1;
                s.push(n);
            }
            scanf("%c",&ch);
        }
        if(ch!=' ')break;
    }
    int root=s.top();
    scanf("%d",&m);
    for(int i=1;i<=m;i++){
        int x;
        scanf("%d",&x);
        a[p[i]].val=x;
    }
    dfs1(root);
    a[root].dp=true;
    dfs2(root);
    scanf("%d",&q);
    for(int i=0;i<q;i++){
        int x;
        scanf("%d",&x);
        if(a[p[x]].dp)printf("%d\n",a[root].val^1);
        else printf("%d\n",a[root].val);
    }
}