打破零回复
by I_AK_IoI_2028 @ 2021-09-29 14:50:30
```c
#include<bits/stdc++.h>
using namespace std;
struct st //一个运算对象,包含了值(v)和位置(id)
{
st() {}
st(int id, int v) : id(id), v(v) {}
int id, v;
} tx, ty, s[1000001]; //s是栈
char ss[1111]; //读入的字符串
int n, q, res, x, y, a[1000001], e[2000001], l = 0, xe[1000001], f[2000001], stop = 0; //stop为栈顶
/*
e表示每个运算:
若e[i]>0则e[i]就是题目中的x[e[i]]
若e[i]=-1则表示&运算
若e[i]=-2则表示|运算
若e[i]=-3则表示!运算
l是e的长度
xe[i]表示x[i]在e中的位置
f意义同上
*/
/*
char s[] = "123 4.56 abc";
int a;
double b;
char c[10];
sscanf(s, "%d%lf%s", &a, &b, c);
//a=123, b=4.56, c="abc"
*/
inline void push(st x) //入栈
{
s[++stop] = x;
}
inline void pop() //出栈
{
stop--;
}
inline st top() //栈顶
{
return s[stop];
}
int main()
{
freopen("expr.in", "r", stdin);
freopen("expr.ans", "w", stdout);
while(1)
{
scanf("%s", ss);
if ( ss[0] >= '0' && ss[0] <= '9' ) break;
l++;
if ( ss[0] == 'x' )
{
sscanf(ss + 1, "%d", e + l); //见干货
xe[e[l]] = l;
}
if ( ss[0] == '&' ) e[l] = -1;
if ( ss[0] == '|' ) e[l] = -2;
if ( ss[0] == '!' ) e[l] = -3;
}
sscanf(ss, "%d", &n); //见干货
for ( int i = 1 ; i <= n ; i++ ) scanf("%d", a + i);
for ( int i = 1 ; i <= l ; i++ ) //求值并且给f赋值
{
if ( e[i] > 0 ) push(st(i, a[e[i]]));
if ( e[i] == -3 ) //!
{
tx = top();
pop();
push(st(i, !tx.v));
f[tx.id] = i;
}
if ( e[i] == -2 ) //|
{
tx = top();
pop();
ty = top();
pop();
push(st(i, tx.v || ty.v));
if ( !ty.v ) f[tx.id] = i;
if ( !tx.v ) f[ty.id] = i;
}
if ( e[i] == -1 ) //&
{
tx = top();
pop();
ty = top();
pop();
push(st(i, tx.v && ty.v));
if ( ty.v ) f[tx.id] = i;
if ( tx.v ) f[ty.id] = i;
}
}
res = top().v; //取得运算结果
scanf("%d", &q);
for ( int i = 1 ; i <= q ; i++ )
{
scanf("%d", &x);
for ( y = xe[x] ; f[y] ; y = f[y] ); //一路找到它最终会改变哪个值
//显然最后一个运算是l,那么当它会改变l时将原答案取反
printf("%d\n", y == l ? !res : res);
}
return 0;
}
```
看看我这个
by hierophant_green @ 2021-10-03 11:08:34