M_sea

洛谷1054 等价表达式
Luogu分析这题坑的程度和神经网络有的一拼。神经网络那题是题面毒瘤,比如公式对第一层不适用、公式的$U_i$到底...
扫描右侧二维码阅读全文
06
2018/10

洛谷1054 等价表达式

Luogu

分析

这题坑的程度和神经网络有的一拼。

神经网络那题是题面毒瘤,比如公式对第一层不适用、公式的$U_i$到底放在哪。

这题是数据毒瘤,比如括号不匹配。

重点是括号不匹配还要直接忽略。


直接展开合并不好搞。考虑随机代一个数进去。

然后按常规方法计算即可。

代码

#include <bits/stdc++.h>
#define re register
#define MOD 998244353
typedef int mainint;
#define int long long
using namespace std;

int n;
char a[60];
char b[30][60];
int la,lb[30];
int no[30];

inline void get_string(char* s) {
    char c; int len=0;
    do c=getchar(); while (c=='\r'||c=='\n');
    while (233) {
        if (c=='\r'||c=='\n') break;
        s[len++]=c;
        c=getchar();
    }
    s[len]='\0';
}
inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=(X<<3)+(X<<1)+c-'0',c=getchar();
    return X*w;
}

inline int Pow(int a,int k,int p) {
    int rt=1;
    for (re int i=1;i<=k;i++) (rt*=a)%=p;
    return rt;
}

inline int calc(char* s,int l,int r,int a) { //计算表达式 
    int tmp=0,p[60],f=0,have_a=0,pos=l,Min=2147483647; //p:优先级 
    memset(p,0x3f,sizeof(p));
    for (re int i=l;i<=r;i++) {
        if (s[i]=='(') tmp+=100;
        else if (s[i]==')') tmp-=100;
        else if (s[i]=='+'||s[i]=='-') p[i]=tmp+1,f=1;
        else if (s[i]=='*') p[i]=tmp+2,f=1;
        else if (s[i]=='^') p[i]=tmp+3,f=1;
        else if (s[i]=='a') have_a=1;
        if (p[i]<=Min) pos=i,Min=p[i]; //这里<=的目的是从前往后算
    }
    if (!f) {
        if (have_a) return a;
        int rt=0;
        for (re int i=l;i<=r;i++)
            if (isdigit(s[i])) (rt=rt*10+s[i]-'0')%=MOD;
        return rt;
    }
    int L=calc(s,l,pos-1,a),R=calc(s,pos+1,r,a);
    if (s[pos]=='+') return (L+R)%MOD;
    else if (s[pos]=='-') return (L-R+MOD)%MOD;
    else if (s[pos]=='*') return L*R%MOD;
    else if (s[pos]=='^') return Pow(L,R,MOD);
}

mainint main() {
    get_string(a+1); la=strlen(a+1);
    n=read();
    for (re int i=1;i<=n;i++) {
        get_string(b[i]+1);
        lb[i]=strlen(b[i]+1);
    }
    int x=rand()%1000,ans=calc(a,1,la,x);
    for (re int j=1;j<=n;j++) {
        int now=calc(b[j],1,lb[j],x);
        if (!no[j]&&now!=ans) no[j]=1;
    }
    for (re int i=1;i<=n;i++)
        if (!no[i]) putchar(i+'A'-1);
    putchar('\n');
    return 0;
}
最后修改:2019 年 05 月 26 日 03 : 04 PM

发表评论