洛谷题目：P1013 [NOIP 1998 提高组] 进制位题解

小亦rocky

1286人浏览 · 2025-03-22 18:20:23

小亦rocky · 2025-03-22 18:20:23 发布

题目传送门：

P1013 [NOIP 1998 提高组] 进制位 - 洛谷 (luogu.com.cn)

前言：

这道题的核心是根据给定的加法表，找出每个字母对应的数字以及加法运算所使用的进制。由于字母和数字的对应关系是一一映射的，且最多只有一组解，我们可以通过枚举所有可能的字母 - 数字映射关系来解决这个问题。下面详细介绍解题思路：

#题目整体思路：

1、数据读取与预处理：

读取输入的加法表，提取出表中的所有字母，并记录字母的所！有！数量。

2、生成可能的映射：

因为每个字母要对应一个不同的数字，且数字范围是从 0 到字母数量减 1，所以可以通过生成这些数字的全排列，来得到所有可能的字母 - 数字映射。

3、验证映射的有效性：

对于每一种可能的映射，根据该映射将加法表中的字母转换为数字，检查加法表中的每一个加法运算是否满足该映射下的加法规则。如果所有运算都满足规则，那么这个映射就是有效的。

4、输出结果：

如果找到有效的映射，输出字母对应的数字以及加法运算的进制；如果遍历完所有可能的映射都没有找到有效的映射，则输出 ERROR!。

##具体步骤：

1、数据读取与预处理：

1.1、读取输入的行数 n ，它代表加法表的规模。

1.2、逐行读取加法表的内容，存储在一个二维数组中。

1.3、从加法表第一行提取出所有出现的字母，存储在一个容器中，并记录字母中的数量 lc。

2、生成所有可能的映射：

1.1、初始化一个长度为 lc 的数组，元素值从 0 到 lc-1 ，代表不同的数字。

1.2、我们使用全排列算法生成这个数组的所有排列。每个排列对应一种字母-数字的映射关系。

3、验证映射的有效性：

对于每一种排列，执行以下操作：

确定定制：进制数等于映射中最大数字 + 1 。

检查加法表：

遍历加法表中的每一个加法运算（即除去第一行和第一列的元素）。
对于每个运算，根据当前映射将运算的两个操作数和结果转换为十进制数。
检查转换后的两个操作数相加是否等于转换后的结果。如果所有运算都满足这个条件，则认为该映射是有效的。

4、输出结果：

1.1、如果找到了有效的映射：按照字母在加法表中出现的顺序，输出每个字母对应的数字，格式为字母=数字，字母之间用空格分隔。

输出加法运算所使用的进制。

1.2、如果遍历完所有排列都没有找到有效的映射，则输出 ERROR！。

###复杂度分析：

1、时间复杂度：

由于需要生成所有可能的数字排列，排列的数量为 $O(k!)$ ，其中 $k$ 是字母的数量。对于每种排列，需要遍历加法表中的所有元素，时间复杂度为 $O(n^{2})$ 。因此总的时间复杂度为 $O(k!\times n^{2})$ 。

· 2、空间复杂度：

主要用于存储加法表、字母到数字的映射和排列，空间复杂度为 $O(n^{2}+k)$ 。

####代码：

#include <bits/stdc++.h>
using namespace std;
int ctd(const string& s, const vector<int>& mapping, int base) {
    int num = 0;
    for (char c : s) {
        num = num * base + mapping[c - 'A'];
    }
    return num;
}
string dlt(int num, const vector<char>& letters, int base) {
    if (num == 0) return string(1, letters[0]);
    string result;
    while (num > 0) {
        result = letters[num % base] + result;
        num /= base;
    }
    return result;
}
int main() {
    int n;
    cin >> n;
    vector<vector<string>> table(n, vector<string>(n));
    vector<char> letters;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            cin >> table[i][j];
            if (i == 0 && j > 0) {
                letters.push_back(table[i][j][0]);
            }
        }
    }
    int lc = letters.size();
    vector<int> map(26);
    vector<int> perm(lc);
    for (int i = 0; i < lc; ++i) {
        perm[i] = i;
    }
    bool found = false;
    do {
        for (int i = 0; i < lc; ++i) {
            map[letters[i] - 'A'] = perm[i];
        }
        int base = *max_element(perm.begin(), perm.end()) + 1;
        bool valid = true;
        for (int i = 1; i < n; ++i) {
            for (int j = 1; j < n; ++j) {
                int left = ctd(table[i][0], map, base);
                int right = ctd(table[0][j], map, base);
                int ex = left + right;
                string as = table[i][j];
                int at = ctd(as, map, base);
                if (ex != at) {
                    valid = false;
                    break;
                }
            }
            if (!valid) break;
        }
        if (valid) {
            found = true;
            for (int i = 0; i < lc; ++i) {
                cout << letters[i] << "=" << map[letters[i] - 'A'];
                if (i < lc - 1) cout << " ";
            }
            cout << endl;	
            cout << base << endl;
            break;
        }
    } while (next_permutation(perm.begin(), perm.end()));
    if (!found) {
        cout << "ERROR!" << endl;
    }
    return 0;
}