UVA12877 GREAT + SWERC = PORTO

题目描述

PDF

输入格式

输出格式

题意翻译

输入n个字符串，将第1~n-1相加得到第n个字符串

可以用0~9中数字代替某一个字母

一种数字只能代替一种字母

不同的字母不会超过10,n不超过10

求总共有多少可能的方案

Translated by @ysy666

输入输出样例

输入 #1复制

3
GREAT
SWERC
PORTO
3
SEND
MORE
MONEY
5
TOO
GOOD
TO
BE
TRUE

输出 #1复制

6
1
93

我们用 map 存字母和数字的对应关系，遇到一个没有对应数字的字母就枚举所有没用过的数字，每搜完一列就看看得数是否符合（就是剪枝）。 然后就轻松 AC 了。

代码如下：

#include 
using namespace std;
#define ll long long
#define db double
#define ld long double
#define forr(i, a, n) for (int i = a; i < n; i++)
#define rep(i, n) forr(i, 0, n)
#define repp(i, n) forr(i, 1, n + 1)
#define pb push_back
#define mp make_pair
#define vvi vector>
#define MAXN 0x3f3f3f3f
int n, mx = 0, ans = 0;
string s[15];
map m;
map mm;
void dfs(int x, int y, int cnt)
{
	if (x == mx)
	{
		if (!cnt)
			ans++;
		return;
	}
	if (y == n - 1)
	{
		if (m[s[y][x]] != -1)
		{
			if (m[s[y][x]] != cnt % 10)
				return;
			if (s[y][x + 1] == '0' && m[s[y][x]] == 0)
				return;
			dfs(x + 1, 0, cnt / 10);
		}
		else
		{
			if (mm[cnt % 10])
				return;
			if (s[y][x + 1] == '0' && cnt % 10 == 0)
				return;
			m[s[y][x]] = cnt % 10;
			mm[cnt % 10] = 1;
			dfs(x + 1, 0, cnt / 10);
			mm[cnt % 10] = 0;
			m[s[y][x]] = -1;
		}
		return;
	}
	if (m[s[y][x]] != -1)
	{
		if (m[s[y][x]] == 0 && s[y][x + 1] == '0' && s[y][x] != '0')
			return;
		dfs(x, y + 1, cnt + m[s[y][x]]);
	}
	else
	{
		rep(i, 10)
		{
			if (s[y][x + 1] == '0' && !i)
				continue;
			if (!mm[i])
			{
				mm[i] = 1;
				m[s[y][x]] = i;
				dfs(x, y + 1, cnt + i);
				mm[i] = 0;
				m[s[y][x]] = -1;
			}
		}
	}
}
int main()
{
	cin >> n;
	rep(i, n)
	{
		cin >> s[i];
		reverse(s[i].begin(), s[i].end());
		if (s[i].size() > mx)
			mx = s[i].size();
	}
	mx++;
	rep(i, n) rep(j, s[i].size() - mx) s[i] += '0';
	rep(i, 26)
	{
		char c = 'A';
		c = c + i;
		m[c] = -1;
	}
	m['0'] = 0;
	dfs(0, 0, 0);
	cout << ans;
	return 0;
}

其实还有一种做法：

因为数据范围很小，所以暴力枚举所有字母对应的数，最后判断即可。