1 条题解
-
1赵青海 (huhe) LV 7 SU @ 2021-8-7 21:07:53
C++ :
#include <cstring> #include <iostream> #include <algorithm> using namespace std; const int N = 30; int n; char eq[3][N];//存储等式 int q[N];//从低位到高位每个数字的顺序 int path[N];//存储每个字母对应的是哪个数字 bool visit[N]; bool check()//剪枝 { for (int i = n - 1, t = 0; i >= 0; i -- )//判断是否合法,从低位开始 { int a = path[eq[0][i] - 'A'], b = path[eq[1][i] - 'A'], c = path[eq[2][i] - 'A'];//分别为被加数,加数,和 if (a != -1 && b != -1 && c != -1)//非不确定的值 { if (t == -1)//如果t进位不确定 { if ((a + b) % n != c && (a + b + 1) % n != c) return false;//进位为0且进位为1时都不等于c时,矛盾 if (!i && a + b >= n) return false; // 最高位有进位 } else { if ((a + b + t) % n != c) return false;//判断当前的t是否合法 if (!i && a + b + t >= n) return false;// 最高位有进位 t = (a + b + t) / n;//更新进位 } } else t = -1;//由于a,b,c有不确定的值,则进位t也不确定 } return true;//若没有发现矛盾则继续进行 } bool dfs(int u)//u表示当前枚举到哪个数字 { if (u == n) return true;//已经枚举完所有字母了 for (int i = 0; i < n; i ++ )//枚举当前数选哪个数字 if (!visit[i])//如果这个数字没有被枚举过 { visit[i] = true; path[q[u]] = i;//枚举当前数字为i if (check() && dfs(u + 1)) return true;//搜下一层,剪枝 path[q[u]] = -1;//枚举失败,恢复现场 visit[i] = false; } return false; } int main() { cin >> n; cin >> eq[0] >> eq[1] >> eq[2];//输入三条等式 for (int i = n - 1, k = 0; i >= 0; i -- )//从低位开始 for (int j = 0; j < 3; j ++ ) { int c = eq[j][i] - 'A';//转换成0 - N-1的数 if (!visit[c])//若没有被放过的话 { visit[c] = true; q[k ++ ] = c;//放入每个数字到q中 } } memset(visit, 0, sizeof visit);//再次初始化访问数组 memset(path, -1, sizeof path); dfs(0); for (int i = 0; i < n; i ++ ) cout << path[i] << ' '; return 0; }
- 1
信息
- ID
- 95
- 时间
- 1000ms
- 内存
- 128MiB
- 难度
- 3
- 标签
- 递交数
- 79
- 已通过
- 45
- 上传者