题解 P1054 【等价表达式】

Salamander · 2017-10-18 19:42:54 · 题解

由于不太好处理带有未知数的表达式，我们考虑将a取值，然后带入计算。

我们只需要随机取多次a的值检验，即可保证极高的正确率。

洛谷的数据是windows环境下造的，行尾有一个多余的'\r'，判断空白字符的时候要注意一下。

所以用栈转换称后缀表达式，每次用栈计算即可。

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

#define For(i,_beg,_end) for(int i=(_beg),i##end=(_end);i<=i##end;++i)
#define Rep(i,_beg,_end) for(int i=(_beg),i##end=(_end);i>=i##end;--i)

template<typename T>T Max(const T &x,const T &y){return x<y?y:x;}
template<typename T>T Min(const T &x,const T &y){return x<y?x:y;}
template<typename T>int chkmax(T &x,const T &y){return x<y?(x=y,1):0;}
template<typename T>int chkmin(T &x,const T &y){return x>y?(x=y,1):0;}
template<typename T>void read(T &x){
    T f=1;char ch=getchar();
    for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;
    for(x=0;ch>='0'&&ch<='9';ch=getchar())x=x*10+ch-'0';
    x*=f;
}

typedef unsigned long long LL;
const int N=110;
int n,top,suf[N][N],lvl[256],m[N];
LL Sta[N];
char sta[N],str[N];
bool b[N];

void Work(int id){
    int len=strlen(str+1),cnt=0;top=0;
    For(i,1,len){
        if(str[i]=='a')suf[id][++cnt]=-1;
        else if(str[i]>='0'&&str[i]<='9'){
            int j=i,x=0;
            while(str[j]>='0'&&str[j]<='9')x=x*10+str[j++]-'0';
            i=j-1;suf[id][++cnt]=x;
        }
        else if(str[i]=='('||str[i]=='+'||str[i]=='-'||str[i]=='*'||str[i]=='^'){
            while(top&&sta[top]!='('&&lvl[sta[top]]>=lvl[str[i]]){
                suf[id][++cnt]=sta[top]+10000;
                top--;
            }
            sta[++top]=str[i];
        }
        else if(str[i]==')'){
            while(top&&sta[top]!='(')suf[id][++cnt]=sta[top--]+10000;
            top--;
        }
    }
    while(top){
        if(sta[top]!='(')suf[id][++cnt]=sta[top]+10000;
        top--;
    }
    m[id]=cnt;
}
LL power(LL x,LL y){
    LL res=1;
    for(;y;y>>=1,x*=x) if(y&1)res*=x;
    return res;
}
LL calc(LL x,LL y,char c){
    if(c=='+')return x+y;
    if(c=='-')return x-y;
    if(c=='*')return x*y;
    if(c=='^')return power(x,y);
}
LL Calc(int id,int a){
    top=0;
    For(i,1,m[id]){
        if(suf[id][i]==-1)Sta[++top]=a;
        else if(suf[id][i]>10000){
            LL res=calc(Sta[top-1],Sta[top],suf[id][i]-10000);
            Sta[--top]=res;
        }
        else Sta[++top]=suf[id][i];
    }
    return Sta[top];
}

int main(){
    lvl['+']=lvl['-']=0;
    lvl['*']=1;lvl['^']=2;
    lvl['(']=lvl[')']=3;
    cin.getline(str+1,N);
    read(n);getchar();Work(0);
    For(i,1,n){
        cin.getline(str+1,N);
        Work(i);
    }
    For(i,1,100){
        int x=rand();
        LL temp=Calc(0,x);
        For(j,1,n)
            if(Calc(j,x)!=temp)b[j]=true;
    }
    For(i,1,n) if(!b[i])putchar('A'+i-1);
    putchar(10);
    return 0;
}