【NOIP2005提高】等价表达式

stO_kkk · 2025-05-02 16:57:58 · 题解

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

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

解法

很明显无法直接对多项式进行化简我不会，因此考虑特殊值法。枚举 0\le a\le100 ，暴力判断每个选项的这 100 个值是否与题干相等。然后表达式求值即可。

注意

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

   Code

   #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;
   }