洛谷P1092「NOIP2004」《虫食算》

三月 30, 2019 5148

调换搜索顺序以获得更快时间

题目描述

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

1
2
3
 43#9865#045
+  8468#6633
 44445509678

其中 \# 号代表被虫子啃掉的数字。根据算式，我们很容易判断：第一行的两个数字分别是5和3，第二行的数字是5。

现在，我们对问题做两个限制：

首先，我们只考虑加法的虫食算。这里的加法是N进制加法，算式中三个数都有N位，允许有前导的0。

其次，虫子把所有的数都啃光了，我们只知道哪些数字是相同的，我们将相同的数字用相同的字母表示，不同的数字用不同的字母表示。如果这个算式是N进制的，我们就取英文字母表午的前N个大写字母来表示这个算式中的0到N-1这N个不同的数字：但是这N个字母并不一定顺序地代表0到N−1。输入数据保证N个字母分别至少出现一次。

1
2
3
 BADC
+CBDA
 DCCC

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

输入输出格式

输入格式

包含四行。
第一行有一个正整数 N(N \le 26) 。

后面的三行，每行有一个由大写字母组成的字符串，分别代表两个加数以及和。这3个字符串左右两端都没有空格，从高位到低位，并且恰好有NN位。

输出格式

一行，即唯一的那组解。

解是这样表示的：输出N个数字，分别表示A,B,C,…所代表的数字，相邻的两个数字用一个空格隔开，不能有多余的空格。

输入输出样例

输入样例

1
2
3
4
5
ABCED
BDACE
EBBAA

输出样例

1
1 0 3 4 2

说明

对于30％的数据，保证有 N \le 10 ；

对于50％的数据，保证有 N \le 15 ；

对于全部的数据，保证有 N \le 26 。

noip2004提高组第4题

解题思路

考虑暴力枚举每一个数字

肯定是过不去的

考虑枚举算式中的每一个数

用时大大减小

但是可能会填出

1
2
3
4
 1111
+1221
-----
 2333

这样的情况

显然这样的情况是无用的

就需要一个判断

耗时依然较高

换一下搜索顺序，每列每列地填

在填完一列之后判断一下等式是否成立

就差不多了

虽然可能会耗点时间
但是省出来的时间是多得多的

代码实现

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
118
119
120
121
122
123
124
125
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <string>
#include <cstdio>

#define FILE_IN(__fname) freopen(__fname, "r", stdin)
#define FILE_OUT(__fname) freopen(__fname, "w", stdout)
#define IMPROVE_IO() std::ios::sync_with_stdio(false)
#define DDBUG(x,y) std::cerr << #x << " = " << x << y;
#define MDBUG(comment) std::cerr << comment;
#define getNum(x) ((ans[x]))
#define giveNum(x,y) ((ans[x] = y))

using std::cin;
using std::cout;
using std::endl;

const int MAXN = 26 + 10;

int n, ans[MAXN], col[3 + 2][MAXN];
bool vis[MAXN];
std::string ol[3];

void Init() {
    // convert the letters to numbers
    for (int i = 0; i < 3; ++i) {
        for (int j = 0; j < n; ++j) {
            col[i + 1][j + 1] = ol[i][j] - 'A' + 1;
        }
    }
}

namespace Checks {
    bool check1() {
        // Check for unfilled letters
        for (int i = 1; i <= n; ++i) if (ans[i] == -1) return true;
        return false;
    }
    
    bool check2() {
        // Check that the equation is correct
        int nextBit = 0; // addition carry
        for (int i = n; i >= 1; --i) {
            // from right to left
            int A = getNum(col[1][i]);
            int B = getNum(col[2][i]);
            int C = getNum(col[3][i]);
            if ((A + B + nextBit) % n != C) return true;
            nextBit = (bool) ((A + B + nextBit) >= n);
        }
        return false;
    }
    
    bool check3() {
        // Other equation correction checking
        if (getNum(col[1][1]) + getNum(col[2][1]) >= n) return true; // The first one needs to be carried
        for (int i = n; i >= 1; --i) {
            int A = getNum(col[1][i]);
            int B = getNum(col[2][i]);
            int C = getNum(col[3][i]);
            if (A == -1 || B == -1 || C == -1) continue;
            if ((A + B) % n != C && (A + B + 1) % n != C) return true;
        }
        return false;
    }
}

void DFS(int column = n, int line = 1, int nextBit = 0) {
    // from right to left
    if (Checks::check3()) return;
    if (!Checks::check1()) {
        if (!Checks::check2()) {
            for (int i = 1; i <= n; ++i) cout << ans[i] << ' ';
            cout << endl;
            exit(0);
        }
        return;
    }
    if (getNum(col[line][column]) == -1) {
        // unfilled letter, fill it
        for (int i = n - 1; i >= 0; --i) {
            if (vis[i]) continue;
            if (line == 3) {
                int A = getNum(col[1][column]);
                int B = getNum(col[2][column]);
                int C = A + B + nextBit;
                if (C % n != i) continue;
                vis[i] = true;
                giveNum(col[line][column], i);
                DFS(column - 1, 1, (bool) (C >= n));
                vis[i] = false;
                giveNum(col[line][column], -1);
            } else {
                vis[i] = true;
                giveNum(col[line][column], i);
                DFS(column, line + 1, nextBit);
                vis[i] = false;
                giveNum(col[line][column], -1);
            }
        }
    } else {
        // filled letter
        if (line != 3) DFS(column, line + 1, nextBit);
        else {
            int A = getNum(col[1][column]);
            int B = getNum(col[2][column]);
            int C = A + B + nextBit;
            DFS(column - 1, 1, (bool) (C >= n));
        }
    }
}

int main() {
    IMPROVE_IO();
    cin >> n;
    cin >> ol[0];
    cin >> ol[1];
    cin >> ol[2];
    Init();
    memset(ans, -1, sizeof ans);
    DFS();
    return 0;
}