P7941 「Wdcfr-1」Magical Expression 的题解

· · 题解

题目大意

传送门

给你一段合法后缀表达式，包括 |、& 和 ?，以及两个数字 0,1，现在请问有多少个 子串，满足把 ? 替换成 | 或 & 后结果既能是 0，也能是 1。

大体思路

显然是编译原理题了。（建议升绿）

编译原理题的通用思维：

其中这题已经给了后缀，所以第一步可以省略。

又可以发现其中隐藏的贪心：凑成 0 的时候用 & 最优，凑成 1 的时候用 | 最优。这个应该比较明显。

那不就好了吗？

代码如下：

#include <bits/stdc++.h>
using namespace std;
int T;
struct node { int l, r; char x; } a[2000007];
stack<int> st;
int ok[2][2000007];
inline void dfs(int t, bool lxl) { //用大(qing)佬(wa) lxl 的名字作为变量名 
    //lxl 为 1 表示把 ? 替换成 |，为 0 表示替换成 & 
    if(a[t].l == -1) { ok[lxl][t] = a[t].x - '0'; return; }
    dfs(a[t].l, lxl); dfs(a[t].r, lxl); //首先得遍历到底 
    char ch = a[t].x;
    //注意！！外面一定要套一个 ok 数组，a[t].l 不是答案！ 
    int left = ok[lxl][a[t].l];
    int right = ok[lxl][a[t].r];
    if(ch == '&') ok[lxl][t] = left & right;
    if(ch == '|') ok[lxl][t] = left | right;
    if(ch == '?') {
        if(lxl == 0) ok[lxl][t] = left & right;
        else ok[lxl][t] = left | right;
    }
}
int main() {
    speed: std::ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> T;
    while(T--) { //对于每组询问 
        int n; cin >> n;
        string s; cin >> s;
        while(!st.empty()) st.pop(); //多测不清空，爆零两行泪 
        for(int i = 0; i < n; i++) {
            char ch = s[i];
            if(isdigit(ch)) { a[i] = ((node){-1, -1, ch}); st.push(i); continue; }
            a[i].l = st.top(); st.pop(); //否则就是 ? 或 | 或 & 
            a[i].r = st.top(); st.pop(); //弹栈记录两个节点 
            a[i].x = ch; st.push(i);
        } int ans = 0;
        dfs(n - 1, 0); dfs(n - 1, 1);
        //ok 是计算结果 
        for(int i = 0; i < n; i++) if(ok[0][i] != ok[1][i]) ans++;
        cout << ans << "\n";
    }
    return 0;
}