#9 TLE过不了
查看原帖
#9 TLE过不了
727076
hexz01楼主2023/10/19 13:50
#include <iostream>
#include <cstring>
#include <string>
using namespace std;
#define N 30
int n, tot=0;
int a[N], b[N], c[N];
int num[N], zimu[N];//num:字母表示的数,为-1表示不确定
bool pd[N];
inline bool check(){
    int jinwei=0;
    for(int i=n-1;i>=0;i--){
        int tmp=num[a[i]]+num[b[i]]+jinwei;
        if(tmp%n!=num[c[i]])
            return 0;
        jinwei=tmp/n;
    }
    return 1;
}
void dfs(const int now){
    if(num[a[0]]+num[b[0]]>=n)//最高为有进位
        return;
    for(int i=n-1;i>=0;i--){
        if(num[a[i]]==-1 || num[b[i]]==-1 || num[c[i]]==-1)
            continue;
        if((num[a[i]]+num[b[i]])%n!=num[c[i]] && (num[a[i]]+num[b[i]]+1)%n!=num[c[i]])//进不进位都不行
            return;
    }
    if(now==n){
        if(check()){
            for(int i=0;i<n;i++)
                cout<<num[i]<<" ";
            cout<<endl;
        }
        return;
    }
    for(int i=0;i<n;i++){//因为是n进制,只能有0~n-1这n个数
        if(pd[i]==0){//这个数字没有用过
            num[zimu[now]]=i;//修改
            pd[i]=1;

            dfs(now+1);//递归

            num[zimu[now]]=-1;//回溯
            pd[i]=0;
        }
    }
    return;
}
int main(){
    string A, B, C;
    cin>>n;
    cin>>A>>B>>C;
    for(int i=0;i<n;i++){
        a[i]=A[i]-'A';
        b[i]=B[i]-'A';
        c[i]=C[i]-'A';
        if(pd[a[i]]==0){
            pd[a[i]]=1;
            zimu[tot++]=a[i];
        }
        if(pd[b[i]]==0){
            pd[b[i]]=1;
            zimu[tot++]=b[i];
        }
        if(pd[c[i]]==0){
            pd[c[i]]=1;
            zimu[tot++]=c[i];
        }
    }
    for(int i=0;i<n;i++){//因为是-1,不能memset
        num[i]=-1;
    }
    memset(pd, 0, sizeof(pd));
    dfs(0);
    return 0;
}

开氧气了。

2023/10/19 13:50
加载中...