网站开发比较流行的框架,电子商务网站优点,太原网页设计师,百度推广智能网站虫食算
ybtoj dfs-1-3
题目大意
给出一个如ABC的N进制的式子#xff0c;现在知道某些位上的数字是相同的#xff0c;让你求出这个式子
样例输入
5
ABCED
BDACE
EBBAA样例输出
1 0 3 4 2数据范围 1⩽N⩽261\leqslant N \leqslant 261⩽N⩽26
解题思路
从低位到高位枚举…虫食算
ybtoj dfs-1-3
题目大意
给出一个如ABC的N进制的式子现在知道某些位上的数字是相同的让你求出这个式子
样例输入
5
ABCED
BDACE
EBBAA样例输出
1 0 3 4 2数据范围
1⩽N⩽261\leqslant N \leqslant 261⩽N⩽26
解题思路
从低位到高位枚举每一种相同的位置的数值 每枚举一个就判断一次是否合法 对于某一位的加法如果三个数都知道了就判断是否符合对于进位不明的就0,1都判断一遍 如果有不知道的就不用管
代码
#pragma GCC optimez(2)
#includecstdio
#includecstring
#includeiostream
#includealgorithm
#define ll long long
using namespace std;
int n, w, pp, a[50], b[50], p[50], h[50];
string str1, str2, str3;
bool check()
{int g 0;for (int i n - 1; i 0; --i){int A a[str1[i] - 65], B a[str2[i] - 65], C a[str3[i] - 65];if (A ! -1 B ! -1 C ! -1){if (g -1)//进位不明{if ((A B) % n ! C (A B 1) % n ! C) return false;if (!i A B n) return false;//最高位不能存在进位}else{if ((A B g) % n ! C) return false;//判断是否符合g (A B g) / n;if (!i g) return false;}}else g -1;}return true;
}
void dfs(int x)
{if (x n){for (int i 0; i n; i)printf(%d , a[i]);pp 1;return;}for (int i 0; i n; i)//枚举if (!p[i]){a[b[x]] i;p[i] 1;if (check()) dfs(x 1);if (pp) return; p[i] 0;a[b[x]] -1;}return;
}
int main()
{scanf(%d, n);cinstr1str2str3;for (int i n - 1; i 0; --i)//从低位到高位{if (!h[str1[i] - 65]) h[str1[i] - 65] 1, b[w] str1[i] - 65;if (!h[str2[i] - 65]) h[str2[i] - 65] 1, b[w] str2[i] - 65;if (!h[str3[i] - 65]) h[str3[i] - 65] 1, b[w] str3[i] - 65;}for (int i 0; i n; i)a[i] -1;pp 0;dfs(1);return 0;
}
