洛谷1092 虫食算

Luogu

算法

Dfs。

直接从A搜到Z肯定是不行的,我们要考虑别的方法。

考虑按照位置搜,从个位搜到最高位,从第一行往下搜。

所以这样算法就出来了。

PS:倒着搜可以快600+ms。玄学
PS:细节见代码。

代码

#include <bits/stdc++.h>
#define re register
using namespace std;
int n;
char s[4][30];
int num[100]; //num[ch]表示ch代表的数
bool used[30]; //used[i]表示数i是否被用过 

inline bool Number_Filled() {
    for (re int i='A';i<='A'+n-1;i++)
        if (num[i]==-1) return 0;
    return 1;
}
inline bool check() {
    int add=0;
    for (re int i=n;i>=1;i--) {
        int a=num[s[1][i]],b=num[s[2][i]],c=num[s[3][i]];
        if ((a+b+add)%n!=c) return 0;
        add=(a+b+add)/n;
    }
    if (add) return 0;
    else return 1;
}
inline void Print() {
    for (re int i='A';i<='A'+n-1;i++) printf("%d ",num[i]);
    putchar('\n');
}
inline bool Prune() { //能剪枝返回true,否则返回false 
    if (num[s[1][1]]+num[s[2][1]]>=n) return 1; //最高位进位不行
    for (re int i=n;i>=1;i--) {
        int a=num[s[1][i]],b=num[s[2][i]],c=num[s[3][i]];
        if (a==-1|b==-1||c==-1) continue;
        if ((a+b)%n!=c&&(a+b+1)%n!=c) return 1;
    }
    return 0;
}
inline void Dfs(int x,int y,int add) { //x为行,y为列,add为进位
    if (Number_Filled()) {
        if (check()) { Print(); exit(0); }
        return;
    }
    if (Prune()) return;
    if (num[s[x][y]]==-1) { //没有填
        for (re int i=0;i<n;i++) { //据说倒着搜更快 
             if (used[i]) continue;
             if (x!=3) {
                 used[i]=1; num[s[x][y]]=i;
                 Dfs(x+1,y,add);
                 used[i]=0; num[s[x][y]]=-1;
             }
             else {
                 int sum=num[s[x-1][y]]+num[s[x-2][y]]+add;
                 if (sum%n!=i) continue; //不合法
                used[i]=1; num[s[x][y]]=i;
                Dfs(1,y-1,sum/n);
                used[i]=0; num[s[x][y]]=-1;
            }
        }
    }
    else { //被填过了
        if (x!=3) Dfs(x+1,y,add); 
        else {
            int sum=num[s[x-1][y]]+num[s[x-2][y]]+add;
            if (sum%n!=num[s[x][y]]) return;
            if (Prune()) return;
            Dfs(1,y-1,sum/n);
        }
    }
}

int main() {
     ios::sync_with_stdio(false);
     cin>>n; cin>>s[1]+1>>s[2]+1>>s[3]+1;
     memset(num,-1,sizeof(num));
     Dfs(1,n,0);
     return 0;
}
最后修改:2019 年 09 月 24 日 01 : 00 PM

发表评论