自动搬运

查看原文

来自洛谷，原作者为

	卷王 可惜没如果.

搬运于2025-08-24 22:34:30，当前版本为作者最后更新于2023-07-13 13:54:17，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目大意

传送门

给你一段合法后缀表达式，包括 |、& 和 ?，以及两个数字 $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;
}