为什么开O2 TLE,不开O2 90分,求dalao解答
查看原帖
为什么开O2 TLE,不开O2 90分,求dalao解答
1035550
cc1ifsb楼主2023/10/30 21:22
#include<bits/stdc++.h>
#include<stack>
using namespace std;
char ch[53];
long long st[53];
bool flag[53];
bool f[53];
bool OwO[53];
long long QwQ[53];
int sum=0,j=0,n=0,mod=1e9+7;
stack <char> ops;
stack <char> iQ7;
inline int quickPower(int n1,int n2){
    int ans = 1,pow1 = n1;
    while(n2){
        if(n2&1) ans = ans*pow1%mod;
        pow1 = pow1*pow1%mod;
        n2>>=1;
    }
    return ans%mod;
}
void change(int n) {
	sum=0;
	memset(st,0,sizeof(st));
	memset(OwO,0,sizeof(OwO));
	char ch1;
	for(int i=1;i<=n;i++) {
		if(!flag[i]) {
			st[++sum]=QwQ[i];
		} else {
			ch1=QwQ[i];
			if(ch1=='(') {
				ops.push(ch1);
			} else if(ch1==')') {
				bool cxkngm=false;
				while(!ops.empty()) {
					iQ7.push(ops.top());
					if(ops.top()=='(') cxkngm=true;
					ops.pop();
				}
				while(!iQ7.empty()) {
					ops.push(iQ7.top());
					iQ7.pop();
				}
				if(cxkngm) {
					while(!ops.empty() && ops.top()!='(') {
						st[++sum]=ops.top();
						OwO[sum]=1;
						ops.pop();
					}
					ops.pop();
				}
			} else if(ch1=='^') {
				while(!ops.empty() && ops.top()=='^') {
					st[++sum]=ops.top();
					OwO[sum]=1;
					ops.pop();
				}
				ops.push('^');
			} else if(ch1=='*') {
				while(!ops.empty() && (ops.top()!='+' && ops.top()!='-') && ops.top()!='(') {
					st[++sum]=ops.top();
					OwO[sum]=1;
					ops.pop();
				}
				ops.push(ch1);
			} else if(ch1=='+' || ch1=='-') {
				while(!ops.empty() && ops.top()!='(') {
					st[++sum]=ops.top();
					OwO[sum]=1;
					ops.pop();
				}
				ops.push(ch1);
			}
		}
	}
	while(!ops.empty()) {
        if(ops.top()!='(')  {
            st[++sum]=ops.top();
    		OwO[sum]=1;
        }
		ops.pop();
	}
}
int init() {
	memset(QwQ,0,sizeof(QwQ));
	memset(flag,0,sizeof(flag));
	memset(f,0,sizeof(f));
	memset(ch,0,sizeof(ch));
	n=0;
	int opq=0;
	while((ch[opq++]=getchar())!='\n');
	for(int i=0;i<strlen(ch);i++) {
		int j=i;
		if(ch[j]>=48 && ch[j]<=57) {
			++n;
			while(int(ch[j])>=48 && int(ch[j])<=57 && j<strlen(ch)) {
				QwQ[n]=QwQ[n]*10+(ch[j]-'0');
				++j;
			}
			i=j-1;
		} else if(ch[i]=='a') {
			QwQ[++n]=2;
		} else if(ch[i]!=' '){
			++n;
			flag[n]=1;
			QwQ[n]=ch[i];
		}
	}
	change(n);
	int ans=sum;
	while(ans>1) {
		int j=0;
		while(!OwO[++j] && j<=sum);
		int l=j,r=j;
		while(f[--l] && l>=1);
		f[l]=1;
		while(f[--r] && r>=1);
		f[r]=1;
		char ch2=st[j];OwO[j]=0;
		if(ch2=='+') st[j]=(st[r]+st[l])%mod;
		else if(ch2=='-') st[j]=(st[r]-st[l])%mod;
		else if(ch2=='*') st[j]=(st[r]*st[l])%mod;
		else if(ch2=='^') st[j]=(quickPower(st[r],st[l]))%mod;
		ans-=2;
		if(ans==1) {
			return st[j];
		}
	}
}
int main() {
	int ans=init();
	int t;
	cin>>t;
	char s[114514];
	int num=0;
	for(int i=1;i<=t+1;i++) {
		int o=init();
		if(ans==o) {
			if(char((i-2)+'A')>='A' && char((i-2)+'A')<='Z')
				s[num++]=char((i-2)+'A');
		}
	}
	cout<<s<<endl;
}
2023/10/30 21:22
加载中...