P1092. 虫食算

发表于 分类于 阅读次数： Waline： 本文字数： 661 阅读时长 ≈ 2 分钟

考点

  • 剪枝

题解

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
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e2 + 50;
int N, cnt, mp[maxn], q[maxn];
string a, b, c;
bool v[maxn];

bool pd() {
  // 进位，-1代表不确定
  int p = -1;
  for (int i = N - 1; i >= 0; --i) {
    if (~mp[a[i]] && ~mp[b[i]] && ~mp[c[i]]) {
      // 如果三者都有映射，可以进行有效性判断
      int sum = mp[a[i]] + mp[b[i]];
      if (~p) {
        // 如果进位确定
        sum += p;
        p = sum / N, sum %= N;
        // 可行性剪枝：不等于c[i]的映射显然不满足条件
        if (sum != mp[c[i]]) return 0;
        // 可行性剪枝：最高位有进位也不符合条件
        if (!i && p) return 0;
      } else {
        // 进位无非0和1两种情况
        int s1 = sum + 0, s2 = sum + 1;
        // 可行性剪枝：不等于c[i]的映射显然不满足条件
        if ((s1 % N != mp[c[i]]) && (s2 % N != mp[c[i]])) return 0;
        // 可行性剪枝：最高位有进位也不符合条件
        if (!i && (s1 % N == mp[c[i]]) && s1 >= N) return 0;
        if (!i && (s2 % N == mp[c[i]]) && s2 >= N) return 0;
      }
    } else {
      // 三者不确定，进位也置不确定
      p = -1;
    }
  }
  return 1;
}

bool dfs(int now) {
  if (now == N) return 1;
  // 优化搜索顺序：先从大的搜
  for (int i = N - 1; i >= 0; --i) {
    if (v[i]) continue;
    mp[q[now]] = i, v[i] = 1;
    if (pd() && dfs(now + 1)) return 1;
    mp[q[now]] = -1, v[i] = 0;
  }
  return 0;
}

int main() {
  cin >> N >> a >> b >> c;
  // 优化枚举顺序：从低位到高位保存DFS顺序
  for (int i = N - 1; i >= 0; --i) {
    if (!v[a[i]]) q[cnt++] = a[i], v[a[i]] = 1;
    if (!v[b[i]]) q[cnt++] = b[i], v[b[i]] = 1;
    if (!v[c[i]]) q[cnt++] = c[i], v[c[i]] = 1;
  }
  memset(mp, -1, sizeof(mp));
  memset(v, 0, sizeof(v));
  dfs(0);
  for (int i = 'A'; i < 'A' + N; ++i) cout << mp[i] << " ";
  return 0;
}

思路

考虑枚举每个数字的映射时，判断整个算式的可能性；如果在枚举完所有的可能性之后才去判断，会超时。

  • 搜索顺序：算式的运算顺序是低位到高位，所以低位到高位统计依次出现的字母，按这个顺序枚举字母；

    枚举每个字母的可能性映射时，从大到小枚举，即从N-1枚举到0

  • 可行性剪枝：分为三种情况

    1. 当前位，三个字母都存在映射时，且进位p确定

      • 如果(sum = a + b + p) % N != c，剪枝
      • 如果当前是最高位，且还有进位，剪枝

    2. 当前位，三个字母都存在映射时，且进位p不确定

      p无非只有0和1两种可能，按照上面p确定时的规则分类讨论

    3. 当前位，三个字母有部分不确定

      a和b和c三者不作比较，进位p置为不确定