首页 > 代码库 > noip 虫食算 (搜索)
noip 虫食算 (搜索)
描述
所谓虫食算，就是原先的算式中有一部分被虫子啃掉了，需要我们根据剩下的数字来判定被啃掉的字母。来看一个简单的例子：
43#9865#045
+ 8468#6633
= 44445506678
其中#号代表被虫子啃掉的数字。根据算式，我们很容易判断：第一行的两个数字分别是5和3，第二行的数字是5。
现在，我们对问题做两个限制：
首先，我们只考虑加法的虫食算。这里的加法是N进制加法，算式中三个数都有N位，允许有前导的0。
其次，虫子把所有的数都啃光了，我们只知道哪些数字是相同的，我们将相同的数字用相同的字母表示，不同的数字用不同的字母表示。如果这个算式是N进制的，我们就取英文字母表午的前N个大写字母来表示这个算式中的0到N-1这N个不同的数字：但是这N个字母并不一定顺序地代表0到N-1)。输入数据保证N个字母分别至少出现一次。
BADC
+ CRDA
= DCCC
上面的算式是一个4进制的算式。很显然，我们只要让ABCD分别代表0123，便可以让这个式子成立了。你的任务是，对于给定的N进制加法算式，求出N个不同的字母分别代表的数字，使得该加法算式成立。输入数据保证有且仅有一组解
格式
输入格式
输入包含4行。第一行有一个正整数N(N<=26)，后面的3行每行有一个由大写字母组成的字符串，分别代表两个加数以及和。这3个字符串左右两端都没有空格，从高位到低位，并且恰好有N位。
输出格式
输出包含一行。在这一行中，应当包含唯一的那组解。解是这样表示的：输出N个数字，分别表示A，B，C……所代表的数字，相邻的两个数字用一个空格隔开，不能有多余的空格。
样例1
样例输入1
5ABCEDBDACEEBBAA样例输出1
1 0 3 4 2限制
每个测试点1s
来源
NOIp 2004
很明显 我们可以想到枚举全排列 来挨个试解是否成立
但是 O(26!) 的复杂度远远无法承受
总的来说这还是搜索
我们按照计算习惯 从有到左 从上到下 进行枚举
枚举 每个字母可能代表什么数字
和全排列的思路差不多 但是需要剪枝
这时候剪枝就尤为重要了
剪枝在代码中的check函数中
判断如下
如果当前 a,b,s,都知道了
判断是否满足进位条件
若只有两的数知道
知道a,b
如果 c=(a+b)%n,c1=(a+b+1)%n
两种情况中的c和c1都用过了 则不成立
知道a,c
如果 b=(c-a+n)%n,b1=(c-a-1+n)%n
b 和 b1都使用过 不成立
知道 b,c 同理
1 #include<cstdio> 2 #include<iostream> 3 #define MAXN 30 4 5 using namespace std; 6 7 char a[MAXN],b[MAXN],s[MAXN]; 8 9 int n,k; 10 11 int POS[MAXN],rep[MAXN]; 12 13 bool used[MAXN],flag,usednum[MAXN]; 14 15 inline bool judge() { 16 int next=0; 17 for(int i=n-1;i>=0;i--) { 18 int ai=a[i]-‘A‘; 19 int bi=b[i]-‘A‘; 20 int si=s[i]-‘A‘; 21 int sum=(rep[ai]+rep[bi]+next)%n; 22 next=(rep[ai]+rep[bi]+next)/n; 23 if(sum!=rep[si]) return false; 24 } 25 if(next>0) return false; 26 return true; 27 } 28 29 30 inline bool check() { 31 for(int i=n-1;i>=0;i--) { 32 int ai=a[i]-‘A‘; 33 int bi=b[i]-‘A‘; 34 int si=s[i]-‘A‘; 35 if(rep[ai]!=-1 && rep[bi]!=-1 && rep[si]!=-1) {// MDZZ 漏了一个负号 我WA了10遍 36 if( (rep[ai]+rep[bi])%n!=rep[si] && 37 (rep[ai]+rep[bi]+1)%n!=rep[si]) 38 return false; 39 } 40 if(rep[ai]!=-1 && rep[bi]!=-1 && rep[si]==-1) { 41 int ss1,ss2; 42 ss1=(rep[ai]+rep[bi])%n; 43 ss2=(rep[ai]+rep[bi]+1)%n; 44 if(used[ss1] && used[ss2]) return false; 45 } 46 if(rep[ai]!=-1 && rep[bi]==-1 && rep[si]!=-1) { 47 int ss1,ss2; 48 ss1=(rep[si]-rep[ai]+n)%n; 49 ss2=(rep[si]-rep[ai]-1+n)%n; 50 if(used[ss1] && used[ss2]) return false; 51 } 52 if(rep[ai]==-1 && rep[bi]!=-1 && rep[si]!=-1) { 53 int ss1,ss2; 54 ss1=(rep[si]-rep[bi]+n)%n; 55 ss2=(rep[si]-rep[bi]-1+n)%n; 56 if(used[ss1] && used[ss2]) return false; 57 } 58 } 59 return true; 60 } 61 62 inline void dfs(int pos) { 63 if(flag) return; 64 if(!check()) return; 65 if(pos==n) { 66 if(judge()) { 67 for(int i=0;i<n-1;i++) 68 printf("%d ",rep[i]); 69 printf("%d\n",rep[n-1]); 70 flag=true; 71 } 72 return; 73 } 74 for(int i=n-1;i>=0;i--) { 75 if(!used[i]) { 76 used[i]=true; 77 rep[POS[pos]]=i; 78 dfs(pos+1); 79 used[i]=false; 80 rep[POS[pos]]=-1; 81 } 82 } 83 return; 84 } 85 86 int main() { 87 scanf("%d",&n); 88 scanf("%s%s%s",a,b,s); 89 fill(rep,rep+MAXN,-1); 90 fill(used,used+MAXN,false); 91 for(int i=n-1;i>=0;i--) { 92 int ai=a[i]-‘A‘; 93 int bi=b[i]-‘A‘; 94 int si=s[i]-‘A‘; 95 if(!usednum[ai]) { 96 usednum[ai]=true; 97 POS[k++]=ai; 98 } 99 if(!usednum[bi]) {100 usednum[bi]=true;101 POS[k++]=bi;102 }103 if(!usednum[si]) {104 usednum[si]=true;105 POS[k++]=si;106 }107 }108 dfs(0);109 return 0;110 }
noip 虫食算 (搜索)