100pts 但 TLE subtask#2 求调
查看原帖
100pts 但 TLE subtask#2 求调
1380676
He_XY楼主2024/10/4 10:07
#include<bits/stdc++.h>
#define sz(v) (int)v.size()
using namespace std;
const int maxn=1e6+5;
string s;
int p[maxn];
struct Node{
	int AND;
	int OR;
	bool val;
};
Node mnd(int a,int b,bool c){
	Node ret;
	
	ret.AND=a;
	ret.OR=b;
	ret.val=c;
	return ret;
}
Node dfs(int l,int r){
	if(r-l==0){
		if(s[l]=='0') return mnd(0,0,0);
		else return mnd(0,0,1);
	}
	if(s[r]==')'&&s[l]=='('&&p[r]==l){
		l++;
		r--;
	}
	int sym=-1;
	for(int i=r;i>=l;i--){
		if(s[i]==')'){
			i=p[i];
		}else if(s[i]=='|'){
			sym=i;
			break;
		}
	}
	if(sym==-1){
		for(int i=r;i>=l;i--){
			if(s[i]==')'){
				i=p[i];
			}else if(s[i]=='&'){
				sym=i;
				break;
			}
		}
	}
	if(s[sym]=='|'){
		if(sym-l==1){
			if(s[l]=='1'){
				return mnd(0,1,1);
			}else{
				return dfs(sym+1,r);
			}
		}
		Node cur=dfs(l,sym-1);
		if(cur.val==1){
			return mnd(cur.AND,cur.OR+1,1);
		}else{
			if(r-sym==1){
				if(s[r]=='1'){
					return mnd(cur.AND,cur.OR,1);
				}else{
					return mnd(cur.AND,cur.OR,0);
				}
			}else{
				Node cur2=dfs(sym+1,r);
				return mnd(cur.AND+cur2.AND,cur.OR+cur2.OR,cur2.val);
			}
		}
	}else{
		if(sym-l==1){
			if(s[l]=='0'){
				return mnd(1,0,0);
			}else{
				return dfs(sym+1,r);
			}
		}
		Node cur=dfs(l,sym-1);
		if(cur.val==0){
			return mnd(cur.AND+1,cur.OR,0);
		}else{
			if(r-sym==1){
				if(s[r]=='1'){
					return mnd(cur.AND,cur.OR,1);
				}else{
					return mnd(cur.AND,cur.OR,0);
				}
			}else{
				Node cur2=dfs(sym+1,r);
				return mnd(cur.AND+cur2.AND,cur.OR+cur2.OR,cur2.val);
			}
		}
	}
}
int main(){
	cin>>s;
	vector<int> tmp;
	for(int i=sz(s)-1;i>=0;i--){
		if(s[i]==')'){
			tmp.push_back(i);
		}else if(s[i]=='('){
			p[tmp.back()]=i;
			tmp.pop_back();
		}
	}
	Node ans=dfs(0,sz(s)-1);
	
	cout<<ans.val<<endl;
	cout<<ans.AND<<" "<<ans.OR<<endl;
}
2024/10/4 10:07
加载中...