抄的算法竞赛宝典的题解

/*
可以采用一些比较高级的算法，比如解方程之类的，不过通常的
算法是搜索，这个程序也采用搜索的方法 
搜索思路：
1.算式存储方式：A[i][j]表示第j个(从0开始计数)字符串从右往
左数第i个(从0开始计数)字母 
  如样例:ABCED    对应存储于这些元素中 A[4,3,2,1,0][0]
         BDACE                         A[4,3,2,1,0][1]
         EBBAA                         A[4,3,2,1,0][2]
  如此存储，是因为搜索是一位一位进行枚举的，即每次确定
  同一列的字母，如第一次确定A[0][0],A[0][1],A[0][2]三个
  字母
2.A[i][2]=(A[i][0]+A[i][1]+u)%n
  对每一位枚举前两个字母可能对应的数字。如果在之前的搜索
  中字母已经被确定，那此次不需再枚举。若未被确定，则需要
  选择一个数字。 
  当前两个字母确定下来时，第三个字母即得到确定，只需判断
  这个结果是否合法(是否同一个字母对应两个数字，或者同一
  个数字被多个字母使用) 
  其中u表示第i-1位的进位，如果从低位向高位搜索(即从右向
  左)，那么每一次的进位都是确定的
3.剪枝:
  1)每个数字只能被一个字母使用，那么给每个数字做上标记，
  避免被重复使用。
  2)如果最高位出现进位，则等式不成立
  3)如果第三个字母对应的数字已经确定，但是并不是前两个
  字母计算后的结果，那等式不成立
  4)如果前两个字母计算后的结果已经被使用，并且不是被第
  三个字母使用，那等式不成立
  5)如果第三个字母未被确定，那么这一位确定下来后，可能
  会对后面的算式造成影响，甚至直接造成矛盾，后者可以直
  接剪掉 
    直接依次枚举之后的每一位 
    a)如果一个数字不确定，那可以通过另外两个数字计算出
    这个数字，如果这个数字被使用，那等式不成立
      (注意进位，如果进位已经确定则直接计算判断即可，
      否则是否进位两种情况都不成立等式才不成立)
    b)如果三个数字都确定了，那需要计算一下该位等式是否
    成立 
*/
#include <cstdio>
#include <cstdlib>
#include <iostream>
using namespace std;

int n;
char in[3][30];//存储读入的字符串 
int A[30][3];//存储算式 
//标记每个数字是否被使用,1表示被使用，0表示未被使用 
bool use[30];
//记录每个字母对应的数字，-1表示未确定
int num[30]; 
void Search(int,bool);
#define RETURN {num[x]=-1;use[c]=0;return;}//宏定义 还原+返回操作 

//处理第p位第q个数字，前两个数字存储在a中，上一位的进位为u 
void Search2(int p,int q,int a[2],bool u)
{
  int x=A[p][q];
  if(q==2)
  {
    if(p==n-1 && a[0]+a[1]+u>=n) 
      return;//剪枝2 
    int c=(a[0]+a[1]+u)%n,i,j;
    if(num[x]!=-1 && num[x]!=c) 
      return;//剪枝3 
    if(use[c] && num[x]!=c) 
      return;//剪枝4 
    if(num[x]==-1) 
    {
      num[x]=c;
      use[c]=1;
      int up=(a[0]+a[1]+u)/n;
      for(i=p+1;i<n;i++)//剪枝5) 
      {
        int k1=num[A[i][0]],k2=num[A[i][1]],k3=num[A[i][2]];
        if(k1==-1 || k2==-1 || k3==-1)//a)其中up为进位，若up==-1表示进位不确定 
        {
          if(k1!=-1 && k2!=-1 && ((up==-1 && use[(k1+k2)%n] && use[(k1+k2+1)%n])||(up!=-1 && use[(k1+k2+up)%n])))
            RETURN
          else if(k1!=-1 && k3!=-1 && ((up==-1 && use[(k3+2*n-k1)%n] && use[(k3+2*n-1-k1)%n])||(up!=-1 && use[(k3+2*n-up-k1)%n])))
            RETURN
          else if(k2!=-1 && k3!=-1 && ((up==-1 && use[(k3+2*n-k2)%n] && use[(k3+2*n-1-k2)%n])||(up!=-1 && use[(k3+2*n-up-k2)%n])))
            RETURN
          else up=-1;//有两个以上数不确定的情况下，进位也不确定 
        }
        else if((up==-1 && (k1+k2)%n!=k3 && (k1+k2+1)%n!=k3)||(up!=-1 && (k1+k2+up)%n!=k3))//b)
          RETURN
        else if(i==n-1&&((up==-1&&(k1+k2)/n!=0&&(k1+k2+1)/n!=0)||(up!=-1&&(k1+k2+up)/n!=0)))//剪枝2) 
          RETURN
        else up=((k1+k2)>k3);//三个数都确定的情况下要计算进位 
      }
      Search(p+1,(a[0]+a[1]+u)/n);//递归处理下一位 
      num[x]=-1;
      use[c]=0;
    }
    else
      Search(p+1,(a[0]+a[1]+u)/n);
    return;
  }
    
  if(num[x]==-1)//如果字母未被确定 
  {
    for(int i=n-1;i>=0;i--)//倒着取数，避免一些特殊数据 
    {
      if(use[i]==0)//剪枝1 
      {
        num[x]=i;
        use[i]=1;
        a[q]=i;//确定下来的数字作为参数传递下去，更方便 
        Search2(p,q+1,a,u);
        num[x]=-1;
        use[i]=0;
      }
    }
  }
  else//如果字母在之前的搜索已经被确定 
  {
    a[q]=num[x];
    Search2(p,q+1,a,u);
  }
}

void Search(int p,bool u)//处理第p位，上一位进位为u 
{
  if(p>=n)//如果出结果了 
  {
    int i;
    for(i=0;i<n-1;i++)
      cout<<num[i]<<' ';cout<<num[i];
    cout<<endl;
    exit(0);//输出后直接结束程序，节约返回的时间 
  }
  int a[2];
  Search2(p,0,a,u);
}

int main()
{
  for(int i=0;i<30;i++)//初始时所有的字母、数字均未定 
    num[i]=-1,use[i]=0;
    
  cin>>n>>in[0]>>in[1]>>in[2];
  for(int i=0;i<n;i++)//将字符串按预定规则预处理至A数组中 
    for(int j=0;j<3;j++)
      A[n-1-i][j]=in[j][i]-'A';
        
  Search(0,0);//从最低位开始搜索，此时没有进位 
  //cout<<"NO"<<endl;//题目保证有且只有一组解 
  return 0;
}

//c++题解
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<string>
#include<cstdlib>
using namespace std;
char a[30],b[30],c[30];
int t[300],used[30],p[30],u[30],y;
int n;
bool ok_(){
    for(int i=n;i>=1;i--){
        if(t[a[i]]==-1||t[b[i]]==-1||t[c[i]]==-1)continue;
        if((t[a[i]]+t[b[i]])%n!=t[c[i]]){
            if((t[a[i]]+t[b[i]]+1)%n!=t[c[i]])return 0;
        }
    }
    return 1;
}
void Try_(){
    int jw=0;
    for(int i=n;i>=1;i--){
        int s=t[a[i]]+t[b[i]]+jw;
        if(t[c[i]]!=s%n)return ;
        jw=s/n;
    }
    cout<<t['A'];
    for(int i='A'+1;i<='A'+n-1;i++)cout<<' '<<t[i];
    exit(0);
}
void dfs(int now){
    //产生0到n-1的全排列 
    if(now>n){
        Try_();
        return ;
    }
    for(int i=n-1;i>=0;i--){
        if(used[i])continue;
        t[p[now]+'A'-1]=i;
        if(ok_()){
            used[i]=1;
            dfs(now+1);
            used[i]=0;
        }
    }
    t[p[now]+'A'-1]=-1;
}
int main(){
    memset(t,-1,sizeof(t));
    scanf("%d",&n);
    scanf("%s%s%s",a+1,b+1,c+1);
    for(int i=n;i>=1;i--){
        if(!u[a[i]-'A'+1])p[++y]=a[i]-'A'+1,u[a[i]-'A'+1]=1;
        if(!u[b[i]-'A'+1])p[++y]=b[i]-'A'+1,u[b[i]-'A'+1]=1;
        if(!u[c[i]-'A'+1])p[++y]=c[i]-'A'+1,u[c[i]-'A'+1]=1;
    }
    dfs(1);
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
int n;
int res[26];
int used[26];
string a,b,c;
int flag = 0;
char pos[26];
int usedZiMu[26];
int Check()
{
int i;
for (i=n-1;i>=0;i--)
{
char a1=a[i]-'A',b1=b[i]-'A',c1=c[i]-'A';
if(res[a1]!=-1 && res[b1]!=-1 && res[c1]!=-1)
{
if( (res[a1]+res[b1])%n!=res[c1] &&(res[a1]+res[b1]+1)%n!=res[c1])
return 0;
}
if(res[a1]!=-1 && res[b1]!=-1 && res[c1]==-1)
{
int sum1,sum2;
sum1 = (res[a1]+res[b1])%n;
sum2 = (res[a1]+res[b1]+1)%n;
if (used[sum1] && used[sum2])
return 0;
}
if (res[a1]!=-1 && res[b1]==-1 && res[c1]!=-1)
{
int js1,js2;
js1 = (res[c1]-res[a1]+n)%n;
js2 = (res[c1]-res[a1]-1+n)%n;
if (used[js1] && used[js2])
return 0;
}
if (res[a1]==-1 && res[b1]!=-1 && res[c1]!=-1)
{
int js1,js2;
js1 = (res[c1]-res[b1]+n)%n;
js2 = (res[c1]-res[b1]-1+n)%n;
if (used[js1] && used[js2])
return 0;
}

}
return 1;
}
int OK()
{
int i;
int jinwei=0;
int jiahe;
for (i=n-1; i>=0; i--)
{
char a1=a[i]-'A',b1=b[i]-'A',c1=c[i]-'A';

jiahe = (res[a1]+res[b1]+jinwei)%n;
jinwei =( res[a1]+res[b1]+jinwei)/n;
if (jiahe!=res[c1]) return 0;
}
if (jinwei>0) return 0;
return 1;
}
void dfs(int k)
{
int i;
if (flag)
return;
if(k==n)
{
if (OK())
{
for(i=0; i<=n-2; i++) cout<<res[i]<<' ';
cout<<res[n-1]<<endl;
flag=1;
}
return ;
}
for (i=n-1; i>=0; i--)
{
if (!used[i]&&Check() )
{
used[i]=1;
res[pos[k]]=i;
dfs(k+1);
used[i]=0;
res[pos[k]]=-1;
}
}
return ;
}

int main()
{
int k=0,i;
cin>>n;
cin>>a>>b>>c;
memset(res,-1,sizeof(res));
memset(pos,-1,sizeof(pos));
for (i=n-1; i>=0; i--)
{
char a1=a[i]-'A',b1=b[i]-'A',c1=c[i]-'A';
if (!usedZiMu[a1])
{
usedZiMu[a1]=1;
pos[k++] = a1;
}
if (!usedZiMu[b1])
{
usedZiMu[b1]=1;
pos[k++] = b1;
}
if (!usedZiMu[c1])
{
usedZiMu[c1]=1;
pos[k++] = c1;
}
}
dfs(0);
return 0;
}

没什么好说的，注释全在代码里

/*
1.所有的书都是 0 ~ n-1 之间的数
2.满足 a + b = c
3.最高位不允许有进位
4.记忆化，已经被占用的后面就不允许再使用 
*/
#include<bits/stdc++.h>
using namespace std;
int n,q[110],path[110];
int used[110];
string e[3];
bool check()
{
    for(int i = n-1,t = 0;i>=0;i--)
    {
        int a = path[e[0][i]-'A'];
        int b = path[e[1][i]-'A'];
        int c = path[e[2][i]-'A'];
        if(a != -1 && b != -1 && c != -1)
        {
            if(t == -1) // 表示没有进位
            {
                if((a+b)%n != c && (a+b+1)%n != c)
                {
                    return false; 
                }
                if(i == 0 && a+b >= n)
                {
                    return false;
                }
            }
            else // 表示有进位 
            {
                if((a+b+t)%n != c)
                {
                    return false;
                }
                if(i == 0 && a+b+t >= n)
                {
                    return false; 
                }
                t = (a+b+t)/n; // 更新进位 
            }
        }
        else
        {
            t = -1; // 标记 t 没有进位 
        }
    }
    return true;
}
bool dfs(int u) // 表示当前要填写的 path 数组的位置 
{
    if(u == n)
    {
        return true;
    }
    for(int i = 0;i<n;i++)
    {
        if(!used[i])
        {
            used[i] = true;
            path[q[u]] = i;
            if(check() && dfs(u+1))
            {
                return true;
            }
            used[i] = false;
            path[q[u]] = -1;
        }
    }
    return false; 
}
int main()
{
    cin>>n;
    for(int i = 0;i<3;i++)
    {
        cin>>e[i];
    }
    for(int i = n-1,k = 0;i>=0;i--)
    {
        for(int j = 0;j<3;j++)
        {
            int t = e[j][i]-'A';
            if(!used[t])
            {
                q[k++] = t; // 存储 t
                used[t] = true;
            }
        }
    }
    // dfs 还要使用 used
    memset(used,0,sizeof(used));
    memset(path,-1,sizeof(path)); 
    dfs(0); // 从下标为 0 的位置开始搜索 
    // q[]    0 1 2 3 4 5 6 
    //        A B C D E F G 
    // path[] x x x x x x x -- u 表示下标 
    for(int i = 0;i<n;i++)
    {
        cout<<path[i]<<" ";
    }
    return 0;
}

#include<cstdio>
#include<algorithm>
using namespace std;
#define maxn 30
int a[maxn],b[maxn],c[maxn];
int num[maxn],Next[maxn],n,cnt;
char s1[maxn],s2[maxn],s3[maxn];
bool used[maxn];
bool Judge() {
for(int i=n-1,x=0;i>=0;i--) {
int A=num[a[i]],B=num[b[i]],C=num[c[i]];
if((A+B+x)%n!=C) return false;
x=(A+B+x)/n;
}
return true;
}
bool CanPrune() {//prune: 剪枝—百度翻译。
if(num[a[0]]+num[b[0]]>=n)
return true;
for(int i=n-1;i>=0;i--) {
int A=num[a[i]],B=num[b[i]],C=num[c[i]];
if(A==-1||B==-1||C==-1) continue;
if((A+B)%n!=C&&(A+B+1)%n!=C)
return true;
}
return false;
}
void Print() {
for(int i=0;i<n;i++)
printf("%d ",num[i]);
exit(0);
}
void dfs(int x) {
if(CanPrune()==true) return;
if(x==n) {
if(Judge()==true) Print();
return;
}
for(int i=n-1;i>=0;i--)
if(used[i]==false) {
num[Next[x]]=i;
used[i]=true;
dfs(x+1);
num[Next[x]]=-1;
used[i]=false;
}
return;
}
inline int id(char c) {
return c-'A';
}
void GetNext(int x) {
if(used[x]==false) {
used[x]=true;
Next[cnt++]=x;
}
return;
}
int main() {
scanf("%d",&n);
scanf("%s%s%s",s1,s2,s3);
for(int i=0;i<n;i++) {
a[i]=id(s1[i]);
b[i]=id(s2[i]);
c[i]=id(s3[i]);
num[i]=-1;
}
for(int i=n-1;i>=0;i--) {
GetNext(a[i]);
GetNext(b[i]);
GetNext(c[i]);
}
for(int i=0;i<n;i++) used[i]=false;
dfs(0);
return 0;
}
代码看不懂也可以问我qwq

一道大搜索，剪枝会比较多

#include<iostream>
#include<stdlib.h>
#include<cstring>
#include<cstdio>
using namespace std;
int n;
char a[4][28];
int num[27],shu[4][28],jin[27],zimu[27];
void dfs(int now,int wei)
{
    int i;
    if(num[shu[1][1]]>=0&&num[shu[2][1]]>=0)
     if(num[shu[1][1]]+num[shu[2][1]]>=n) //首位不能有进位
      return ;
    for(i=1;i<=n;i++) //不加此处判断9号点TLE
    {
        if(num[shu[1][i]]>=0&&num[shu[2][i]]>=0&&num[shu[3][i]]>=0)
            if((num[shu[1][i]]+num[shu[2][i]])%n!=num[shu[3][i]]&&(num[shu[1][i]]+num[shu[2][i]]+1)%n!=num[shu[3][i]])//进位最多为1
             return ;
    }
    if(now==0)
    {
        for(i=0;i<n;i++)
         cout<<num[i]<<" ";
        exit(0);
    }
    if(wei==1)//分别处理加数，和
    {
    if(num[shu[wei][now]]<0)
     for(i=0;i<n;i++)
     {
        if(zimu[i]<0)
        {
            zimu[i]=shu[wei][now];
            num[shu[wei][now]]=i;
            dfs(now,2);
            zimu[i]=-1;
            num[shu[wei][now]]=-1;
        }
     }
    else
     dfs(now,2);
    }
    if(wei==2)
    {
    if(num[shu[wei][now]]<0)
     for(i=0;i<n;i++)
     {
        if(zimu[i]<0)
        {
            zimu[i]=shu[wei][now];
            num[shu[wei][now]]=i;
            dfs(now,3);
            zimu[i]=-1;
            num[shu[wei][now]]=-1;
        }
     }
    else
     dfs(now,3);
    }
    if(wei==3)
    {
        if(num[shu[wei][now]]<0)
        {
            int temp=num[shu[1][now]]+num[shu[2][now]]+jin[now+1];//快速出和
             if(zimu[temp%n]>=0)//该和已被用
              return ;
             else
             {
                jin[now]=temp/n;
                num[shu[wei][now]]=temp%n;
                zimu[temp%n]=shu[wei][now];
                dfs(now-1,1);
                num[shu[wei][now]]=-1;
                zimu[temp%n]=-1;
             }
        }
        else
         if((num[shu[1][now]]+num[shu[2][now]]+jin[now+1])%n==num[shu[3][now]])
         {
          jin[now]=(num[shu[1][now]]+num[shu[2][now]]+jin[now+1])/n;//维护进位
          dfs(now-1,1);
         }
    }
}

int main()
{
    memset(zimu,-1,sizeof(zimu));
    memset(shu,-1,sizeof(shu));
    memset(num,-1,sizeof(num));
    int i,k;
    cin>>n;
    cin>>a[1]>>a[2]>>a[3];
    for(k=1;k<=3;k++)
     for(i=0;i<n;i++)
      shu[k][i+1]=a[k][i]-'A';
    dfs(n,1);//搜索
    return 0;
}

/include <StdAfx.h>
#include <stdlib.h>
#include <stdio.h>
#include <string>
#include <iostream>
#include <cstring>
using namespace std;

int n;//读入几进制0.1.2.3...n-1
int res[26];//保存A.B..Z代表的数字
int used[26];//保存这个对应数字是否被用，因为题目说每个字母只能代表一个数
string a,b,c;//保存加数1，加数2，和
int flag = 0;//是否已找到符合条件的唯一解//加上这个多对了2个点//
//-----最多只能7个点了，原先是从abcd..填字母，改变
char pos[26];//保存从右往左，从上往下的字母出现顺序，判断的时候也按这个顺序判断
int usedZiMu[26];//保存该字母是否已经出现

//剪枝优化函数，来判断当前的字母的数字取法是否可行
//题目就是一个可行与否的问题
int Check()
{
int i;
//看是否满足 a+b==c
for (i=n-1;i>=0;i--)
{
char a1=a[i]-'A',b1=b[i]-'A',c1=c[i]-'A';//取三个数第i位置值
if(res[a1]!=-1 && res[b1]!=-1 && res[c1]!=-1)//3个数都知道-----3个点
{
if( (res[a1]+res[b1])%n!=res[c1] &&//无进位
(res[a1]+res[b1]+1)%n!=res[c1])//有进位
return 0;
}
//加上后面这些多对了1个点
if(res[a1]!=-1 && res[b1]!=-1 && res[c1]==-1)//如果只知道其中2个
{
int sum1,sum2;//sum1无进位，sum2有进位
sum1 = (res[a1]+res[b1])%n;
sum2 = (res[a1]+res[b1]+1)%n;
if (used[sum1] && used[sum2])//可能填在c1的数都用了肯定不行
return 0;
}
if (res[a1]!=-1 && res[b1]==-1 && res[c1]!=-1)//和与一个加数知道
{
int js1,js2;//js1无进位，js2有进位
js1 = (res[c1]-res[a1]+n)%n;
js2 = (res[c1]-res[a1]-1+n)%n;
if (used[js1] && used[js2])//可能填写咋b1位置的数都被用了
return 0;
}
if (res[a1]==-1 && res[b1]!=-1 && res[c1]!=-1)//和与一个加数知道
{
int js1,js2;//js1无进位，js2有进位
js1 = (res[c1]-res[b1]+n)%n;
js2 = (res[c1]-res[b1]-1+n)%n;
if (used[js1] && used[js2])//可能填写咋b1位置的数都被用了
return 0;
}

}
return 1;
}
/*剪枝策略只这样写，数据只过3个点
int Check()
{
int i;
//看是否满足 a+b==c
for (i=0;i<=n-1;i++)
{
char a1=a[i]-'A',b1=b[i]-'A',c1=c[i]-'A';//取三个数第i位置值
if(res[a1]!=-1 && res[b1]!=-1 && res[c1]!=-1)
{
if( (res[a1]+res[b1])%n!=res[c1] &&//无进位
(res[a1]+res[b1]+1)%n!=res[c1])//有进位
return 0;
}

}
return 1;
}
*/
//严格判断当前所有字母的填数满足等式否
int OK()
{
int i;
int jinwei=0;
int jiahe;
for (i=n-1; i>=0; i--)
{
char a1=a[i]-'A',b1=b[i]-'A',c1=c[i]-'A';

jiahe = (res[a1]+res[b1]+jinwei)%n;//计算和
jinwei =( res[a1]+res[b1]+jinwei)/n;//计算进位
if (jiahe!=res[c1]) return 0;
}
if (jinwei>0) return 0;
return 1;
}
void dfs(int k)//深搜，利用系统的堆栈枚举
{
int i;
if (flag) return ;//已找到解
if (!Check()) return;//现在的方法不合理--从if (!used[i]&&Check())移到这里多了1个点共7个了
if(k==n)//找到可行解且唯一(题目得知)，输出
{
if (OK())//如果当前所有字母填数满足等式则输出
{
for(i=0; i<=n-2; i++) cout<<res[i]<<' ';
cout<<res[n-1]<<endl;
flag=1;
}
return ;
}
//在第k层，也就是第k个字母所可能取得数为0...n-1中未用值枚举
for (i=n-1; i>=0; i--)
{
//如果i还没被占用，且满足剪枝条件，则进行下层遍历
if (!used[i] )
{
used[i]=1;//i被占用
res[pos[k]]=i;//第k个字母取数字i
dfs(k+1);
used[i]=0;//i被释放，可以被其他字母占用
res[pos[k]]=-1;//第k个字母释放
}
}
return ;
}

int main()
{
int k=0,i;
//读入数据
cin>>n;
cin>>a>>b>>c;
memset(res,-1,sizeof(res));
memset(pos,-1,sizeof(pos));
//初始化
for (i=n-1; i>=0; i--)//从右向左
{
char a1=a[i]-'A',b1=b[i]-'A',c1=c[i]-'A';//全部转成对应数字下标
if (!usedZiMu[a1]) ///从上往下
{
usedZiMu[a1]=1;
pos[k++] = a1;
}
if (!usedZiMu[b1])
{
usedZiMu[b1]=1;
pos[k++] = b1;
}
if (!usedZiMu[c1])
{
usedZiMu[c1]=1;
pos[k++] = c1;
}
}
dfs(0);
return 0;
}

这个程序在洛谷上会 TLE 一个点，不过在这就过了。
我是从三个数最低位开始dfs，要是可以判断出来（即三个数中两个已经确定）就马上判断出来。
有一个地方还可以优化，就是枚举位置位上的数时，从 n-1 枚举到 0 会比从 0 到 n-1 更快（快非常多）。

#include <cstdio>
#define A(xx,yy) (f[a[xx][yy]]-1)
int f[30],a[3][30],g[30],jw[30],n,ok,boo;
char ch;
void dfs(int x,int y){
    if (ok) return;
    if (y==0){
        if (A(0,1)+A(1,1)+jw[2]==A(2,1)){
            for (int i=0; i<n; i++) printf("%d ",f[i]-1);
            ok=1;
        }
        return;
    }
    if (x<2){
        int k=1-x;
        if (!f[a[x][y]]){
            if (f[a[k][y]] && f[a[2][y]]){
                if (!g[(A(2,y)-A(k,y)-jw[y+1]+n)%n]){
                    f[a[x][y]]=(A(2,y)-A(k,y)-jw[y+1]+n)%n+1;
                    g[A(x,y)]=1;
                    dfs(x+1,y);
                    if (ok) return;
                    g[A(x,y)]=0;
                    f[a[x][y]]=0;
                }
                return;
            }
            for (int i=n-1; i>=0; i--) if (!g[i]){
                f[a[x][y]]=i+1;
                g[A(x,y)]=1;
                dfs(x+1,y);
                g[A(x,y)]=0;
                f[a[x][y]]=0;
            }
            return;
        }
        dfs(x+1,y);
        return;
    }
    if (x==2){
        if (!f[a[x][y]]){
            f[a[x][y]]=(A(0,y)+A(1,y)+jw[y+1])%n+1;
            if (!g[A(x,y)]){
                g[A(x,y)]=1;
                jw[y]=(jw[y+1]+A(0,y)+A(1,y))/n;
                dfs(0,y-1);
                g[A(x,y)]=0;
            }
            f[a[x][y]]=0;
            return;
        }
        if ((A(0,y)+A(1,y)+jw[y+1])%n==A(2,y)){
            jw[y]=(jw[y+1]+A(0,y)+A(1,y))/n;
            dfs(0,y-1);
        }
        return;
    }
}
int main(){
    scanf("%d",&n);
    for (int i=0; i<3; i++){
        while (ch<'A' || ch>'Z') ch=getchar();
        for (int j=1; j<=n; j++) a[i][j]=ch-'A',ch=getchar();
    }
    dfs(0,n);
}

这个才是正确答案

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
bool vis[100];
char b[100][100];
int a[100],c[100]; 
int n;
void print()
{
    int i;
    for (i=65;i<65+n;i++) printf("%d ",a[i]);
    printf("\n");
    return ; 
} 

bool judge1()
{
    int i;
    for (i=n;i>0;i--)
        if (a[b[i][1]]!=-1 &&  a[b[i][2]]!=-1&& a[b[i][3]]!=-1  &&
           (a[b[i][1]]+a[b[i][2]]) % n !=a[b[i][3]] &&
           (a[b[i][1]]+a[b[i][2]]+1) % n !=a[b[i][3]]) return 0;
    return 1; 
} 

bool judge2()
{
    int i,k=0;
    for (i=n;i>1;i--){
        k=a[b[i][1]]+a[b[i][2]]+k;
        if (a[b[i][3]]!=k % n) return false;
        k/=n;  
    }    
    return true; 
} 
void DFS(int m)
{
    int i;
    if (!judge1()) return ; 
    if (a[b[1][1]]+a[b[1][2]]>=n) return ;
    if (m>n){
        if(judge2()){print(); exit(0);}
        else return ;
    }
    else{
        for (i=n-1;i>=0;i--){
            if (vis[i]) {
                a[c[m]]=i;
                vis[i]=0;
                DFS(m+1);
                a[c[m]]=-1;
                vis[i]=1;    
            }     
        }
    }
}
int main()
{
    int k=1;
    bool h[100];
    memset(h,1,sizeof(h)); 
    memset(vis,1,sizeof(vis)); 
    memset(a,-1,sizeof(a)); 
    scanf("%d",&n);
    for (int j=1;j<4;j++) 
        for (int i=1;i<=n;i++) { 
           cin>>b[i][j]; 
        }
    for (int i=n;i>0;i--)
        for (int j=1;j<4;j++)
        if (h[b[i][j]]) {
                c[k++]=b[i][j];
                h[b[i][j]]=0;
            } 
    DFS(1);
   // system ("PAUSE");
    return 0;
}
 


用户信息


ZGZZN




 

题目操作

 查看 P1099
 查看本题题解
 查看本题递交记录
 

我的记录







12-17

Accepted
​
 

三个剪枝
1)首先是搜索顺序是按3排字母从右往左的出现顺序（感觉类似靶形数独），
2）其次当一列的3个数都算出来时判断是否合法即(a+b)%n==c||(a+b+1)%n==c
3）给字母赋值时从大到小，因为搜索顺序是从右到左，大的值一定靠后，否则在最高位a+b可能造成进位，但a,b,c是等长的
```
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;
int n,X[5][30],let[30],vis[30]={0},q[30]={0};
bool check(){
int i,j,tmp[5][30]={0};
for(i=1;i<=3;i++){
for(j=0;j<n;j++){
tmp[i][j]=let[X[i][j]];
}

}
int k=0,re[30]={0};
for(i=n-1;i>=0;i--){
re[i]=tmp[1][i]+tmp[2][i]+k;k=0;
k=re[i]/n;
re[i]=re[i]%n;
}
if(memcmp(re,tmp[3],sizeof(re))==0) return true;
else return false;
}
bool checkcheck(){
int i;
for(i=n-1;i>=0;i--){
int x=X[1][i],y=X[2][i],z=X[3][i];
if(let[x]!=-1&&let[y]!=-1&&let[z]!=-1){
int flag=0;
if((let[x]+let[y])%n==let[z]) flag=1;
if((let[x]+let[y]+1)%n==let[z]) flag=1;
if(!flag) return false;
}
}
return true;
}
void dfs(int step){
int i;
if(step==n){
if(check()){
for(i=0;i<n-1;i++){
printf("%d ",let[i]);
}
printf("%d",let[n-1]);
exit(0);
}
}
if(!checkcheck()) return; //**剪枝2）**
for(i=n-1;i>=0;i--){ //**剪枝3）**
if(!vis[i]){
let[q[step]]=i;
vis[i]=1;
dfs(step+1);
vis[i]=0;
let[q[step]]=-1;
}
}
}
int main(){
freopen("in.txt","r",stdin);
int i,j,book[30]={0};
char ch;
scanf("%d",&n);
ch=getchar();
for(i=1;i<=3;i++){
for(j=0;j<n;j++){
scanf("%c",&ch);
X[i][j]=ch-'A';
}
ch=getchar();
}
int top=0;
for(i=n-1;i>=0;i--){
int x=X[1][i],y=X[2][i],z=X[3][i];
if(!book[x]){
q[top++]=x;book[x]=1;
}
if(!book[y]){
q[top++]=y;book[y]=1;
}
if(!book[z]){
q[top++]=z;book[z]=1;
}
} //**剪枝1）**
memset(let,-1,sizeof(let));
dfs(0);
return 0;
}
```
100ms

测试数据 #0: Accepted, time = 0 ms, mem = 576 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 576 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 576 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 580 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 576 KiB, score = 10
测试数据 #5: Accepted, time = 15 ms, mem = 576 KiB, score = 10
测试数据 #6: Accepted, time = 0 ms, mem = 576 KiB, score = 10
测试数据 #7: Accepted, time = 0 ms, mem = 576 KiB, score = 10
测试数据 #8: Accepted, time = 15 ms, mem = 576 KiB, score = 10
测试数据 #9: Accepted, time = 0 ms, mem = 576 KiB, score = 10
Accepted, time = 30 ms, mem = 580 KiB, score = 100
五个剪枝成就未来

各种奇迹淫巧+cheat总算A了这个神题。。
PS：倒着枚举待放数字快纯属因为两个大数据点为0 1 2 3 4 ..
代码，太丑就不贴了。。

测试数据 #0: TimeLimitExceeded, time = 1203 ms, mem = 580 KiB, score = 0
测试数据 #1: Accepted, time = 0 ms, mem = 576 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 576 KiB, score = 10
测试数据 #3: Accepted, time = 156 ms, mem = 572 KiB, score = 10
测试数据 #4: TimeLimitExceeded, time = 1203 ms, mem = 576 KiB, score = 0
测试数据 #5: TimeLimitExceeded, time = 1203 ms, mem = 576 KiB, score = 0
测试数据 #6: TimeLimitExceeded, time = 1187 ms, mem = 576 KiB, score = 0
测试数据 #7: TimeLimitExceeded, time = 1203 ms, mem = 572 KiB, score = 0
测试数据 #8: TimeLimitExceeded, time = 1015 ms, mem = 576 KiB, score = 0
测试数据 #9: Accepted, time = 0 ms, mem = 576 KiB, score = 10
TimeLimitExceeded, time = 7170 ms, mem = 580 KiB, score = 40
有点懵逼了。

让你的搜索顺序顺应你的剪枝，将剪枝最优化。
var a:array['A'..'Z'] of longint;
i:char;
B:ARRAY[1..100] OF CHAR;
n,j,k,l:longint;
S1,S2,S3:STRING;
P:ARRAY[0..30] OF BOOLEAN;
PP:ARRAY['A'..'Z'] OF BOOLEAN;
PROCEDURE FIND(Y,X:LONGINT);
VAR R,O:LONGINT;
PPP:BOOLEAN;
PROCEDURE SUAN;
VAR R,O:LONGINT;
I:CHAR;
X,Y,Z:INT64;
L1,L2,L3:STRING;
BEGIN
L1:=S1; L2:=S2; L3:=S3; O:=0;
FOR R:=N DOWNTO 1 DO
BEGIN
X:=A[S1[R]];
Y:=A[S2[R]];
X:=X+Y+O;
O:=0;
IF X>=N THEN BEGIN O:=1; X:=X-N; END;
IF X<>A[S3[R]] THEN EXIT;
END;
FOR I:='A' TO CHR(64+N) DO
WRITE(A[I],' ');
HALT;
END;
BEGIN
IF ( ( (A[S1[1]]>A[S3[1]]) OR (A[S2[1]]>A[S3[1]]) ) AND(A[S3[1]]<>-1) )OR(A[S2[1]]+A[S1[1]]>=N)OR(A[S1[1]]=N-1)OR(A[S2[1]]=N-1)
THEN EXIT;
IF (A[S1[1]]<>-1)AND(A[S2[1]]<>-1)AND(A[S3[1]]<>-1)AND(A[S1[1]]+A[S2[1]]<>A[S3[1]])AND(A[S1[1]]+A[S2[1]]<>A[S3[1]]-1) THEN EXIT;
FOR R:=2 TO N DO
IF (A[S1[R]]<>-1)AND(A[S2[R]]<>-1)AND(A[S3[R]]<>-1) THEN
IF (A[S1[R]]+A[S2[R]]<>A[S3[R]]-1)AND(A[S1[R]]+A[S2[R]]<>A[S3[R]])AND(A[S1[R]]+A[S2[R]]<>A[S3[R]]+N)AND(A[S1[R]]+A[S2[R]]<>A[S3[R]]+N-1) THEN EXIT;
IF X=N+1 THEN BEGIN SUAN; EXIT; END;
FOR R:=N-1 DOWNTO 0 DO
IF P[R] THEN
BEGIN
A[CHR(Y)]:=R;
P[R]:=FALSE;
INC(K);
FIND(ORD(B[K]),X+1);
DEC(K);
P[R]:=TRUE;
A[CHR(Y)]:=-1;
END;
END;
begin
FILLCHAR(PP,SIZEOF(PP),TRUE);
FILLCHAR(P,SIZEOF(P),TRUE);
READLN(N);
READLN(S1);
READLN(S2);
READLN(S3); K:=0;
FOR J:=N DOWNTO 1 DO
BEGIN
IF PP[S1[J]] THEN BEGIN
INC(K);
B[K]:=S1[J]; PP[S1[J]]:=FALSE;
END;
IF PP[S2[J]] THEN BEGIN
INC(K);
B[K]:=S2[J]; PP[S2[J]]:=FALSE;
END;
IF PP[S3[J]] THEN BEGIN
INC(K);
B[K]:=S3[J]; PP[S3[J]]:=FALSE;
END;
END; K:=1;
FOR I:='A' TO CHR(64+N) DO
A[I]:=-1;
PP[S1[N]]:=FALSE;
FIND(ORD(B[K]),1);
end.

我表示不愿意挖坟，但是为了以后来刷这道ws的搜索题的童鞋能更快地过掉，我再总结一下这题的几个强力剪枝吧（也是本人所用的剪枝）：
1、从算式的右侧到左侧、从上到下（从下到上会更快），一列一列地枚举待搜索的字符；
2、枚举未知字符对应的数字时要从大到小搜；
3、枚举出任意一个未知字符对应的数字之后，判断一下这一列数的合法性——
比如说对于某一列数：
　？1
＋？A <-显然这里A除了取3或4之外没有其他可能
＝？5
4、同上，应该也判断一下其他列的合法性
比如：
　？9
＋？7
＝？A <-假设刚刚确定了7，那么这里A只可能取6或7，如果这两个数字都已经被其他字符选用了，那也是无解的

第3、4个剪枝很强大，因为本人的程序在没加3、4优化时其他点0ms，第9个点（此乃神点）超时，百思不得其解……加了之后，30ms通过……
当然，本人的程序是一列一列从上到下搜的，很多人总结出如果从下到上搜会有奇效，童鞋们可自己试试……

#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
bool u[26];
char e[3][26];
double a[26][26],b[26][26],c[26],t,x[26];
int i,j,k,n,s;
using namespace std;
main()
{
cin>>n;
gets(e[0]);
gets(e[0]);
gets(e[1]);
gets(e[2]);
for(i=0;i<n;i++)
{
b[i][i]=1;
a[i][e[0][i]-'A']++;
a[i][e[1][i]-'A']++;
a[i][e[2][i]-'A']--;
}
for(i=0;i<n;i++)
{
for(j=i+1,k=i,t=a[i][i];j<n;j++)
if(fabs(a[j][i])>fabs(t))
{
t=a[j][i];
k=j;
}
if(k!=i)
for(j=0;j<n;j++)
{
t=a[i][j];
a[i][j]=a[k][j];
a[k][j]=t;
t=b[i][j];
b[i][j]=b[k][j];
b[k][j]=t;
}
if(fabs(a[i][i]-1)>1e-6)
for(t=a[i][i],k=0;k<n;k++)
{
a[i][k]/=t;
b[i][k]/=t;
}
for(j=i+1;j<n;j++)
if(fabs(a[j][i])>1e-6)
for(k=0,t=a[j][i];k<n;k++)
{
a[j][k]-=a[i][k]*t;
b[j][k]-=b[i][k]*t;
}
}
for(i=n-1;i>=0;i--)
for(j=i-1;j>=0;j--)
if(fabs(a[j][i])>1e-6)
for(k=0,t=a[j][i],a[j][i]=0;k<n;k++)
b[j][k]-=t*b[i][k];
do
{
memset(c,0,sizeof(c));
memset(u,0,sizeof(u));
memset(x,0,sizeof(x));
for(i=0;i<n-1;i++)
if(s&1<<i)
{
c[i]--;
c[i+1]+=n;
}
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
if(fabs(b[i][j])>1e-6&&fabs(c[j])>1e-6)
x[i]+=b[i][j]*c[j];
if(fabs(x[i]-floor(x[i]+0.5))>1e-6||x[i]<-1e-6||x[i]-n+1>1e-6||u[int(x[i]+0.1)])
break;
u[int(x[i]+0.1)]=1;
}
}while(s++,i<n);
for(i=0;i<n;i++)
cout<<int(x[i]+0.1)<<' ';
}

var
a:array['A'..'Z']of integer;
b:array[1..26,1..3]of char;
p:array['A'..'Z']of boolean;
n,i,j,m:integer;
r:array[1..26]of char;
c:array[0..26]of boolean;
procedure print;
var
i:integer;
begin
for i:=1 to n-1 do write(a[chr(64+i)],' ');
writeln(a[chr(n+64)]);
halt;
end;

function f:boolean;
var
i:integer;
begin
for i:=n downto 1 do
if (a[b[i,1]]<>-1)and(a[b[i,2]]<>-1)and(a[b[i,3]]<>-1)
and((a[b[i,1]]+a[b[i,2]])mod n<>a[b[i,3]])
and((a[b[i,1]]+a[b[i,2]]+1)mod n<>a[b[i,3]])then
begin
f:=true;
exit;
end;
f:=false;
end;

function pd:boolean;
var
i,j,z:integer;
begin
z:=0;
for i:=n downto 2 do
begin
z:=z+a[b[i,1]]+a[b[i,2]];
if z mod n<>a[b[i,3]]then begin pd:=false;exit;end;
z:=z div n;
end;
z:=z+a[b[1,1]]+a[b[1,2]];
if z<>a[b[1,3]]then begin pd:=false;exit;end;
end;

procedure so(m:integer);
var
i:integer;
begin
if f then exit;
if a[b[1,1]]+a[b[1,2]]>=n then exit;
if m>n then begin
if pd then print;
exit;
end;
for i:=n-1 downto 0 do
if c[i]then begin
a[r[m]]:=i;
c[i]:=false;
so(m+1);
a[r[m]]:=-1;
c[i]:=true;
end;
end;

begin
m:=0;
readln(n);
fillchar(c,sizeof(c),true);
fillchar(p,sizeof(p),true);
for i:=1 to n do
a[chr(64+i)]:=-1;
for j:=1 to 3 do
begin
for i:=1 to n do
read(b[i,j]);
readln;
end;
for i:=n downto 1 do
for j:=1 to 3 do
if p[b[i,j]] then
begin
inc(m);
r[m]:=b[i,j];
p[b[i,j]]:=false;
end;
so(1);
end.

本机过了在这RE时什么情况QAQ

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
bool vis[100];
char b[100][100];
int a[100],c[100];
int n;
void print()
{
int i;
for (i=65;i<65+n;i++) printf("%d ",a[i]);
printf("\n");
return ;
}

bool judge1()
{
int i;
for (i=n;i>0;i--)
if (a[b[i][1]]!=-1 && a[b[i][2]]!=-1&& a[b[i][3]]!=-1 &&
(a[b[i][1]]+a[b[i][2]]) % n !=a[b[i][3]] &&
(a[b[i][1]]+a[b[i][2]]+1) % n !=a[b[i][3]]) return 0;
return 1;
}

bool judge2()
{
int i,k=0;
for (i=n;i>1;i--){
k=a[b[i][1]]+a[b[i][2]]+k;
if (a[b[i][3]]!=k % n) return false;
k/=n;

}

return true;
}
void DFS(int m)
{
int i;
if (!judge1()) return ;
if (a[b[1][1]]+a[b[1][2]]>=n) return ;
if (m>n){
if(judge2()){print(); exit(0);}
else return ;
}
else{
for (i=n-1;i>=0;i--){
if (vis[i]) {
a[c[m]]=i;
vis[i]=0;
DFS(m+1);
a[c[m]]=-1;
vis[i]=1;

}

}
}
}
int main()
{
int k=1;
bool h[100];
memset(h,1,sizeof(h));
memset(vis,1,sizeof(vis));
memset(a,-1,sizeof(a));
scanf("%d",&n);
for (int j=1;j<4;j++)
for (int i=1;i<=n;i++) {
cin>>b[i][j];
}
for (int i=n;i>0;i--)
for (int j=1;j<4;j++)
if (h[b[i][j]]) {
c[k++]=b[i][j];
h[b[i][j]]=0;
}
DFS(1);
// system ("PAUSE");
return 0;
}