【DFS】Ybt_虫食算
题目大意
可恶的虫子把一些数字吃掉了！
你只能知道数位数和进制数为n的三个数 A，B，C。
其中 C=A B，数字都由大写字母表示，相同字母表示这个位置上是相同的数字。
要你求每个字母所代表的数字。
输入
5
ABCED
BDACE
EBBAA
输出
1 0 3 4 2
解
深度搜索。枚举这些字母代表的数字。
从后往前枚举列，设这列的被加数，加数，与和为 a，b，c，得：
- 如果上一列的a’，b’确定，那么进位也是确定的，如果a b t不等于这一列的c，方案不合法
- 如果上一列不确定，如果 a b不等于c 且 a b 1不等于c，方案不合法
- 如果最大位有进位…方案不合法。
代码
#include<cstdio>#include<cstring>#include<iostream>using namespace std;bool used[30];int n, flag, t;int k[30],A[30],B[30],S[30],sssx[30];char getc(){ //读入char lc = getchar();while(lc > 'Z' || lc < 'A') lc = getchar();return lc;}bool check(){ //判断int jw = 0;for(int i = n; i > 0; --i){int a = k[A[i]], b = k[B[i]], c = k[S[i]];if(a != -1 && b != -1 && c != -1){ //知道这三个数if(jw != -1){ //知道进位if((a b jw) % n != c) return 0;if(i == 1 && a b jw >= n) return 0; //最大位超jw = (a b jw) / n;} else{ //不知道进位if((a b) % n != c && (a b 1) % n !=c) return 0; if(i == 1 && a b >=n) return 0; //最大位超}}else jw = -1;}return 1; //返回}void dfs(int noo){ //第几个该填的数的序号...if(noo == n){flag = 1;return;}int no = sssx[noo]; //no为该填的数for(int i = n-1; i >= 0; --i) //倒着轮会快一点if(used[i] == 0){ //没填过 k[no] = i;if(check()){ //判断 used[i] = 1; dfs(noo 1); if(flag) return; used[i] = 0; } k[no] = -1;}} int main(){scanf("%d", &n);for(int i = 1; i <= n; i) A[i] = getc()-65;for(int i = 1; i <= n; i) B[i] = getc()-65;for(int i = 1; i <= n; i) S[i] = getc()-65;for(int i = n; i >= 1; --i){ //搞个判断字母的顺序（从数位小到大）if(used[A[i]] == 0) sssx[t ] = A[i];used[A[i]] = 1;if(used[B[i]] == 0) sssx[t ] = B[i];used[B[i]] = 1;if(used[S[i]] == 0) sssx[t ] = S[i];used[S[i]] = 1;}memset(used, 0, sizeof(used));for(int i = 0; i < n; i) k[i] = -1; dfs(0);for(int i = 0; i < n; i) //输出 printf("%d ", k[i]);} 赞 (0)