萌新求助,本地AC提交TLE >_<
查看原帖
萌新求助,本地AC提交TLE >_<
238408
vectorwyxSD省选加油楼主2021/3/27 23:04

RT,下载数据之后用ide测了一下发现似乎是读入字符串后在turn函数那边卡住了,但是蒟蒻真的想不通为什么。求好心的巨佬帮帮忙QAQ

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<ctime>
#include<cstdlib>
#define ll long long
#define fo(i,x,y) for(register int i=x;i<=y;++i)
#define go(i,x,y) for(register int i=x;i>=y;--i)
using namespace std;
inline int read(){int x=0,fh=1; char ch=getchar(); while(!isdigit(ch)){if(ch=='-') fh=-1; ch=getchar();} while(isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0'; ch=getchar();} return x*fh;}

const int N=30,lim=100,inf=2e9;
int random(int x,int y){
	return rand()%(y-x+1)+x;
}
string s;
char st[N];
int fl[N][2],top,a1[N][2],n[2],stk[N],mod[]={1000000007,998244353,19260817};
char a2[N][2];

void add1(char x,int od){
	++n[od];
	if(x=='a') fl[n[od]][od]=1,a1[n[od]][od]=-inf;
	else fl[n[od]][od]=0,a2[n[od]][od]=x;;
}

void add2(int x,int od){
	//printf("add2(%d,%d)\n",x,od);
	++n[od];
	fl[n[od]][od]=1,a1[n[od]][od]=x;
}

int level(char x){
	if(x=='+'||x=='-') return 1;
	if(x=='*') return 2;
	if(x=='^') return 3;
	return -1;
}

void turn(int od){//把当前的中缀表达式转为后缀表达式存储到序号od的数组里 
	top=0;n[od]=0;
	int len=s.size();
	fo(i,0,len-1){
		char x=s[i];
		if(x==' ') continue;
		else if(x=='a') add1(x,od);
		else if(isdigit(x)){
			int y=x^48;
			while(isdigit(s[i+1])) y=x*10+(s[++i]^48);
			add2(y,od);
		}else if(x=='(') st[++top]=x;
		else if(x==')'){
			while(st[top]!='(') add1(st[top--],od);
			top--;
		}else{
			int k=level(x);
			while(level(st[top])>=k) add1(st[top--],od);
			st[++top]=x;
		}
	}
	while(top) add1(st[top--],od);
}

int ksm(int x,int y,int lmq){
	int ans=1,t=x;
	while(y){
		if(y&1) ans=1ll*ans*t%lmq;
		t=1ll*t*t%lmq;
		y>>=1;
	}
	return ans;
}

int opt(int x,int y,char c,int lmq){
	if(c=='+') return (x+y)%lmq;
	if(c=='-') return (x-y+lmq)%lmq;
	if(c=='*') return 1ll*x*y%lmq;
	if(c=='^') return ksm(x,y,lmq);
}

int get_val(int x,int y,int od){
	top=0;
	fo(i,1,n[od]){
		if(fl[i][od]){
			if(a1[i][od]==-inf) stk[++top]=x;
			else stk[++top]=a1[i][od];
		}else stk[--top]=opt(stk[top],stk[top+1],a2[i][od],y);
	}
	return stk[1];
}

inline int rndm(int x,int y){
	return rand()%(y-x+1)+x; 
}

int main(){
	srand(time(0)+20060428);
	getline(cin,s);turn(0);
	int q=read();
	string ans="";
	fo(i,0,q-1){
		getline(cin,s);turn(1);
		fo(j,1,lim){
			int x=rndm(1,100000),y=mod[rndm(0,2)];
			if(get_val(x,y,0)!=get_val(x,y,1)) goto H;
		}
		ans+=('A'+i);
		H:;
	}
	cout<<ans;
	return 0;
}
2021/3/27 23:04
加载中...