ACDREAM 05D 嘩啦啦族的加法計算

Problem Description

小彭玉今天開始學(xué)習(xí)加法啦！

唐老師寫了個加法等式，小彭玉撲通撲通就湊出來了一種合法解

唐老師又寫了個加法等式，然后想問你，這個加法等式究竟有多少種可行解呢？

Input

輸入包含多組數(shù)據(jù)。

每組數(shù)據(jù)第一行一個整數(shù)n，表示有n個字符串 3 ≤ n ≤ 10

接下來n行，每行有1個最多只含10個大寫字母的字符串，前 n - 1 行的字符串表示加數(shù)，第 n 行的字符串表示和

每個樣例最多只有26個互不相同的大寫字母，每個字母表示 0 - 9 中的一個數(shù)，相同字母表示相同的數(shù)，不同字母表示不同的數(shù)輸入包含多組數(shù)據(jù)。
Output

對于每組數(shù)據(jù)輸出一個整數(shù)，表示不同的可行解的數(shù)量。

對于兩個可行解，只要有一個字母表示不同的數(shù)字，我們就認(rèn)為這兩個可行解不同
Sample Input

4
TAI
SHEN
LA
ACER

Sample Output

76

題目大意：由26個字母組成的豎式加法，一個字母對應(yīng)一個數(shù)字（0~9，不會同時出現(xiàn)10個不同的字母），問有幾種映射是滿足這個豎式的。

解題思路：注意豎式上的數(shù)不能有前導(dǎo)零。

#include <cstdio> #include <cstring> #include <algorithm> #include <cmath> #include <cstdlib> #include <map> using namespace std; typedef long long ll; int n; char s[15][15]; int vis[10]; int len[15], Max, ans; int mp[30]; bool check() {for(int i = 1; i <= n; i++) {int len = strlen(s[i]);if(mp[s[i][len-1] - 'A'] == 0)return false;}return true; } void dfs(int x, int y, int sum) {if(x == n) {if(y == Max - 1) {if(sum / 10 == 0) {if(mp[s[x][y] - 'A'] == -1 && check() && !vis[sum % 10]) {ans++;}else if(mp[s[x][y] - 'A'] == sum % 10 && check()) {ans++;}}}else if(mp[s[x][y] - 'A'] != -1) {if(sum % 10 == mp[s[x][y] - 'A'])dfs(1, y + 1, sum / 10);}else {if(!vis[sum % 10]) {mp[s[x][y] - 'A'] = sum % 10;vis[sum % 10] = true;dfs(1, y + 1, sum / 10);mp[s[x][y] - 'A'] = -1;vis[sum % 10] = false;}}return ;}else {if(s[x][y] == 0) {dfs(x + 1, y, sum);}else if(mp[s[x][y] - 'A'] != -1) {dfs(x + 1, y, sum + mp[s[x][y] - 'A']);}else {for(int i = 0; i < 10; i++) {if(!vis[i]) {mp[s[x][y] - 'A'] = i;vis[i] = true;dfs(x + 1, y, sum + i);mp[s[x][y] - 'A'] = -1;vis[i] = false;}}}} }int main() {while (scanf("%d\n", &n) != EOF) {memset(vis, 0, sizeof(vis));memset(mp, -1, sizeof(mp));memset(s, 0, sizeof(s));Max = 0;for (int i = 1; i <= n; i++) {scanf("%s", s[i]);len[i] = strlen(s[i]);Max = max(Max, len[i]);reverse(s[i], s[i] + len[i]);} ans = 0;dfs(1, 0, 0);printf("%d\n", ans);}return 0; }

總結(jié)

以上是生活随笔為你收集整理的ACDREAM 05D 哗啦啦族的加法计算（DFS专场）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。