\(\texttt{洛谷の题目链接}\) 与 \(\texttt{Topsの题目链接}\) 以及 \(\texttt{Hydroの题目链接}\)
这道题是 \(\texttt{CSP-2020}\) 普及组的 第三题 ,但个人认为比第四题还要恶心
当时考场上这道题没写出来,现在发现这道题的算法和思想其实是 结论和模拟
首先考虑最关键的询问:因为每个询问都要修改一个数,每次在线修改太过复杂,时间也会承受不了,所以我们考虑先把答案算出来,对于每个数判断它对答案的影响(因为答案只属于 \(0\) 和 \(1\) 中 任意一个,所以我们只需要判断改变这个数会不会让答案取非)
大意就是判断一个变量对答案有没有影响,比如 1 | x = 1
和 0 & x = 0
中 \(x\) 就对答案没有任何影响,而 1 & x
和 0 | x
中的 \(x\) 对答案就有关键的影响。根据上面四个例子也可以推出 !x
中 \(x\) 对答案有关键影响
大体方向考虑好以后,我们考虑程序的流程
首先输入了一行后缀表达式,我们要解出这道题目肯定要把这个表达式解析出来,这里我们考虑利用栈来建立 表达式树 以处理这个后缀表达式(不清楚 表达式树 的看 这里 或自行在百度、B站等网站上搜索)
然后我们对树上的每个变量都打上一个 \(0\) 或 \(1\) 的标记,分类考虑操作符的种类:
&
:对于 &
来说,如果一棵子树结果是 \(0\),就给另一棵子树打上标记 \(1\),代表 另一棵子树的结果不会对答案造成影响,|
:对于 |
来说,如果一棵子树结果是 \(1\),就给另一棵子树打上标记 \(1\),代表 另一棵子树的结果不会对答案造成影响(如果不是就打上标记 \(0\))!
:对于 !
来说,由于 !
一定会对当前变量或表达式产生反转的结果,所以我们利用 德·摩根定律,下传标记让该节点及其子树全部反转(其实可以不用反转子树的)最后我们先计算出该表达式原有的答案 \(ans\),再根据每个询问找到变量的标记,判断该标记是不是 \(1\)
如果是,就直接输出 ans
,如果不是,就输出 !ans
\(AC \quad Code:\)
#include<bits/stdc++.h> using namespace std; int n,cnt,ans,Q; int val[1000009],tra[1000009],pl[1000009]; pair<int,int>tree[1000009]; string str; inline int take(int &p) { p++; int res=0; while(str[p]!=' ') res*=10,res+=str[p++]-48; p--; return res; } inline void work(stack<int>& res,int& now,int vv) { int t1,t2; t1=res.top(),res.pop(),t2=res.top(),res.pop(),res.push(++now); val[cnt]=vv,tree[cnt]=make_pair(t1,t2);//建立表达式树 return; } inline void expr() { cnt=n; stack<int>st; while(!st.empty()) st.pop();//用栈来建立表达式树 for(int i=0;i<str.size();i+=2) switch(str[i]) { case 'x': st.push(take(i));//处理以 i 为起点的数字并压入栈中 break; case '&': work(st,cnt,2);//按上文说的处理运算符 break; case '|': work(st,cnt,3);//同理 break; case '!': tra[st.top()]^=1;//把该结点的标记反转 break; } return; } inline int dfs(int u,int tp) { val[u]^=tp; if(u<=n) return val[u]; pair<int,int>res=make_pair(dfs(tree[u].first,tp^tra[tree[u].first]), dfs(tree[u].second,tp^tra[tree[u].second])); if(val[u]==2) { if(!res.first) pl[tree[u].second]=1; if(!res.second) pl[tree[u].first]=1;//同时打标记 return res.first&res.second; } else { if(res.first==1) pl[tree[u].second]=1; if(res.second==1) pl[tree[u].first]=1; return res.first|res.second; } } inline void push_down(int u) { if(u<=n) return; pl[tree[u].first]|=pl[u],pl[tree[u].second]|=pl[u]; push_down(tree[u].first),push_down(tree[u].second); return; } signed main() { ios::sync_with_stdio(0); cin.tie(0);cout.tie(0);//cin,cout 优化 getline(cin,str); cin>>n; for(int i=1;i<=n;i++) cin>>val[i];//输入 expr();//建立表达式树 ans=dfs(cnt,tra[cnt]);//计算表达式的值 push_down(cnt);//标记从根节点开始下放 cin>>Q; while(Q--) { int u; cin>>u; if(pl[u]) cout<<ans;//如果对答案没影响就直接输出 ans else cout<<!ans;//不然就输出 !ans cout<<endl;//记得换行 } return 0; }