【NOIP2005提高】等价表达式

好 ** 的题目，用 getline 会 RE 。

膜拜机房直接暴力化简多项式的大佬 %%%

解法

很明显无法直接对多项式进行化简~~我不会~~，因此考虑特殊值法。枚举

0\le a\le100

，暴力判断每个选项的这 100 个值是否与题干相等。然后表达式求值即可。

注意

由于 Linux 的特性，使用 getline 会 RE 。详见这个帖子。感谢 @wsm52 大佬的字符串快读模板。
会爆 long long 。如果你不想写高精度，就最好在表达式求值的时候进行取模。

Code

CPP

#include<bits/stdc++.h>
#define md 1000000007
typedef long long ll;
using namespace std;
ll n,vis[1145],rd[15];
string s1,s;
stack<ll>a;
stack<char>b;
vector<ll>as,nw;
ll pw(ll x,ll y){
	ll ans=1;
	while(y--)ans=(ans*x)%md;
	return ans;
}
ll sv(ll v){
	for(int i=0;i<s.size();i++){
		if(s[i]=='(')b.push('(');
		else if(s[i]=='a')a.push(v);
		else if(s[i]<='9'&&s[i]>='0'){
			ll vv=0;
			while(s[i]<='9'&&s[i]>='0'){
				vv=vv*10+s[i]-'0';
				i++;
			}
			i--;
			a.push(vv);
		}else if(s[i]==')'){
			while(b.size()&&b.top()!='('){
				auto nx=a.top();
				a.pop();
				auto pr=a.top();
				a.pop();
				if(b.top()=='+')a.push((pr+nx)%md);
				else if(b.top()=='-')a.push((pr-nx+md)%md);
				else if(b.top()=='*')a.push(pr*nx%md);
				else a.push(pw(pr,nx));
				b.pop();
			}
			if(b.size())b.pop();
		}else{
			while(b.size()&&vis[b.top()]>=vis[s[i]]){
				auto nx=a.top();
				a.pop();
				auto pr=a.top();
				a.pop();
				if(b.top()=='+')a.push((pr+nx)%md);
				else if(b.top()=='-')a.push((pr-nx+md)%md);
				else if(b.top()=='*')a.push(pr*nx%md);
				else a.push(pw(pr,nx));
				b.pop();
			}
			b.push(s[i]);
		}
	}
	ll ans=a.top();
	a.pop();
	return ans;
}
string read(){
    string ss;
    char ch = getchar();
    while(ch=='\n'||ch=='\r'||ch==' ') ch=getchar();
    while(ch!='\n'&&ch!='\r'){
        if(ch!=' ') ss+=ch;
        ch=getchar();
        if(ch==EOF) break;
    }
    return ss;
}
int main(){
	vis['+']=vis['-']=1;
	vis['*']=2;
	vis['^']=3;
	s1=read();
	s1="("+s1+")";
	for(auto it:s1)if(it!=' ')s.push_back(it);
	for(int i=0;i<=100;i++)as.emplace_back(sv(i));
	cin>>n;
	for(int i=0;i<n;i++){
		s1=read();
		s1="("+s1+")";
		s="";
		for(auto it:s1)if(it!=' ')s.push_back(it);
		for(int j=0;j<=100;j++)nw.emplace_back(sv(j));
		if(nw==as)cout<<char('A'+i);
		nw.clear();
	}
	return 0;
}

【NOIP2005提高】等价表达式

文章操作

解法

注意

Code

相关推荐

评论

【NOIP2005提高】等价表达式