题解 | 进制位-NOIP1998提高组复赛A题

这道题标签是搜索，自然要好好的dfs了。我是先看的题解的，发现一点都不懂，而且代码风格也和我不符，所以自己分析了一下。

首先我分析题意很容易得出进制位是n-1。其次要怎么做呢，我想到了经典的八皇后，就是生成8*8的全排列；那么我是不是可以生成n-2的全排列，然后把字母代换成这些数字，然后按照矩阵求和，看看符不符合呢？

看看数据范围，似乎完全没问题。那么可以开始动手了。枚举每种第一行（也是第一列）的状态（0~n-1）的全排列，求出和，然后赋值给字母,然后字母矩阵求一个和与全排列相比较。如果符合就输出。一些小范围要注意。

如果看别人代码感觉难懂，就自己写好啦，欢迎各位私信我讨论。

另外看起来是道很简单的搜索，一加上字符串难度直接上升到提高难度了

只是抛砖引玉，提供一种思路。递推法需要更多分析，像我这种智商还是好好搜索吧。

#include<cstdio>
#include<iostream>
#include<string>
#include<map>
#include<cstring>
#define maxn 20
using namespace std;
string a[maxn][maxn];//记录数据 
int h[maxn];//第一横行 
int z[maxn]; //第一纵行，这里横行纵行写一个数组就可以了，我是多此一举了 
int n;//注意是n-1个数 
int d[maxn][maxn];//这个是枚举全排列生成的和 
int d2[maxn][maxn];//这个是字母矩阵生成的和 
int vis[maxn];//和生成全排列有关的一个数据 
map<char,int>duiying;//枚举每一种情况后，要把对应的字母和数字对应好 
int getit=0;//我这个判断比较简陋，这个是用来判断是否成功输出了解 
bool check(){
    for(int i=2;i<=n;i++)
    for(int j=2;j<=n;j++){
        d[i][j]=h[i]+z[j];//这个是枚举出来的和 
    }
    memset(d2,0,sizeof(d2));//每一次记得清零 
    for(int i=2;i<=n;i++)
    for(int j=2;j<=n;j++){
        int k=0;
        while(k<=a[i][j].length()-1){//进位，看不懂吗，想想十进制 
        d2[i][j]=d2[i][j]*(n-1)+duiying[a[i][j][k]];
        //或许这个a[i][j][k]不好理解，i，j是矩阵的位置，很好理解，k就是当前字符串的第k个字母啊！ 
        k++;
        }
    }
     for(int i=2;i<=n;i++){
         for(int j=2;j<=n;j++)
         if(d[i][j]!=d2[i][j])return 0;//不对应就算了 
     }
    return 1;
}
void print(){
    getit=1;//这样就不输出error了 
    for(int i=2;i<=n;i++){
    cout<<a[1][i]<<"="<<h[i]<<" ";
    }
    cout<<endl<<n-1<<endl;
}
void dfs(int p){
    for(int i=0;i<=n-2;i++){//是0~n-2的全排列哦，不信你去看看样例 
        if(vis[i])continue;
        vis[i]=1;//
        h[p]=i; 
        z[p]=i;
        duiying[a[1][p][0]]=i;//记录这种对应,a[1][p][0]看起来不好理解，
        //其实就是横行的每个字母，因为要存两个以上的字母所以用字符串,但是第一行第一列一定是单字母  
        if(p==n){//到头了，可以判断了 
        if(check())print();
        vis[i]=0;
        return;
        }
        dfs(p+1);
        vis[i]=0;//回溯 
    }
    return;
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++){
    cin>>a[i][j];
    }
    dfs(2);//从第二个开始，因为第一个是"+" 
    if(!getit)cout<<"ERROR!";
}