【题解】表达式

我的rp大概真的爆int了。。。
考前我把所有2012-2019pj真题共44题刷了43题。
考前本来有时间做最后一题,但看这玩意儿是后缀表达式,我看过的题里就这一道要用,又懒得写,于是。。就跳过了
于是在CSP2020中,CCF突然猝不及防地出了这道题,在考试的时候我就绝望了。考试的时候又脑子一抽,知道要用栈偏偏用数组,最后把自己绕死了。
这次CSP是真的非常遗憾,如果当时做了这题,我大概300+就有了,也能算J组高分了。

题目链接

解题思路

很容易发现,这是一道后缀表达式的题目。按照常有套路,我们建树做。每一个x?都作为叶子节点。对于逻辑运算:
!:给栈顶的位置上面加个父亲,并求值
&:给栈顶和次栈顶上面加个连接两者的父亲,并求值
|:同&,并求值

数据的q是1e5的,树也是1e5的。如果很不幸是一条链或者接近链都会爆炸,所以我们不能朴素的从叶子节点到根节点全部算一下,而是可以引入一个“废物标记”。

废物标记即如果当前节点为&,左儿子的值为0,右儿子的值无论怎么改都没法改变当前节点。它就是一个废物,每一个废物的子树都是废物节点。
|同上。

于是我们DFS一遍就会得到每一个节点是不是废物,不难想到不是废物节点的点可以直接改变根节点。于是每次询问只需要判断当前节点是否是废物即可。

代码

#include<bits/stdc++.h>
using namespace std;
stack<int> st;
int n,q;
int a[100005];
struct tr{
    int op,sum;//1:! 2:& 3:|
}tree[4000005];
int father[4000005];
int son[4000005][2];
int id[4000005];
int cntid=0;
int tot=0;
char s[1000005];
int fw[4000005];
void DFS(int now){
    if(now==0)return ; 
    if(fw[now])fw[son[now][0]]=fw[son[now][1]]=1;
    DFS(son[now][0]);
    DFS(son[now][1]);
}
int main(){
    scanf("%[^\n]",s);//输入一行带空格的字符串
    int len=strlen(s);
    cin>>n;
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    int tmp=0,tmpp=0;
    for(int i=0;i<len;i++){
        tmp=0,tmpp=0;
        if(s[i]=='x'){
            while(s[++i]<='9'&&s[i]>='0'){
                tmp*=10;
                tmp+=s[i]-'0';
            }
            tree[++tot].sum=a[tmp];
            id[tmp]=tot;
            st.push(id[tmp]);
        }else if(s[i]=='!'){
            tmp=st.top();
            st.pop();
            father[tmp]=++tot;
            tree[father[tmp]].op=1;
            tree[father[tmp]].sum=!tree[tmp].sum;
            son[father[tmp]][0]=tmp;
            st.push(tot);
        }else if(s[i]=='&'){
            tmp=st.top();
            st.pop();
            tmpp=st.top();
            st.pop();
            father[tmp]=father[tmpp]=++tot;
            tree[father[tmp]].op=2;
            tree[father[tmp]].sum=tree[tmp].sum&tree[tmpp].sum;
            son[father[tmp]][0]=tmp;
            son[father[tmp]][1]=tmpp;
            if(tree[tmp].sum==0)fw[tmpp]=1;
            if(tree[tmpp].sum==0)fw[tmp]=1;
            st.push(tot);
        }else if(s[i]=='|'){
            tmp=st.top();
            st.pop();
            tmpp=st.top();
            st.pop();
            father[tmp]=father[tmpp]=++tot;
            tree[father[tmp]].op=3;
            tree[father[tmp]].sum=tree[tmp].sum|tree[tmpp].sum;
            son[father[tmp]][0]=tmp;
            son[father[tmp]][1]=tmpp;
            if(tree[tmp].sum==1)fw[tmpp]=1;
            if(tree[tmpp].sum==1)fw[tmp]=1;
            st.push(tot);
        }
    }
    DFS(tot);
    scanf("%d",&q);
    int ans=0;
    for(int i=1;i<=q;i++){
        scanf("%d",&tmp);
        int now=id[tmp],was;
        if(fw[now])cout<<tree[tot].sum<<endl;
        else cout<<!tree[tot].sum<<endl;
    }
    return 0;
} 

本文链接:http://kaispace.com.cn/index.php/archives/757/

如果未注明出处,复制公开后需将注明本博客链接。
打赏作者