首页 > 代码库 > DFS——jzyzoj1187:虫食算
DFS——jzyzoj1187:虫食算
卡了两天的虫食算，调了一天的错误代码。给出题面：
没错题目很长，不过实际上就是给出三个n位数的字符串，每个大写字母都代表唯一的数字，让第一个字符串与第二个字符串相加，使得前两个字符串构成的N位数字相加后等于第三个字符串所代表的N位数字。按照字典序输出各个大写字母对应的值。
暴力的方法非常简单。用简单的dfs+回溯搜索每一个大写字母出现的值然后相加（注意进制以及进位），如果最终结果符合条件的话退出即可。
代码：
1 //暴力 2 #include <iostream> 3 #include <cstdio> 4 #include <algorithm> 5 #include <string> 6 #include <cstring> 7 using namespace std; 8 int num[30],n; 9 char ch[4][30]; 10 bool f[30],flag=false; 11 void dfs(int p) 12 { 13 if (p==n) 14 { 15 int sum=0,n1,n2,n3; 16 for (int i=n-1;i>=0;i--) 17 { 18 n1=num[ch[1][i]-‘A‘]; 19 n2=num[ch[2][i]-‘A‘]; 20 n3=num[ch[3][i]-‘A‘]; 21 if ((n1+n2+sum)%n!=n3) return; 22 sum=(n1+n2+sum)/n; 23 } 24 flag=true; 25 } 26 else 27 { 28 for (int i=n-1;i>=0;i--) 29 { 30 if (!f[i]) 31 { 32 f[i]=true; 33 num[p]=i; 34 dfs(p+1); 35 if (flag) 36 { 37 return; 38 } 39 f[i]=false; 40 } 41 } 42 } 43 } 44 int main() 45 { 46 freopen("add.in","r",stdin); 47 freopen("add.out","w",stdout); 48 memset(f,false,sizeof(f)); 49 scanf("%d",&n); 50 scanf("%s",&ch[1]); 51 scanf("%s",&ch[2]); 52 scanf("%s",&ch[3]); 53 dfs(0); 54 for (int i=0; i<n; i++) 55 { 56 printf("%d ",num[i]); 57 } 58 printf("\n"); 59 return 0; 60 }
但是数据范围是26....如果极限数据的话，26^26.....而且剪枝似乎很难...果断放弃搜索字母的方法
所以还是后序遍历。。。
从每个字符串的尾部开始枚举，如果1或2字符串的字符还没有出现过，就进行枚举，如果全部出现过的话，就进行特判，这样的算法看上去也是o(n^n)，但是仔细想想：从尾字母开始，每个字符串的长度都是n，所以一定会有某个大写字母重复出现的情况，而且事实上这种情况会有很多，所以整体的时间复杂度就特别低。可以将90%的数据在1S之内得出答案。
代码：
1 //后序遍历(AC) 2 #include<iostream> 3 #include<cstdio> 4 #include<string> 5 #include<cstring> 6 #include<algorithm> 7 #include<cmath> 8 int n,num[30],sum=0; 9 char ch1[30],ch2[30],ch3[30]; 10 bool flag[30],flagnum[30],f=false; 11 using namespace std; 12 void dfs(int p) 13 { 14 if (p==-1) 15 { 16 f=true; return; 17 } 18 if (flag[ch1[p]-‘A‘]&&flag[ch2[p]-‘A‘]) 19 { 20 int temp=sum; 21 int n1=num[ch1[p]-‘A‘],n2=num[ch2[p]-‘A‘],n3; 22 if (flag[ch3[p]-‘A‘]) 23 { 24 n3=num[ch3[p]-‘A‘]; 25 if ((n1+n2+sum)%n!=n3) return; 26 sum=(n1+n2+sum)/n; 27 dfs(p-1); 28 if (f) return; 29 sum=temp; 30 } 31 else 32 { 33 n3=(n1+n2+sum)%n; 34 sum=(n1+n2+sum)/n; 35 if (flagnum[n3]) 36 { 37 sum=temp; 38 return; 39 } 40 flag[ch3[p]-‘A‘]=true; 41 flagnum[n3]=true; 42 num[ch3[p]-‘A‘]=n3; 43 dfs(p-1); 44 if (f) return; 45 flag[ch3[p]-‘A‘]=false; 46 flagnum[n3]=false; 47 num[ch3[p]-‘A‘]=-1; 48 sum=temp; 49 } 50 } 51 else if (flag[ch1[p]-‘A‘]&&!flag[ch2[p]-‘A‘]) 52 { 53 else 54 { 55 for (int i=n-1;i>=0;i--) 56 { 57 if (!flagnum[i]) 58 { 59 flagnum[i]=true; 60 num[ch2[p]-‘A‘]=i; 61 flag[ch2[p]-‘A‘]=true; 62 dfs(p); 63 if (f) return; 64 flagnum[i]=false; 65 num[ch2[p]-‘A‘]=-1; 66 flag[ch2[p]-‘A‘]=false; 67 } 68 } 69 } 70 } 71 else if (flag[ch2[p]-‘A‘]&&!flag[ch1[p]-‘A‘]) 72 { 73 for (int i=n-1;i>=0;i--) 74 { 75 if (!flagnum[i]) 76 { 77 flagnum[i]=true; 78 num[ch1[p]-‘A‘]=i; 79 flag[ch1[p]-‘A‘]=true; 80 dfs(p); 81 if (f) return; 82 flagnum[i]=false; 83 num[ch1[p]-‘A‘]=-1; 84 flag[ch1[p]-‘A‘]=false; 85 } 86 } 87 } 88 else 89 { 90 for (int i=n-1;i>=0;i--) 91 if (!flagnum[i]) 92 { 93 flagnum[i]=flag[ch1[p]-‘A‘]=true; 94 num[ch1[p]-‘A‘]=i; 95 dfs(p); 96 if (f) return; 97 num[ch1[p]-‘A‘]=-1; 98 flagnum[i]=flag[ch1[p]-‘A‘]=false; 99 } 100 } 101 } 102 int main() 103 { 104 //freopen("add.in","r",stdin); 105 //freopen("add.out","w",stdout); 106 memset(flag,false,sizeof(flag)); 107 memset(flagnum,false,sizeof(flagnum)); 108 memset(num,-1,sizeof(num)); 109 scanf("%d",&n); 110 scanf("%s",&ch1); 111 scanf("%s",&ch2); 112 scanf("%s",&ch3); 113 dfs(n-1); 114 for (int i=0;i<n;i++) 115 printf("%d ",num[i]); 116 printf("\n"); 117 return 0; 118 }
但是其实这个也算是暴力的方法。
下面不给出代码了（懒得敲），只有具体的思路。
1.只要在某个地方，如果三个字符中有两个大写字母的值已经出现，那么另外一个字母的值是一定可以知道的。
2.当三个字符中有一个字符代表0，且进位也是0时可以进行判断，如果剩下的两个字符不相等的话，无论怎么枚举都不可能得到正解。
3.如果三个字符中存在2个相等，如果进位是0，剩下的一个必定是0。如果进位是1，剩下的一个必定是n-1。
大概还有别的剪枝条件....
但是只需要这三个剪枝条件就能把程序的运行时间降到很短。
这样的话大概可以对本题进行延伸：
数据不一定有解，如果无解的话，输出-1。
DFS——jzyzoj1187:虫食算
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。