简答题 偏难
#22118

表达式(expr)

表达式(expr)


未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include &lt;bits/stdc++.h&gt; using namespace std; /* 取反某一个操作数的值时,原表达式的值为多少 思路: 1.读入表达式,将表达式建成二叉树 2.计算出表达式的值 3.深搜,求出哪些结点的值修改后对结果有影响 */ const int N = 1e6 + 10; struct node{     int to,next; }a[N];//邻接表 int pre[N],k;//存储以每个点为起点的最后一条边的编号 int num[N];//存储二叉树每个结点的值 char c[N];//存储操作符 int m;//表示c数组的下标 bool f[N];//标记哪些点的值修改后对结果有影响 int n; string s,w;//w用来存储每个操作数的下标 stack&lt;int&gt; st;//用于计算后缀表达式 //建边 void add(int u,int v){     k++;     a[k].to = v;     a[k].next = pre[u];     pre[u] = k; } //深搜求哪些结点的值修改后对结果有影响 void dfs(int x){     f[x] = true;     if(x &lt;= n) return;//如果是叶子结点     if(c[x] == '!') dfs(a[pre[x]].to);     else{         int n1 = a[pre[x]].to,n2 = a[a[pre[x]].next].to;         if(c[x] == '&amp;'){             if(num[n1] == 1) dfs(n2);             if(num[n2] == 1) dfs(n1);         }else if(c[x] == '|'){             if(num[n1] == 0) dfs(n2);             if(num[n2] == 0) dfs(n1);         }     } } int main() {     getline(cin,s);     cin&gt;&gt;n;     for(int i = 1;i &lt;= n;i++){         scanf("%d",&amp;num[i]);     }     //分析表达式,建树     int x,y;     m = n;     for(int i = 0;i &lt; s.size();i++){         if(isdigit(s[i])){             w = w + s[i];             //如果连续数字结束             if(i==s.size()-1||!isdigit(s[i+1])){                 st.push(atoi(w.c_str()));//将操作数的下标入栈                 w = "";             }         }else if(s[i] == '!'){             //如果是取反操作符             m++;             c[m] = s[i];//操作符的编号是m             x = st.top();//取栈顶元素来运算             st.pop(); //出栈             //建边             add(m,x);             num[m] = !num[x];             st.push(m);         }else if(s[i] == '&amp;' || s[i] == '|'){             //如果是&amp; |操作符             m++;             c[m] = s[i];             //取2个操作数             x = st.top();             st.pop();             y = st.top();             st.pop();             //建边             add(m,x);             add(m,y);             //计算结点的值             if(s[i] == '&amp;') num[m] = num[x] &amp; num[y];             else if(s[i] == '|') num[m] = num[x] | num[y];             st.push(m);         }     }     int ans = num[st.top()];     //cout&lt;&lt;ans;     //深搜求哪些结点的值修改后对结果有影响     dfs(st.top());//从根开始深搜     //q次询问     int q;     cin&gt;&gt;q;     while(q--){         scanf("%d",&amp;x);         if(f[x]==true) printf("%d\n",!ans);         else printf("%d\n",ans);     }     return 0; }</pre><p><br/></p>
这道题暂未补解析。