CSP2022 T3 求
  • 板块灌水区
  • 楼主da_ke
  • 当前回复3
  • 已保存回复3
  • 发布时间2023/9/29 15:13
  • 上次更新2023/11/2 17:20:18
查看原帖
CSP2022 T3 求
766675
da_ke楼主2023/9/29 15:13
#include <bits/stdc++.h>
#define rep(i,l,r) for(int i=l;i<=r;++i)

using namespace std;

struct Node{
    int root,lc,rc;
};

const int N=1e6+23;
string s;
stack<int> ops;
stack<int> sta;
vector<int> sf;

int num=0;
int ans1=0,ans2=0;
Node tree[N];

void change(){
    for(auto&i:s){
        if(i=='0'||i=='1')
            sf.push_back(i);
        else if(i=='(')
            ops.push(i);
        else if(i==')')
        {
            while(!ops.empty()&&ops.top()!='(')
            {
                sf.push_back(ops.top());
                ops.pop();
            }
            ops.pop();
        }
        else if(i=='&')
        {
            while(!ops.empty()&&ops.top()=='&')
            {
                sf.push_back(ops.top());
                ops.pop();
            }
            ops.push('&');
        }
        else if(i=='|')
        {
            while(!ops.empty()&&ops.top()!='(')
            {
                sf.push_back(ops.top());
                ops.pop();
            }
            ops.push('|');
        }
    }
    while(!ops.empty())
    {
        sf.push_back(ops.top());
        ops.pop();
    }
}

void build()
{
    for(auto& i:sf){
        if(i=='0'||i=='1')
            tree[++num]={i-'0',-1,-1};
        else{
            int lc=sta.top();sta.pop();
            int rc=sta.top();sta.pop();
            int opt=(i=='&')?2:3; //&->2 |->3
            tree[++num]={opt,lc,rc};
        }
        sta.push(num);
    }
}

bool dfs(int u){
    Node & v=tree[u];
    if(v.root==1||v.root==0)
        return v.root;
    bool ansl=dfs(v.lc);
    if(ansl==0&&v.root==2) //0&
    {
        ans1++;
        return 0;
    }
    if(ansl==1&&v.root==3) //1|
    {
        ans2++;
        return 1;
    }
    bool ansr=dfs(v.rc); //0| or 1&
    return ansr;
}

signed main(){
    cin>>s;
    change();
    build();
    cout<<dfs(num)<<endl;
    cout<<ans1<<' '<<ans2<<endl;
} 

0 pts 样例没过,求条

2023/9/29 15:13
加载中...