A19857. 乘法描述给定一个乘法式子，例如AB*CD=EFG每一个字母代表一个1~9 之间的一个数字，不同字母代表的数字不同，问有多少个不同的满足该式的取值方案。
填空题
容易
知识点
题目描述
乘法
描述
给定一个乘法式子，例如
AB*CD=EFG
每一个字母代表一个1~9 之间的一个数字，不同字母代表的数字不同，问有多少个不同的满足该式的取值方案。
输入格式
一个乘法等式由大写字母（A~I）、一个乘号（*）、一个等号（=）构成，无空格等其它字符
输出格式
满足该式的取值方案数量
输入样例
A*B=CB输出样例
6参考答案
#include <stdio.h>
#include <iostream>
#include <cstring>
using namespace std;
int used[10]; // 标记数字 1~9 是否用过
int val[26]; // 字母 -> 数字 正确映射
char s[15];
int a, b, c, ans = 0;
char letters[10]; // 存储所有出现的字母
int cnt = 0; // 字母总数
// 把字符串转成数字
void convert() {
int i = 0;
a = 0;
while (s[i] != '*') a = a*10 + val[s[i++]-'A'];
i++;
b = 0;
while (s[i] != '=') b = b*10 + val[s[i++]-'A'];
i++;
c = 0;
while (s[i]) c = c*10 + val[s[i++]-'A'];
}
// DFS 给第 k 个字母赋值
void dfs(int k) {
if (k == cnt) {
convert();
if (a * b == c) ans++;
return;
}
// 枚举 1~9
for (int i = 1; i <= 9; i++) {
if (!used[i]) {
used[i] = 1;
val[letters[k] - 'A'] = i;
dfs(k + 1);
used[i] = 0;
}
}
}
int main() {
scanf("%s", s);
int vis[26] = {0};
// 收集所有不重复字母
for (int i = 0; s[i]; i++) {
if (s[i] >= 'A' && s[i] <= 'Z' && !vis[s[i]-'A']) {
vis[s[i]-'A'] = 1;
letters[cnt++] = s[i];
}
}
dfs(0);
printf("%d\n", ans);
return 0;
}
上一题
下一题