A38 正经题解

题意分析
给定一个后缀逻辑表达式，其中有若干变量，给定变量初始值，问哪些变量单独改变会对整个表达式的结果造成影响
具体思路
建图部分：
遍历字符串，通过空格将字符串分割成若干元素，将元素编号后一一塞入栈中，若是变量则作为叶子节点，若当前元素为单目运算符（!）就提出前一元素作为该节点的左节点，若为双目运算符（&和|）就提出前二元素分别作为该节点的左节点与右节点。同时为了后续操作，我们也记录下每个叶子节点的编号所对应的变量，即v[i]表示节点i对应的变量，若不是叶子节点则默认值为0。
第一遍dfs：
为了后续计算哪些变量取反会影响整个表达式，我们需要首先得知树中以每个节点为根的子树所表示的表达式的值，我们定义这些表达式为"子表达式"，并定义以某一子树的根的父节点为根的树为这一子树表示表达式的"父表达式"，dist[i]表示以i为根的子树所表示表达式的值。我们将问题拆分为类似动态规划的子问题，x_value[i]表示变量i的初始值，若x是叶子节点，则dist[x]=x_value[v[x]]的值，否则根据其叶子节点的值逐步往上推。根据这个思路，我们就能在dfs递归的"归"过程中算出所有"子表达式"的值。
第二遍dfs：
根据牢马亡教的小学三年级知识，我们知道形如1&x或0|x的表达式中，x的值会影响表达式的结果。因此，在第二遍dfs中，我们无视单目运算符（!），因为我们的目标是找到所有改变会影响总值的叶子节点，并且已经得知每个"子表达式"的值，并不需要用到它。当遇到双目运算符时，依据dist中存储的左右子树的值，我们可以判断出当前表达式是否是形如1&x或0|x的表达式，并以此判断出左右子树的值是否影响当前表达式的结果。对影响结果的那一棵子树进行搜索，当你的dfs发现自己在叶子节点上时，就说明这个叶子节点的改变会影响整个表达式的值。将结果储存在is_turn数组中。
收尾：
对于每一组询问，只需要依照is_turn数组输出原表达式或取反的结果即可。
AC代码

#include <bits/stdc++.h>
using namespace std;
const int INF = 1e6+5;
//son数组表示每个节点的子节点，son[i][0]为i的左子节点，son[i][1]为i的右子节点
int son[INF][2], v[INF];  //v[n]表示节点n对应的变量
bool x_value[INF], dist[INF], is_turn[INF];
//x_value[i]表示变量i对应的初始值，dist[i]表示以i为根的表达式的值，is_turn[i]表示i变量的改变是否会影响整个结果
void dfs1(int u){  //将整个"父表达式"拆成"子表达式"，并判断它们的值，递归将值传回到父亲节点
    if(v[u]>0)
        dist[u] = x_value[v[u]];
    if(v[u]==-1){
        dfs1(son[u][0]);
        dist[u] = !dist[son[u][0]];
    }
    if(v[u]==-2){
        dfs1(son[u][0]);
        dfs1(son[u][1]);
        dist[u] = dist[son[u][0]] & dist[son[u][1]];
    }
    if(v[u]==-3){
        dfs1(son[u][0]);
        dfs1(son[u][1]);
        dist[u] = dist[son[u][0]] | dist[son[u][1]];
    }
    return;
}

void dfs2(int u){ //判断哪些叶子节点的值会影响整个表达式的值
    if(v[u]>0)
        is_turn[v[u]] = true;
    if(v[u]==-1)
        dfs2(son[u][0]);
    if(v[u]==-2){  //x&1和1&x
        if(dist[son[u][1]]==1)
            dfs2(son[u][0]);
        if(dist[son[u][0]]==1)
            dfs2(son[u][1]);
    }
    if(v[u]==-3){  //x|0和0|x
        if(dist[son[u][1]]==0)
            dfs2(son[u][0]);
        if(dist[son[u][0]]==0)
            dfs2(son[u][1]);
    }
    return;
}

int main(){
    int n, q;
    string s;
    getline(cin, s);
    cin >> n;
    for(int i=1;i<=n;++i){
        cin >> x_value[i];
    }
    cin >> q;
    stack<int> stk;  //用栈建树
    int idx = 0;  //idx表示节点编号
    for(int i=0;i<s.size();++i){
        idx++;
        if(s[i]=='x'){
            int num = 0;
            while(s[i+1]!=' '){
                i++;
                num = num*10+s[i]-'0';
            }
            stk.push(idx);
            v[idx] = num;
        }
        if(s[i]=='!'){
            auto x = stk.top();
            stk.pop();
            son[idx][0] = x;
            stk.push(idx);
            v[idx] = -1;
        }
        if(s[i]=='&'){
            auto x = stk.top();
            stk.pop();
            auto y = stk.top();
            stk.pop();
            son[idx][0] = x, son[idx][1] = y;
            stk.push(idx);
            v[idx] = -2;
        }
        if(s[i]=='|'){
            auto x = stk.top();
            stk.pop();
            auto y = stk.top();
            stk.pop();
            son[idx][0] = x, son[idx][1] = y;
            stk.push(idx);
            v[idx] = -3;
        }
    }
    dfs1(idx);
    dfs2(idx);
    while(q--){
        int c;
        cin >> c;
        if(is_turn[c])
            cout << !dist[idx] << endl;
        else
            cout << dist[idx] << endl;
    }
}

时间复杂度
线性，$O(\lvert s\rvert + N + q)$，其中$\vert s\vert$表示字符串$s$的长度，$N$表示树节点数(变量数$n$+逻辑符号数量)，可以处理较大范围数据。