题解：P7941 「Wdcfr-1」Magical Expression

· · 题解

题目传送门

题意

给一个合法的后缀表达式，包括 |、&、?，以及数字 0 和 1。现在问其有多少个子串满足把 ? 替换成 | 或 & 后这个表达式的值既能为 0 又能为 1。

思路

可以贪心。

可以发现结果最可能为 0 的情况是所有的 ? 全都变成 &，最可能为 1 的情况是全都变成 |，所以可以建表达式树然后 dfs 即可。

代码就不放了，求关~