P1092 虫食算
算法：爆搜+剪枝
启发:
1.代码结构要清晰，便于调试
80分代码
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int MAXN=32;
int n,exp[4][MAXN],val[MAXN],flag,used[MAXN];
void func(int &x,int &y,int &z,int bft,int idx);
void dfs(int x/*Ö´ÐеÚxλ*/,int y/*Óнøλ*/);
void func(int &x,int &y,int &z,int bft,int idx){
if(flag){
return;
}
if(x!=-1&&y!=-1&&z!=-1){
// printf("x=%d y=%d z=%d
",x,y,z);
if((x+y+bft)%n==z){
dfs(idx+1,(x+y+bft)/n);
}
return;
}
if(x==-1){
for(x=0;x<n;x++){
if(!used[x]){
used[x]=1;
func(x,y,z,bft,idx);
used[x]=0;
}
}
x=-1;
}else if(y==-1){
for(y=0;y<n;y++){
if(!used[y]){
used[y]=1;
func(x,y,z,bft,idx);
used[y]=0;
}
}
y=-1;
}else{
for(z=0;z<n;z++){
if(!used[z]){
used[z]=1;
func(x,y,z,bft,idx);
used[z]=0;
}
}
z=-1;
}
}
void dfs(int x/*Ö´ÐеÚxλ*/,int y/*Óнøλ*/){
if(flag){
return;
}
// printf("x=%d y=%d
",x,y);
// for(int i=0;i<n;i++){
// printf("val[%c]=%d
",'A'+i,val[i]);
// }
if(x==n+1){
for(int i=0;i<n;i++){
printf("%d ",val[i]);
}
flag=1;
return;
}
func(val[exp[1][x]],val[exp[2][x]],val[exp[3][x]],y,x);
}
int main(){
scanf("%d",&n);
memset(val,-1,sizeof(val));
for(int i=1;i<=3;i++){
char str[MAXN];
scanf("%s",str);
for(int j=1;j<=n;j++){
exp[i][j]=str[n-j]-'A';
}
}
dfs(1,0);
return 0;
}
这段代码运用了太多递归嵌套，过于复杂
2.剪枝
70分代码
// luogu-judger-enable-o2
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int MAXN=32;
int n,exp[4][MAXN],val[MAXN],flag,used[MAXN];
inline int abs(int x){ return x>0?x:-x; }
inline bool check(){
for(int i=1;i<=n;i++){
int ii=val[exp[1][i]],jj=val[exp[2][i]],kk=val[exp[3][i]];
if(-1==ii||-1==jj||-1==kk){
continue;
}
if((ii+jj)%n!=kk&&(ii+jj+1)%n!=kk){
return true;
}
}
return false;
}
inline bool okay(){
int ii=0;
for(int i=1;i<=n;i++){
int jj=val[exp[1][i]],kk=val[exp[2][i]],ll=val[exp[3][i]];
if((jj+kk+ii)%n!=ll){
return false;
}
ii=(jj+kk+ii)/n;
}
if(ii){
return false;
}
for(int i=0;i<n;i++){
printf("%d ",val[i]);
}
return true;
}
void dfs(int x){
if(flag||check()){
return;
}
if(x>=n){
flag=okay();
return;
}
for(int i=0;i<n;i++){
if(!used[i]){
used[i]=1;
val[x]=i;
dfs(x+1);
used[i]=0;
val[x]=-1;
}
}
}
int main(){
scanf("%d",&n);
memset(val,-1,sizeof(val));
for(int i=1;i<=3;i++){
char str[MAXN];
scanf("%s",str);
for(int j=1;j<=n;j++){
exp[i][j]=str[n-j]-'A';
}
}
dfs(0);
return 0;
}
增加了模块化，按照搜索基本架构写，虽然损了一些效率，但代码更加清晰可读
80分代码
// luogu-judger-enable-o2
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int MAXN=32;
int n,exp[4][MAXN],val[MAXN],flag,used[MAXN],pos[MAXN],vis[MAXN],top;
inline bool check(){
for(int i=1;i<=n;i++){
int ii=val[exp[1][i]],jj=val[exp[2][i]],kk=val[exp[3][i]];
if(-1!=ii&&-1!=jj&&-1!=kk){
if((ii+jj)%n!=kk&&(ii+jj+1)%n!=kk){
return true;
}
}else if(-1!=ii&&-1!=jj&&-1==kk){
if(used[(ii+jj)%n]&&used[(ii+jj+1)%n]){
return true;
}
}else if(-1!=ii&&-1==jj&&-1!=kk){
if(used[(kk+n-ii)%n]&&used[(kk+n-ii-1)%n]){
return true;
}
}else if(-1==ii&&-1!=jj&&-1!=kk){
if(used[(kk+n-jj)%n]&&used[(kk+n-jj-1)%n]){
return true;
}
}
}
return false;
}
inline bool okay(){
int ii=0;
// for(int i=1;i<=3;i++){
// if(i==2){
// printf("+");
// }else if(i==1)
// printf(" ");
// if(i==3){
// puts("--------------------");
// printf(" ");
// }
// for(int j=n;j>=1;j--){
// printf("%d",val[exp[i][j]]);
// }
// puts("");
// }
// puts("");
for(int i=1;i<=n;i++){
int jj=val[exp[1][i]],kk=val[exp[2][i]],ll=val[exp[3][i]];
if((jj+kk+ii)%n!=ll){
return false;
}
ii=(jj+kk+ii)/n;
}
if(ii){
return false;
}
for(int i=0;i<n;i++){
printf("%d ",val[i]);
}
return true;
}
void dfs(int x){
if(flag||check()){
return;
}
if(x>=n){
flag=okay();
return;
}
for(int i=0;i<n;i++){
if(!used[i]){
used[i]=1;
val[pos[x]]=i;
dfs(x+1);
used[i]=0;
val[pos[x]]=-1;
}
}
}
int main(){
// freopen("1.out","w",stdout);
scanf("%d",&n);
memset(val,-1,sizeof(val));
for(int i=1;i<=3;i++){
char str[MAXN];
scanf("%s",str);
for(int j=1;j<=n;j++){
exp[i][j]=str[n-j]-'A';
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=3;j++){
if(!vis[exp[j][i]]){
vis[exp[j][i]]=1;
pos[top++]=exp[j][i];
}
}
}
dfs(0);
return 0;
}
对搜索对象进行了排序，可以有效降低复杂度
100分代码
// luogu-judger-enable-o2
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int MAXN=32;
int n,exp[4][MAXN],val[MAXN],flag,used[MAXN],pos[MAXN],vis[MAXN],top;
inline bool check(){
for(int i=1;i<=n;i++){
int ii=val[exp[1][i]],jj=val[exp[2][i]],kk=val[exp[3][i]];
if(-1!=ii&&-1!=jj&&-1!=kk){
if((ii+jj)%n!=kk&&(ii+jj+1)%n!=kk){
return true;
}
}else if(-1!=ii&&-1!=jj&&-1==kk){
if(used[(ii+jj)%n]&&used[(ii+jj+1)%n]){
return true;
}
}else if(-1!=ii&&-1==jj&&-1!=kk){
if(used[(kk+n-ii)%n]&&used[(kk+n-ii-1)%n]){
return true;
}
}else if(-1==ii&&-1!=jj&&-1!=kk){
if(used[(kk+n-jj)%n]&&used[(kk+n-jj-1)%n]){
return true;
}
}
}
int ii=val[exp[1][n]],jj=val[exp[2][n]],kk=val[exp[3][n]];
if(-1!=ii&&-1!=jj){
if(ii+jj>=n){
return true;
}
}
if(-1==ii&&-1!=jj&&-1!=kk){
if(kk<jj){
return true;
}
}
if(-1!=ii&&-1==jj&&-1!=kk){
if(kk<ii){
return true;
}
}
return false;
}
inline bool okay(){
int ii=0;
// for(int i=1;i<=3;i++){
// if(i==2){
// printf("+");
// }else if(i==1)
// printf(" ");
// if(i==3){
// puts("--------------------");
// printf(" ");
// }
// for(int j=n;j>=1;j--){
// printf("%d",val[exp[i][j]]);
// }
// puts("");
// }
// puts("");
for(int i=1;i<=n;i++){
int jj=val[exp[1][i]],kk=val[exp[2][i]],ll=val[exp[3][i]];
if((jj+kk+ii)%n!=ll){
return false;
}
ii=(jj+kk+ii)/n;
}
if(ii){
return false;
}
for(int i=0;i<n;i++){
printf("%d ",val[i]);
}
return true;
}
void dfs(int x){
if(flag||check()){
return;
}
if(x>=n){
flag=okay();
return;
}
for(int i=n-1;i>=0;i--){
if(!used[i]){
used[i]=1;
val[pos[x]]=i;
dfs(x+1);
used[i]=0;
val[pos[x]]=-1;
}
}
}
int main(){
// freopen("1.out","w",stdout);
scanf("%d",&n);
memset(val,-1,sizeof(val));
for(int i=1;i<=3;i++){
char str[MAXN];
scanf("%s",str);
for(int j=1;j<=n;j++){
exp[i][j]=str[n-j]-'A';
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=3;j++){
if(!vis[exp[j][i]]){
vis[exp[j][i]]=1;
pos[top++]=exp[j][i];
}
}
}
dfs(0);
return 0;
}
将最先搜到的对象从大到小枚举，可以辅助剪枝，因为当最后的位数太小时不容易产生进位，不会冲突，从而剪枝力度就小了