题目连接：
https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=4896
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 nd 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!
Given a word addition problem, compute the number of solutions (possibly zero)
题意：
给你 n个字符串 问你是否能将1~n-1相加得到第n个字符串
你可以用0~9中数字代替某一个字母
一种数字只能代替一种字母
不同的字母不会超过10,n不超过10
题解：
对每一位填数爆搜
要耐心写好
#include<bits/stdc++.h>
using namespace std;
const int N = , M = 1e2+, mod = 1e9+, inf = 2e9;
typedef long long ll; char s[][];
int can = ,n,v[N],num[N];
void dfs(int dep,int last,int p,int now) {
int f = strlen(s[n]+);
if(dep>=(f+)) {
if(last==)
can++;
return ;
}
f = strlen(s[p]+);
if(p!=n) {
if((f - dep + ) >= ) {
if(v[s[p][f - dep + ]] != -) {
if(f - dep + == && v[s[p][f - dep + ]]==) return ;
dfs(dep,last,p+,now+v[s[p][(f - dep + )]]);
}else {
for(int i=;i<=;i++) {
if(num[i]) continue;
if(f - dep + ==&&i==) continue;
num[i] = ;
v[s[p][(f - dep + )]] = i;
dfs(dep,last,p+,now+i);
v[s[p][(f - dep + )]] = -;
num[i] = ;
}
}
}else dfs(dep,last,p+,now);
}else {
if(v[s[p][(f - dep + )]]!=-) {
if((f-dep+==)&&v[s[p][(f - dep + )]]==) return ;
if((now+last)% != v[s[p][(f - dep + )]]) return ;
dfs(dep+,(now+last)/,,);
}
else {
if(num[(now+last)%]) return ;
if(dep==f&&(now+last)%==) {return ;}
v[s[p][(f - dep + )]] = (now+last)%;
num[(now+last)%] = ;
dfs(dep+,(now+last)/,,);
num[(now+last)%] = ;
v[s[p][(f - dep + )]] = -;
}
}
}
int main()
{
while(~scanf("%d",&n)) {
for(int i=;i<=n;i++) scanf("%s",s[i]+);
int mx = ;
for(int i=;i<n;i++) {
int len = strlen(s[i]+);
mx = max(mx,len);
}
int mxx = strlen(s[n]+);
if(mx > mxx ) {
cout<<<<endl;
continue;
}
memset(num,,sizeof(num));
memset(v,-,sizeof(v));
can = ;
dfs(,,,);
cout<<can<<endl;
}
}