QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#544959#7858. Basic Equation SolvingXfJbUhpyzgaW#WA 337ms3956kbC++145.0kb2024-09-02 21:14:372024-09-02 21:14:38

Judging History

你现在查看的是最新测评结果

  • [2024-09-02 21:14:38]
  • 评测
  • 测评结果:WA
  • 用时:337ms
  • 内存:3956kb
  • [2024-09-02 21:14:37]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const int mod=998244353;
char ch[100],a[15][100],b[15][100],op[15];
int len[15],val[256];
int n,ans=0;
void dfs(int x,int i){
    if (i>len[x]) ++x,i=1;
    if (x>n){
        int res=1;
        for (char i='A';i<='Z';++i) if (val[i]==-1) res=10ll*res%mod;
        (ans+=res)%=mod;
        // printf("%d\n",res);
        return;
    }
    if (op[x]=='<'){
        if (val[a[x][i]]!=-1 && val[b[x][i]]!=-1){
            if (val[a[x][i]]<val[b[x][i]]) dfs(x+1,1);
            else if (val[a[x][i]]==val[b[x][i]]){
                if (i==len[x]) return;
                dfs(x,i+1);
            }
            else return;
        }
        else if (val[a[x][i]]!=-1 && val[b[x][i]]==-1){
            for (int v=val[a[x][i]]+1;v<=9;++v){
                val[b[x][i]]=v;
                dfs(x,len[x]+1);
                val[b[x][i]]=-1;
            }
            if (i!=len[x]){
                val[b[x][i]]=val[a[x][i]];
                dfs(x,i+1);
                val[b[x][i]]=-1;
            }
        }
        else if (val[a[x][i]]==-1 && val[b[x][i]]!=-1){
            for (int v=0;v<val[b[x][i]];++v){
                val[a[x][i]]=v;
                dfs(x,len[x]+1);
                val[a[x][i]]=-1;
            }
            if (i!=len[x]){
                val[a[x][i]]=val[b[x][i]];
                dfs(x,i+1);
                val[a[x][i]]=-1;
            }
        }
        else{
            for (int va=0;va<=9;++va)
                for (int vb=va;vb<=9;++vb)
                    if (va<vb){
                        val[a[x][i]]=va,val[b[x][i]]=vb;
                        dfs(x,len[x]+1);
                        val[a[x][i]]=val[b[x][i]]=-1;
                    }
                    else if (i!=len[x]){
                        val[a[x][i]]=val[b[x][i]]=va;
                        dfs(x,i+1);
                        val[a[x][i]]=val[b[x][i]]=-1;
                    }
        }
    }
    else if (op[x]=='='){
        if (val[a[x][i]]!=-1 && val[b[x][i]]!=-1){
            if (val[a[x][i]]==val[b[x][i]]) dfs(x,i+1);
            else return;
        }
        else if (val[a[x][i]]!=-1 && val[b[x][i]]==-1){
            val[b[x][i]]=val[a[x][i]];
            dfs(x,i+1);
            val[b[x][i]]=-1;
        }
        else if (val[a[x][i]]==-1 && val[b[x][i]]!=-1){
            val[a[x][i]]=val[b[x][i]];
            dfs(x,i+1);
            val[a[x][i]]=-1;
        }
        else{
            for (int v=0;v<=9;++v){
                val[a[x][i]]=val[b[x][i]]=v;
                dfs(x,i+1);
                val[a[x][i]]=val[b[x][i]]=-1;
            }
        }
    }
    else{// >
        if (val[a[x][i]]!=-1 && val[b[x][i]]!=-1){
            if (val[a[x][i]]>val[b[x][i]]) dfs(x+1,1);
            else if (val[a[x][i]]==val[b[x][i]]){
                if (i==len[x]) return;
                dfs(x,i+1);
            }
            else return;
        }
        else if (val[a[x][i]]!=-1 && val[b[x][i]]==-1){
            for (int v=0;v<val[a[x][i]];++v){
                val[b[x][i]]=v;
                dfs(x,len[x]+1);
                val[b[x][i]]=-1;
            }
            if (i!=len[x]){
                val[b[x][i]]=val[a[x][i]];
                dfs(x,i+1);
                val[b[x][i]]=-1;
            }
        }
        else if (val[a[x][i]]==-1 && val[b[x][i]]!=-1){
            for (int v=val[b[x][i]]+1;v<=9;++v){
                val[a[x][i]]=v;
                dfs(x,len[x]+1);
                val[a[x][i]]=-1;
            }
            if (i!=len[x]){
                val[a[x][i]]=val[b[x][i]];
                dfs(x,i+1);
                val[a[x][i]]=-1;
            }
        }
        else{
            for (int va=0;va<=9;++va)
                for (int vb=0;vb<=va;++vb)
                    if (va>vb){
                        val[a[x][i]]=va,val[b[x][i]]=vb;
                        dfs(x,len[x]+1);
                        val[a[x][i]]=val[b[x][i]]=-1;
                    }
                    else if (i!=len[x]){
                        val[a[x][i]]=val[b[x][i]]=va;
                        dfs(x,i+1);
                        val[a[x][i]]=val[b[x][i]]=-1;
                    }
        }
    }
}
int main(){
    //freopen("b.in","r",stdin);
    scanf("%d",&n);
    for (int i=1;i<=n;++i){
        scanf("%s",ch+1);
        int la=0,lb=0,it=1,L=strlen(ch+1);
        while (ch[it]!='<' && ch[it]!='>' && ch[it]!='=') a[i][++la]=ch[it++];
        op[i]=ch[it++];
        while (it<=L) b[i][++lb]=ch[it++];
        len[i]=max(la,lb);
        if (la<len[i]){
            for (int j=len[i];j>=len[i]-la+1;--j) a[i][j]=a[i][j-(len[i]-la)];
            for (int j=len[i]-la;j>=1;--j) a[i][j]='0';
        }
        if (lb<len[i]){
            for (int j=len[i];j>=len[i]-lb+1;--j) b[i][j]=b[i][j-(len[i]-lb)];
            for (int j=len[i]-lb;j>=1;--j) b[i][j]='0';
        }
    }
    for (int i=0;i<256;++i) val[i]=-1;
    for (int i=0;i<=9;++i) val['0'+i]=i;
    dfs(1,1);
    printf("%d\n",ans);
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3780kb

input:

1
P=NP

output:

766136394

result:

ok single line: '766136394'

Test #2:

score: 0
Accepted
time: 0ms
memory: 3816kb

input:

1
2000CNY>3000USD

output:

0

result:

ok single line: '0'

Test #3:

score: 0
Accepted
time: 1ms
memory: 3956kb

input:

4
AB>CD
E<A
BC>FF
EF>F1

output:

23645065

result:

ok single line: '23645065'

Test #4:

score: 0
Accepted
time: 0ms
memory: 3916kb

input:

2
BC>DD
BD<EA

output:

27271695

result:

ok single line: '27271695'

Test #5:

score: 0
Accepted
time: 1ms
memory: 3896kb

input:

3
CE>ED
CC>BA
BB<AC

output:

426829091

result:

ok single line: '426829091'

Test #6:

score: -100
Wrong Answer
time: 337ms
memory: 3956kb

input:

10
KG<EI
EJ>DA
EB<IH
EB>JG
KF<CF
JC>FC
IC<BJ
FI>HH
KD>AH
AE>GJ

output:

80219740

result:

wrong answer 1st lines differ - expected: '87744507', found: '80219740'