NOIP 2004 数字游戏(虫食算)

下面程序可计算如下形式的式子:

1
2
3
4
5
6
7
8
9
10
11
one
+ nine
+ fifty
+twenty
-------
eighty
a
+a
--
bc

方法是枚举进位+解方程,涉及的字母以及各个位上的进位作为变量,然后解方程。这样可以用 各个位上的进位 和 字母变量中的自由变量 表示 其他字母变量。枚举 各个位上的进位 和 字母变量中的自由变量 以求出 其他字母变量,以此得到各组解。使用方法:根据要求解的式子设置各个变量,N、M设置得大点没关系,L要正好等于式子的行数,然后输入L行字符串

举例:

1
2
3
N=10(10个变量)
M=6(一行最大长度6)
L=5(5行)

输入

1
2
3
4
5
one
nine
fifty
twenty
eighty
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <math.h>
#include <string>
#include <vector>
using namespace std;
const int N = 10; //maximum number of variables
const int M = 6; //maximum line length
const int L = 3; //number of lines
string s[L];
int len[L], mapping[256];
int m = 0, n = 0, res;
int pi[N], x[M+N], a[M][M+N], d[M];
vector<int> fre;
int gcd(int x, int y)
{
int t;
x = abs(x);
y = abs(y);
while (y) t = x%y, x = y, y = t;
return x;
}
bool GaussJordanElimination()
{
memset(pi, 0xFF, sizeof(pi));
for (int i = 0; i < m; ++i)
{
int pivot = i;
if (!a[i][i])
{
for (int j = 0; j < n; ++j)
if (a[i][j]) pivot = j;
if (pivot == i) continue;
}
pi[pivot] = i;
for (int j = 0; j < m; ++j)
if (j != i && a[j][pivot])
{
int lcm = a[i][pivot] / gcd(a[i][pivot], a[j][pivot]) * a[j][pivot], k1 = lcm/a[i][pivot], k2 = lcm/a[j][pivot];
for (int k = 0; k < m+n; ++k)
a[j][k] = a[j][k]*k2-a[i][k]*k1;
}
}
for (int i = 0; i < n; ++i)
if (pi[i] == -1)
fre.push_back(i);
}
void DFS_left(int k)
{
if (k == fre.size())
{
for (int i = 0; i < n; ++i)
if (pi[i] != -1)
{
int t = 0;
for (int j = 0; j < fre.size(); ++j)
t -= a[pi[i]][fre[j]]*x[fre[j]];
for (int j = 0; j < m; ++j)
t -= a[pi[i]][n+j]*x[n+j];
if (t%a[pi[i]][i]) return;
x[i] = t/a[pi[i]][i];
if (x[i] < 0 || x[i] >= 10) return;
}
for (int i = 0; i < L; ++i)
{
for (int j = m-s[i].size(); j; --j) printf(" ");
for (string::iterator it = s[i].begin(); it != s[i].end(); ++it)
printf("%3d", x[mapping[*it]]);
puts("");
}
puts("");
++res;
}
else for (int i = 0; i < 10; ++i)
x[fre[k]] = i, DFS_left(k+1);
}
void DFS_right(int k)
{
if (k == m)
DFS_left(0);
else for (int i = 0; i < L-1; ++i)
x[n+k] = i, DFS_right(k+1);
}
int main()
{
memset(mapping, 0xFF, sizeof(mapping));
memset(a, 0, sizeof(a));
for (int i = 0; i < L; ++i)
{
cin >> s[i];
if (s[i].size() > m) m = s[i].size();
for (int j = 0; j < s[i].size(); ++j)
{
if (mapping[s[i][j]] == -1)
mapping[s[i][j]] = n++;
a[s[i].size()-1-j][mapping[s[i][j]]] += i == L-1 ? -1 : 1;
}
}
for (int i = 0; i < m; ++i)
{
if (i) a[i][n+i] = 1;
if (i < m-1) a[i][n+i+1] = -10;
}
GaussJordanElimination();
res = 0;
DFS_right(1);
printf("\n%d solution(s).\n", res);
}