蟲食算

ybtoj dfs-1-3

題目大意

給出一個如A+B=C的N進制的式子，現在知道某些位上的數字是相同的，讓你求出這個式子

樣例輸入

5 ABCED BDACE EBBAA

樣例輸出

1 0 3 4 2

數據范圍

$1?N?26$

解題思路

從低位到高位枚舉每一種相同的位置的數值
每枚舉一個就判斷一次是否合法：
對于某一位的加法，如果三個數都知道了就判斷是否符合（對于進位不明的就0,1都判斷一遍）
如果有不知道的就不用管

代碼

#pragma GCC optimez(2) #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #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);cin>>str1>>str2>>str3;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; }

總結

以上是生活随笔為你收集整理的【dfs】虫食算（ybtoj dfs-1-3）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。