P7073题解
这题比赛中我只拿30，但是离正解非常接近惹，稍微修改就AC。
经我研究这题是氵题哦~（难度不到黄题，但比橙题难上那么一点点。）
后缀表达式改如何处理呢？
1.遇到x，就往后搜索，把x后面的数字记录下来，并把相应的值（1/0）加入一个数组（定义为num），相应的下标加入s1，该数在s1里的位置加入pla，并且把它在s1里的位置入栈；
2.遇到！，取出栈头，把其num取反得到的值加入num，把！加入s1（我定义“！”是1000001，“&”是1000002，“|”是1000003），把其fa改为！在s1 里的位置，再把！在s1里位置入栈。
3.遇到“&”或“|”，取出两个栈头，把相应经过与或者或运算得到的结果加入num，把运算符加入s1，再把两个栈头互相加入到对方的br里，把两个栈头的fa改为&或|在s1里的位置，把运算符的位置加入栈。
4.根据后缀表达式的定义，最后一个字符必定是父节点，即num[s1[0]]就是我们要的答案。
5.为什么遇到运算符，栈头一定就是它的儿子呢？因为如果不先用排在后面的，而选了前面的，那么就一定会有num没有被计算。可以证明，如果后缀表达式无误，则取栈头一定会被计算完。（其实也是后缀表达式的性质awa）
这是处理的代码：
for(int i=0;i<s.length();i++)
{
if(s[i]=='x')
{
s1[0]++;
while(++i && s[i]>='0' && s[i]<='9') s1[s1[0]]=s1[s1[0]]*10+s[i]-'0';
pla[s1[s1[0]]]=s1[0];
num[s1[0]]=a[s1[s1[0]]];
fatherless.push(s1[0]);
}
else
{
if(s[i]=='!')
{
num1=fatherless.top();
fatherless.pop();
s1[++s1[0]]=1000001;
num[s1[0]]=!num[num1];
fatherless.push(s1[0]);
fa[num1]=s1[0];
}
if(s[i]=='&')
{
num1=fatherless.top();
fatherless.pop();
num2=fatherless.top();
fatherless.pop();
s1[++s1[0]]=1000002;
if(num[num1]==1 && num[num2]==1) num[s1[0]]=1;
else num[s1[0]]=0;
fatherless.push(s1[0]);
fa[num1]=s1[0];
fa[num2]=s1[0];
br[num1]=num2;
br[num2]=num1;
}
if(s[i]=='|')
{
num1=fatherless.top();
fatherless.pop();
num2=fatherless.top();
fatherless.pop();
s1[++s1[0]]=1000003;
if(num[num1]==0 && num[num2]==0) num[s1[0]]=0;
else num[s1[0]]=1;
fatherless.push(s1[0]);
fa[num1]=s1[0];
fa[num2]=s1[0];
br[num1]=num2;
br[num2]=num1;
}
}
}接着，对于每一个要取反的数，找到它的fa（显然肯定是一个运算符），如果该数的num取反后对结果没有影响，就直接输出num[s1[0]]，（考试的时候我就忘了这一点，导致TLE，不过加入后稳稳地AC）否则继续dfs。
这是dfs代码：
void f(int k)
{
if(k==s1[0])
{
printf("%d\n",num[k]);
return;
}
if(s1[fa[k]]==1000001)
{
bool nup=num[fa[k]];
if(nup==!num[k])
{
printf("%d\n",num[s1[0]]);
return;
}
num[fa[k]]=!num[k];
f(fa[k]);
num[fa[k]]=nup;
return;
}
if(s1[fa[k]]==1000002)
{
bool nup=num[fa[k]];
if(num[br[k]]==1 && num[k]==1) num[fa[k]]=1;
else num[fa[k]]=0;
if(nup==num[fa[k]])
{
printf("%d\n",num[s1[0]]);
return;
}
f(fa[k]);
num[fa[k]]=nup;
return;
}
if(s1[fa[k]]==1000003)
{
bool nup=num[fa[k]];
if(num[br[k]]==0 && num[k]==0) num[fa[k]]=0;
else num[fa[k]]=1;
if(nup==num[fa[k]])
{
printf("%d\n",num[s1[0]]);
return;
}
f(fa[k]);
num[fa[k]]=nup;
return;
}
}这就是大体的思路，送上完整代码（当中的read（）函数是快读，不过并没有什么用武之地，因为该TLE的都TLE了）：
#include<bits/stdc++.h>
using namespace std;
string s;
int n,q,kk,num1,num2,s1[1000005],pla[100005],fa[1000005],br[1000005];
bool a[100005],num[1000005];
stack<int> fatherless;
void f(int k)
{
if(k==s1[0])
{
printf("%d\n",num[k]);
return;
}
if(s1[fa[k]]==1000001)
{
bool nup=num[fa[k]];
if(nup==!num[k])
{
printf("%d\n",num[s1[0]]);
return;
}
num[fa[k]]=!num[k];
f(fa[k]);
num[fa[k]]=nup;
return;
}
if(s1[fa[k]]==1000002)
{
bool nup=num[fa[k]];
if(num[br[k]]==1 && num[k]==1) num[fa[k]]=1;
else num[fa[k]]=0;
if(nup==num[fa[k]])
{
printf("%d\n",num[s1[0]]);
return;
}
f(fa[k]);
num[fa[k]]=nup;
return;
}
if(s1[fa[k]]==1000003)
{
bool nup=num[fa[k]];
if(num[br[k]]==0 && num[k]==0) num[fa[k]]=0;
else num[fa[k]]=1;
if(nup==num[fa[k]])
{
printf("%d\n",num[s1[0]]);
return;
}
f(fa[k]);
num[fa[k]]=nup;
return;
}
}
int read()
{
int res=0,f=1;
char C=getchar();
while(C<'0' || C>'9')
{
if(C=='-') f=-1;
C=getchar();
}
while(C>='0' && C<='9') res=res*10+C-'0',C=getchar();
return res*f;
}
int main()
{
//freopen("expr.in","r",stdin);
//freopen("expr.out","w",stdout);
getline(cin,s);
n=read();
for(int i=1;i<=n;i++) a[i]=read();
for(int i=0;i<s.length();i++)
{
if(s[i]=='x')
{
s1[0]++;
while(++i && s[i]>='0' && s[i]<='9') s1[s1[0]]=s1[s1[0]]*10+s[i]-'0';
pla[s1[s1[0]]]=s1[0];
num[s1[0]]=a[s1[s1[0]]];
fatherless.push(s1[0]);
}
else
{
if(s[i]=='!')
{
num1=fatherless.top();
fatherless.pop();
s1[++s1[0]]=1000001;
num[s1[0]]=!num[num1];
fatherless.push(s1[0]);
fa[num1]=s1[0];
}
if(s[i]=='&')
{
num1=fatherless.top();
fatherless.pop();
num2=fatherless.top();
fatherless.pop();
s1[++s1[0]]=1000002;
if(num[num1]==1 && num[num2]==1) num[s1[0]]=1;
else num[s1[0]]=0;
fatherless.push(s1[0]);
fa[num1]=s1[0];
fa[num2]=s1[0];
br[num1]=num2;
br[num2]=num1;
}
if(s[i]=='|')
{
num1=fatherless.top();
fatherless.pop();
num2=fatherless.top();
fatherless.pop();
s1[++s1[0]]=1000003;
if(num[num1]==0 && num[num2]==0) num[s1[0]]=0;
else num[s1[0]]=1;
fatherless.push(s1[0]);
fa[num1]=s1[0];
fa[num2]=s1[0];
br[num1]=num2;
br[num2]=num1;
}
}
}
q=read();
for(int i=1;i<=q;i++) kk=pla[read()],num[kk]=!num[kk],f(kk),num[kk]=!num[kk];
return 0;
}这题主要看细心，因为我太粗惹，所以只拿惹30分。其实如果考试不吃巧克力而多花点时间在代码上，爷就320惹，可惜啊。。。