ACM International Collegiate Programming Contest 2014 A dfs 好题

GREAT + SWERC = PORTO
We want to have a great SWERC at Porto this year and we approached this challenge
in several ways. We even framed it as a word addition problem, similar to the classic
SEND+MORE=MONEY, where each letter stands for a single digit (0, 1, 2, …, 8, 9)
that makes the arithmetic operation correct. In word additions different letters cannot be
assigned the same digit and the leftmost letter in a word cannot be zero (0). In particular,
a single letter term cannot be zero.
To solve this word addition problem we had to find positive digits for G, S and P, and
digits for R, E, A, T, W, C, O, so that each letter has a different digit and the sum is
correct. It turns out that, unlike the classical SEND+MORE=MONEY which has a single
solution, GREAT+SWERC=PORTO has six solutions.
T=7, E=3, W=9, G=1, A=0, P=4, S=2, C=8, R=6, O=5
T=7, E=3, W=9, G=2, A=0, P=4, S=1, C=8, R=6, O=5
T=8, E=5, W=1, G=3, A=7, P=9, S=6, C=4, R=0, O=2
T=8, E=5, W=1, G=6, A=7, P=9, S=3, C=4, R=0, O=2
T=9, E=5, W=2, G=1, A=8, P=7, S=6, C=4, R=0, O=3
T=9, E=5, W=2, G=6, A=8, P=7, S=1, C=4, R=0, O=3
Having more than one solution does not make GREAT+SWERC=PORTO a good problem
to solve by hand, but it is still a piece of cake for a programer. Moreover, it gives us another
reason to organize SWERC again next year and, who knows, in years to come!
Task
Given a word addition problem, compute the number of solutions (possibly zero).
Input
A line with an integer n, followed by n lines containing a word each with maximum length
of 10 letters. The first n−1 words are the terms to be added and the last line is the result.
Universidade do Porto Computer Science Department 3
Problem A Problem A
Words contain only capital letters. If words have different lengths, they must be interpreted
as aligning to the right. For instance, in the SEND+MORE=MONEY problem, the D of
the first word and E of the second word align with the Y of the final word. You can also
assume that the size of the last word is greater than or equal to the maximum size of the
preceding words, and moreover, at most ten distinct letters are involved in a word problem.
Constraints
3 ≤ n ≤ 10
Each word has at most 10 symbols (capital letters).
A word problem has at most 10 distinct letters.
Output
A single line with an integer: the number of solutions of the word addition problem given
as input.
Sample Input 1
3
GREAT
SWERC
PORTO
Sample Output 1
6
Sample Input 2
3
SEND
MORE
MONEY
Sample Output 2
1
Sample Input 3
5
TOO
GOOD
TO
BE
TRUE
Sample Output 3
93
给定字符串，满足加法，求解有多少种方案，前导0不合法：
dfs 即可： 但写法得细心；

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<string>
#include<cmath>
#include<map>
#include<set>
#include<vector>
#include<queue>
#include<string>
#include<bitset>
typedef long long ll;
using namespace std;
typedef unsigned long long int ull;
#define maxn 200005
#define ms(x) memset(x,0,sizeof(x))
#define inf 0x3f3f3f3f
const long long int mod = 1e9 + 7;
#define pie acos(-1.0)

ll read() {
    ll x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch>'9') {
        if (ch == '-') {
            f = -1;
        }
        ch = getchar();
    }
    while (ch >= '0'&&ch <= '9') {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}

ll quickpow(ll a, ll b) {
    ll ans = 1;
    while (b > 0) {
        if (b % 2)ans = ans * a%mod;
        b = b / 2;
        a = a * a%mod;
    }
    return ans;
}

int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a%b);
}
int tot, n, s;
char ch[20][20];
int book[1000], p[1000], a[1000];
int u[1000];
int ans;
int revs(char ch[]) {
    int res = 0;
    int len = strlen(ch);
    if (a[ch[0] - 'A'] == 0)return -1;
    int x = 1;
    for (int i = len - 1; i >= 0; i--) {
        res += x * a[ch[i] - 'A'];
        x = x * 10;
    }
    return res;
}
bool judge() {
    int pre = 0, sum = 0;
    for (int i = 0; i < n - 1; i++) {
        if (revs(ch[i])==-1)return false;
        pre += revs(ch[i]);
    }
    if (revs(ch[n - 1]) == -1)return false;
    sum += revs(ch[n - 1]);
    if (pre == sum)return true;
    else return false;
}

void dfs(int step) {
    if (step >= tot) {
        if (judge())ans++;
        return;
    }
    for (int i = 0; i < 10; i++) {
        if (book[i] == 0) {
            a[p[step]] = i;
            book[i] = 1;
            dfs(step + 1);
            book[i] = 0;
        }
    }
    return;
}
int main() {
    //ios::sync_with_stdio(false);
    while (cin >> n) {
        ms(book); ms(p); ms(a); ms(u);
        tot = 0;
        ans = 0;
    //  step = 0;
        for (int i = 0; i < n; i++) {
            cin >> ch[i];
            int len = strlen(ch[i]);
            for (int j = 0; j < len; j++) {
                u[ch[i][j]-'A'] = 1;
            }
        }
        for (int i = 0; i < 26; i++) {
            if (u[i])p[tot++] = i;
        }
        dfs(0);
        cout << ans << endl;
    }

    return 0;
}