记录编号	167572	评测结果	AAAAAAAAAA
题目名称	[NOIP 2005]等价表达式	最终得分	100
用户昵称	mikumikumi	是否通过	通过
代码语言	C++	运行时间	0.003 s
提交时间	2015-06-26 20:15:40	内存使用	0.32 MiB

#include<cstdio>
#include<deque>
#include<stack>
#include<iostream>
#include<string>
#include<cmath>
#include<cstdlib>
#include<climits>
using namespace std;
typedef long long LL; 
int n,SIZE=5;
string a[27],b="~";
LL mod=INT_MAX/2;
deque<LL> Q;
stack<LL> num;
stack<char> lo;
int gf(char x)
{
	if(x=='+'||x=='-') return 1;
	if(x=='*'||x=='/') return 2;
	if(x=='^') return 3;
	else return 0;
}
LL mi(int x,int t)
{
	LL re=1;
	for(int i=1;i<=t;i++)
	{
		re*=x;
		re%=mod;
	}
	return re;
}
LL get(int s,int x)
{
	LL re=0;
	while(!num.empty()) num.pop();
	while(!lo.empty()) lo.pop();
	LL now=-1;
	for(int i=0;i<a[x].length();i++)
	{
		//cout<<a[x][i]<<endl;
		if(a[x][i]>='0'&&a[x][i]<='9')
		{
			//cout<<a[x][i]-'0'<<endl;
			if(now==-1) now=a[x][i]-'0';
			else now=now*10+a[x][i]-'0';
		}
		else if(a[x][i]=='a') num.push(s);
		else
		{
			if(now!=-1) {num.push(now);now=-1;}
			if(a[x][i]=='(') goto NEXT;
			//cout<<a[x][i]<<endl;
			while(!lo.empty()&&gf(lo.top())>=gf(a[x][i]))
			{
				//cout<<a[x][i]<<endl;
				if(a[x][i]==')'&&lo.top()=='(') {lo.pop();break;}
				else
				{
					//cout<<a[x][i]<<endl;
					char v=lo.top();lo.pop();
					LL y1=num.top();num.pop();
					LL y2=num.top();num.pop();
					//cout<<y2<<" "<<v<<" "<<y1<<endl;
					LL tem=0;
					if(v=='+') tem=y2+y1;
					if(v=='-') tem=y2-y1;
					if(v=='*') tem=y2*y1;
					if(v=='^') tem=mi(y2,y1);
					tem%=mod;
					//cout<<tem<<endl;
					num.push(tem);
				}
			}
			NEXT:;
			if(a[x][i]!=')') lo.push(a[x][i]);
		}
	}
	//cout<<endl;
	re=num.top();
	return re;
}
int random(int x,int y)
{
	return rand()%(y-x)+x;
}
void work()
{
	Q.clear();
	for(int i=1;i<=n;i++) Q.push_back(i);
		int now=random(1,20);
		LL std=get(now,0);
		//cout<<std<<endl;
		int m=Q.size();
		for(int j=0;j<m;j++)
		{
			int x=Q.front();Q.pop_front();
			LL tem=get(now,x);
			if(tem==std)
				Q.push_back(x);
			//cout<<x<<' '<<tem<<endl;
		}
		//cout<<"88888888888"<<endl;
}
int main()
{
	freopen("equal.in","r",stdin);
	freopen("equal.out","w",stdout);
	getline(cin,a[0]);
	a[0]+=b;
	scanf("%d",&n);
	string c;
	getline(cin,c);
	for(int i=1;i<=n;i++)
	{
		getline(cin,a[i]);
		a[i]+=b;
	}
	for(int i=0;i<=n;i++)
	{
		while(a[i].find(" ")!=-1)
		{
			a[i].erase(a[i].find(" "),1);
		}
		//cout<<a[i]<<endl;
	}     
	work();
	//cout<<1<<endl;
	for(int i=0;i<Q.size();i++)
	{
		char ans=(char)Q[i]-1+'A';
		cout<<ans;
	}
	return 0;
}