【题解】洛谷#P7073 [CSP-J2020] 表达式

Description

给定一个逻辑表达式和其中每一个操作数的初始取值后，再取反某一个操作数的值时，求出原表达式的值。表达式将采用后缀表达式的方式输入。

Solution

根据题目可得，当取反一个操作数的值时，整个表达式大体只有变与不变两种情况，而往下分解，整个表达式可以被分成若干子表达式，然后子表达式继续分解······

这样，我们就可以把表达式直接当作一棵树，而操作数\(x\)取反是否会改变表达数的值，或者说它是否起到决定性的作用取决于它所在的子表达式，而子表达式又有可能影响到更上一级的表达式······最后是到整个表达式，

我们发现，如此将一个操作数逐层递增，最后爬到根节点的操作可以用类似并查集的方法实现，如果这层递增后发现起到决定性的作用时，继续递增，当最后递增到整个表达式的范畴时，则输出原表达式结果的取反结果，否则直接输出结果

Step

1. 读入表达式和操作数初值

2. 计算表达式，同时判断每个操作数是否起到决定性的作用，分或运算\(|\)和与运算\(\&\)两种情况：

• 当是或运算且另一个操作数为0时，这个操作数就将起着决定性的作用

• 当是与运算且另一个操作数为1时，这个操作数就将起着决定性的作用

3. 输入查询，判断是否影响到整个表达式，如是则输出结果的取反结果，否则直接输出结果

Code

#include <bits/stdc++.h>
using namespace std;
const int maxE=1e6+5,maxN=1e5+5;
int n,e[maxE],l,wx[maxN],a[maxN],fa[maxE];
struct Node{
    int eid,val;
};
stack<Node>st;
int main(){
    while(1)
    {
        string s;
        cin>>s;
        char c=s[0];
        if(c>='0'&&c<='9')
        {
            n=stoi(s);
            break;
        }
        if(c=='x')
        {
            int xid=stoi(s.substr(1));
            e[++l]=xid;
            wx[xid]=l;
        }
        if(c=='!') e[++l]=-1;
        if(c=='&') e[++l]=-2;
        if(c=='|') e[++l]=-3;
    }
    for(int i=1;i<=n;i++)
        cin>>a[i];
    for(int i=1;i<=l;i++)
    {
        if(e[i]>0)
        {
            st.push({i,a[e[i]]});
        }
        if(e[i]==-1)
        {
            Node x=st.top();st.pop();
            st.push({i,!x.val});
            fa[x.eid]=i;
        }
        if(e[i]==-2)
        {
            Node y=st.top();st.pop();
            Node x=st.top();st.pop();
            st.push({i,x.val&y.val});
            if(x.val==1)fa[y.eid]=i;
            if(y.val==1)fa[x.eid]=i;
        }
        if(e[i]==-3)
        {
            Node y=st.top();st.pop();
            Node x=st.top();st.pop();
            st.push({i,x.val|y.val});
            if(x.val==0)fa[y.eid]=i;
            if(y.val==0)fa[x.eid]=i;
        }
    }
    int res=st.top().val;
    int q;
    cin>>q;
    for(int i=1;i<=q;i++)
    {
        int xid;
        cin>>xid;
        int j=wx[xid];
        while(fa[j])
            j=fa[j];
        if(j==l)
            cout<<!res<<endl;
        else
            cout<<res<<endl;
    }
    return 0;
}

感谢@fyz的代码

好吧，我承认思路也是他的（bushi