139 条题解
-
5
PowderHan LV 10 @ 2017-05-08 07:53:25
抄的算法竞赛宝典的题解
/* 可以采用一些比较高级的算法，比如解方程之类的，不过通常的 算法是搜索，这个程序也采用搜索的方法 搜索思路： 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; } -
1
//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; } -
1
Hammer_cwz_77 LV 8 @ 2017-08-24 11:20:02
#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;
} -
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 -
0
一道大搜索，剪枝会比较多
#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; } -
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;
} -
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); } -
0
#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 -
0
三个剪枝
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
测试数据 #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
五个剪枝成就未来 -
0
测试数据 #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
有点懵逼了。 -
0
LN_handsome LV 9 @ 2015-07-17 15:23:15
让你的搜索顺序顺应你的剪枝，将剪枝最优化。
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. -
0
longyuepeng LV 10 @ 2015-04-14 16:50:52
我表示不愿意挖坟，但是为了以后来刷这道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通过……
当然，本人的程序是一列一列从上到下搜的，很多人总结出如果从下到上搜会有奇效，童鞋们可自己试试…… -
0
#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)<<' ';
} -
0
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. -
0
#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;
}-
克莉斯丁 @ 2016-09-23 16:57:24
真是帮了大忙啊，我看自己的代码怎么看都找不出错但是就是错的，之后看到了你的程序，发现我们的思路居然特别像！！！！比网上的那些题解都容易看懂！！！之后我经过不断的努力终于发现了自己的错误！！！好开心！！！顺便说一下这是我的第一道自己考虑思路的搜索题，感觉以后会在搜索上自信一点了。。。。。
-
PowderHan
LV 10
@ 2017-05-08 07:53:25
