[NOIP2004] 虫食算 - NekoMio's Blog

题目描述#

所谓虫食算，就是原先的算式中有一部分被虫子啃掉了，需要我们根据剩下的数字来判定被啃掉的字母。来看一个简单的例子：

1
43#98650#45
2
+ 8468#6633
3
44445506978

其中#号代表被虫子啃掉的数字。根据算式，我们很容易判断：第一行的两个数字分别是5和3，第二行的数字是5。现在，我们对问题做两个限制：首先，我们只考虑加法的虫食算。这里的加法是N进制加法，算式中三个数都有N位，允许有前导的0。其次，虫子把所有的数都啃光了，我们只知道哪些数字是相同的。我们将相同的数字用相同的字母表示，不同的数字用不同的字母表示。如果这个算式是N进制的，我们就取英文字母表中的前N个大写字母来表示这个算式中的0到N-1这N个不同的数字（但是这N个字母并不一定顺序地代表0到N-1）。输入数据保证N个字母分别至少出现一次。

1
BADC
2
+ CBDA
3
DCCC

上面的算式是一个4进制的算式。很显然，我们只要让ABCD分别代表0123，便可以让这个式子成立了。你的任务是，对于给定的N进制加法算式，求出N个不同的字母分别代表的数字，使得该加法算式成立。输入数据保证有且仅有一组解。

输入#

包含4行。第一行有一个正整数N（N <= 26），后面的3行每行有一个由大写字母组成的字符串，分别代表两个加数以及和。这3个字符串左右两端都没有空格，从高位到低位，并且恰好有N位。

输出#

包含一行。在这一行中，应当包含唯一的那组解。解是这样表示的：输出N个数字，分别表示A，B，C……所代表的数字，相邻的两个数字用一个空格隔开，不能有多余的空格。

样例输入#

1
5
2
ABCED
3
BDACE
4
EBBAA

样例输出#

1
1 0 3 4 2

题解#

从后向前从大到小倒着搜
分8种情况讨论
打的是真爽

1
#include <cstdio>
2
#include <cstring>
3
#include <algorithm>
4
#include <cstdlib>
5
using namespace std;
6
char a[30], b[30], c[30];
7
bool mark[30];
8
int map[300], n, ans;
9
void dfs(int pos, int y)
10
{
11
    ans++;
12
    //printf("%d\n", ans);
13
    if(pos == 0)
14
    {
15
        for (int i = 'A'; i < 'A' + n; i++)
16
            printf("%d ",map[i]);
17
        exit(0);
18
    }
19
    if(map[a[pos]] != -1 && map[b[pos]] != -1 && map[c[pos]] != -1)
20
    {
21
        if((map[a[pos]] + map[b[pos]] + y) % n != map[c[pos]])
22
            return;
23
        else
24
            dfs(pos - 1, (map[a[pos]] + map[b[pos]] + y) / n);
25
    }
26
    else if (map[a[pos]] != -1 && map[b[pos]] != -1)
27
    {
28
        if(mark[(map[a[pos]] + map[b[pos]] + y) % n])
29
            return;
30
        else
31
        {
32
            map[c[pos]] = (map[a[pos]] + map[b[pos]] + y) % n;
33
            mark[(map[a[pos]] + map[b[pos]] + y) % n] = 1;
34
            dfs(pos - 1, (map[a[pos]] + map[b[pos]] + y) / n);
35
            mark[(map[a[pos]] + map[b[pos]] + y) % n] = 0;
36
            map[c[pos]] = -1;
37
        }
38
    }
39
    else if (map[a[pos]] != -1 && map[c[pos]] != -1)
40
    {
41
        int now = map[c[pos]] + n - y - map[a[pos]];
42
        if(mark[now % n])
43
            return;
44
        map[b[pos]] = now % n;
45
        mark[now % n] = 1;
46
        dfs(pos - 1, (now % n) == now ? 1 : 0);
47
        map[b[pos]] = -1;
48
        mark[now % n] = 0;
49
    }
50
    else if (map[b[pos]] != -1 && map[c[pos]] != -1)
51
    {
52
        int now = map[c[pos]] + n - y - map[b[pos]];
53
        if(mark[now % n])
54
            return;
55
        map[a[pos]] = now % n;
56
        mark[now % n] = 1;
57
        dfs(pos - 1, (now % n) == now ? 1 : 0);
58
        map[a[pos]] = -1;
59
        mark[now % n] = 0;
60
    }
61
    else if(map[a[pos]] != -1)
62
    {
63
        for (int i = 0; i < n; i++)
64
            if(!mark[i] && !mark[(map[a[pos]] + i + y) % n])
65
            {
66
                map[b[pos]] = i;
67
                map[c[pos]] = (map[a[pos]] + i + y) % n;
68
                mark[i] = 1;
69
                mark[(map[a[pos]] + i + y) % n] = 1;
70
                dfs(pos - 1, (map[a[pos]] + i + y) / n);
71
                map[b[pos]] = -1;
72
                map[c[pos]] = -1;
73
                mark[i] = 0;
74
                mark[(map[a[pos]] + i + y) % n] = 0;
75
            }
76
    }
77
    else if(map[b[pos]] != -1)
78
    {
79
        for (int i = 0; i < n; i++)
80
            if(!mark[i] && !mark[(map[b[pos]] + i + y) % n])
81
            {
82
                map[a[pos]] = i;
83
                map[c[pos]] = (map[b[pos]] + i + y) % n;
84
                mark[i] = 1;
85
                mark[(map[b[pos]] + i + y) % n] = 1;
86
                dfs(pos - 1, (map[b[pos]] + i + y) / n);
87
                map[a[pos]] = -1;
88
                map[c[pos]] = -1;
89
                mark[i] = 0;
90
                mark[(map[b[pos]] + i + y) % n] = 0;
91
            }
92
    }
93
    else if(map[c[pos]] != -1)
94
    {
95
        for (int i = 0; i < n; i++)
96
        {
97
            if(!mark[i] && !mark[(map[c[pos]] + n - i - y) % n])
98
            {
99
                map[a[pos]] = i;
100
                map[b[pos]] = (map[c[pos]] + n - i - y) % n;
101
                mark[i] = 1;
102
                mark[(map[c[pos]] + n - i - y) % n] = 1;
103
                dfs(pos - 1, ((map[c[pos]] + n - i - y) % n == (map[c[pos]] + n - i - y)));
104
                map[a[pos]] = -1;
105
                map[b[pos]] = -1;
106
                mark[i] = 0;
107
                mark[(map[c[pos]] + n - i - y) % n] = 0;
108
            }
109
        }
110
    }
111
    else
112
    {
113
        // printf("\\\\\n");
114
        for (int i = n - 1; i >= 0; i--)
115
        {
116
            if(mark[i]) continue;
117
            mark[i] = 1;
118
            map[a[pos]] = i;
119
            // printf("------__\n");
120
            for (int j = n - 1; j >= 0; j--)
121
            {
122
                if(!mark[j] && !mark[(i + j + y) % n])
123
                {
124
                    // printf("===\n");
125
                    mark[j] = mark[(i + j + y) % n] = 1;
126
                    map[b[pos]] = j;
127
                    map[c[pos]] = (i + j + y) % n;
128
                    dfs(pos - 1, (i + j + y) / n);
129
                    mark[j] = mark[(i + j + y) % n] = 0;
130
                    map[b[pos]] = -1;
131
                    map[c[pos]] = -1;
132
                }
133
                else if (mark[j] && mark[(i + j + y) % n] && (j == map[b[pos]]) && ((i + j + y) % n == map[c[pos]]))
134
                {
135
                    dfs(pos - 1, (i + j + y) / n);
136
                }
137
                else if (mark[j] && (j == map[b[pos]]) && !mark[(i + j + y) % n])
138
                {
139
                    // printf("----\n");
140
                    mark[(i + j + y) % n] = 1;
141
                    map[c[pos]] = (i + j + y) % n;
142
                    dfs(pos - 1, (i + j + y) / n);
143
                    map[c[pos]] = -1;
144
                    mark[(i + j + y) % n] = 0;
145
                }
146
            }
147
            map[a[pos]] = -1;
148
            mark[i] = 0;
149
        }
150
    }
151
}
152
int main()
153
{
154
    // freopen("alpha.in","r",stdin);
155
    // freopen("alpha.out","w",stdout);
156
    scanf("%d", &n);
157
    scanf("%s%s%s", a + 1, b + 1, c + 1);
158
    for (int i = 'A'; i < 'A' + n; i++)
159
        map[i] = -1;
160
    dfs(n, 0);
161
}