IP20T3
目录
[toc]
[HTML_REMOVED]
题目
小 CC 热衷于学习数理逻辑。
有一天,他发现了一种特别的逻辑表达式。
在这种逻辑表达式中,所有操作数都是变量,且它们的取值只能为 00 或 11,运算从左往右进行。
如果表达式中有括号,则先计算括号内的子表达式的值。
特别的,这种表达式有且仅有以下几种运算:
- 与运算:a & b𝑎 & 𝑏。当且仅当 a𝑎 和 b𝑏 的值都为 11 时,该表达式的值为 11。其余情况该表达式的值为 00。
- 或运算:a | b𝑎 | 𝑏。当且仅当 a𝑎 和 b𝑏 的值都为 00 时,该表达式的值为 00。其余情况该表达式的值为 11。
- 取反运算:!a!𝑎。当且仅当 a𝑎 的值为 00 时,该表达式的值为 11。其余情况该表达式的值为 00。
小 CC 想知道,给定一个逻辑表达式和其中每一个操作数的初始取值后,再取反某一个操作数的值时,原表达式的值为多少。
为了化简对表达式的处理,我们有如下约定:表达式将采用后缀表达式的方式输入。
后缀表达式的定义如下:
- 如果 E𝐸 是一个操作数,则 E𝐸 的后缀表达式是它本身。
- 如果 E𝐸 是 E1 op E2𝐸1 𝑜𝑝 𝐸2 形式的表达式,其中 op𝑜𝑝 是任何二元操作符,且优先级不高于 E1、E2𝐸1、𝐸2 中括号外的操作符,则 E𝐸 的后缀式为 E′1 E′2 op𝐸1′ 𝐸2′ 𝑜𝑝,其中 E′1、E′2𝐸1′、𝐸2′ 分别为 E1、E2𝐸1、𝐸2 的后缀式。
- 如果 E𝐸 是 (E1)(𝐸1) 形式的表达式,则 E1𝐸1 的后缀式就是 E𝐸 的后缀式。
同时为了方便,输入中:
a) 与运算符(&&)、或运算符(||)、取反运算符(!!)的左右均有一个空格,但表达式末尾没有空格。
b) 操作数由小写字母 xx 与一个正整数拼接而成,正整数表示这个变量的下标。例如:x10x10,表示下标为 1010 的变量 x10𝑥10。数据保证每个变量在表达式中出现恰好一次。
题解
可以先转换成表达式树,然后再来求解
比如说样例:
nginx X1 X2 & X3 |
$\qquad$所有的叶子节点节点都是变量,其他的节点都是运算符。
$\qquad$首先模拟一下哎样例:$X1=1,X2=0,X3=1$,然后,样例第一次取反的变量的下标为1,于是样例变成了0 0 1,表达式的值为(0 & 0) | 1 = 0 | 1 = 1,所以打印
1
$\qquad$样例第二次取反的变量的下标为2,于是样例变成了1 1 1,表达式的值为(1 & 1) | 1 = 1 | 1 = 1,所以打印
1
$\qquad$样例第三次取反的变量的下标为3,于是样例变成了1 0 0,表达式的值为(1 & 0) | 0 = 0 | 0 = 0,所以打印
0
$\qquad$如果直接求一个值,就非常简单,我们可以利用一个[栈][嘎嘎],然后从根节点(样例是
bitor
)开始, 一层一层地递归,然后就求出了答案,但是,由于每一次更改,我们都需要重新求一遍表达式的值,所以,时间复杂度:$O(n\times m)$,明显超时了。$\qquad$想到优化也很容易,因为修改某一个点的值,只会影响到这个点往上走的一整条路径的值,不会影响到其他点的值,所以从这个点往根节点去遍历,也就是说,只用更新这一条路径就可以了。但是还有一个问题,如果是斜二叉树怎么办呢?最坏情况又退化到了$O(n\times m)$,所以还是不行。
$\qquad$更强的优化
不好想了,如果上面的节点是[HTML_REMOVED]bitand[HTML_REMOVED],那么:[HTML_REMOVED]有一个子节点是0的话,怎么修改另外一个节点的值,运算的结果都是0[HTML_REMOVED],$\qquad$如果上面的节点是[HTML_REMOVED]bitor[HTML_REMOVED]的话,那么:有一个子节点是1的话,怎么修改另外一个节点的值,运算的结果都是1
$\qquad$但是如果有一个节点是[HTML_REMOVED]not[HTML_REMOVED]的话,无法用这种方法优化(因为他只有一个子树),那该怎么办呢?如果不优化,还是难逃$O(n\times m)$,继续TLE,下场就是这个:laughing:。
$\qquad$这时候就需要用到一个定理了![HTML_REMOVED]!(a&b)=(!a)|(!b), !(a|b)=(!a)&(!b)[HTML_REMOVED]。
$\qquad$实际上还能再优化:第一步$dfs$一下求出整个表达式的值,然后后面的如果影响到了前面的值,那么就打一个标记,后面遍历点的时候,如果没有打过标记,就不dfs下去了。这样,整个时间复杂度是$O(n)$的,就不会超时了。
代码
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <cctype>
#include <ciso646>
#include <climits>
#include <algorithm>
using namespace std;
const int N = 1000010;
int n, m;
char str[N];
int w[N];
int h[N];
int e[N];
int ne[N];
int idx;
char c[N];
int stk[N];
int tt;
bool st[N];
void add(int a, int b)
{
e[idx] = b;
ne[idx] = h[a];
h[a] = idx ++;
}
int dfs1(int u)
{
if(u <= n) return w[u];
if(c[u] == '!') return w[u] = !dfs1(e[h[u]]);
else if(c[u] == '&')
{
w[u] = 1;
for(int i = h[u]; ~i; i = ne[i])
{
w[u] &= dfs1(e[i]);
}
return w[u];
}
else
{
w[u] = 0;
for(int i = h[u]; ~i; i = ne[i])
{
w[u] |= dfs1(e[i]);
}
return w[u];
}
}
void dfs2(int u)
{
st[u] = true;
if(u <= n) return ;
if(c[u] == '!') dfs2(e[h[u]]);
else
{
int a = e[h[u]];
int b = e[ne[h[u]]];
if(c[u] == '&')
{
if(w[a]) dfs2(b);
if(w[b]) dfs2(a);
}
else
{
if(! w[a]) dfs2(b);
if(! w[b]) dfs2(a);
}
}
}
int main()
{
cin.getline(str, N);
scanf("%d", &n);
for(int i = 1; i <= n; i ++)
{
scanf("%d", &w[i]);
}
memset(h, -1, sizeof(h));
m = n;
for(int i = 0; str[i]; i ++)
{
if(str[i] == 'x')
{
int k = 0;
i ++;
while(isdigit(str[i]))
{
k = k * 10 + str[i] - '0';
i ++;
}
stk[++ tt] = k;
}
else if(str[i] == '!')
{
c[++ m] = str[i];
add(m, stk[tt --]);
stk[++ tt] = m;
i ++;
}
else
{
c[++ m] = str[i];
add(m, stk[tt --]);
add(m, stk[tt --]);
stk[++ tt] = m;
i ++;
}
}
int root = stk[tt];
int res = dfs1(root);
dfs2(root);
int q;
scanf("%d", &q);
while(q --)
{
int x;
scanf("%d", &x);
if(st[x])
{
printf("%d\n", ! res);
}
else
{
printf("%d\n", res);
}
}
return 0;
}