P1013 [NOIP1998 提高组] 进制位 题解

· · 题解

0x00 前言：

（本人第一篇绿题题解，若有不足请诸位多多包涵）

为了方便描述，本文中一些词汇用以下变量代替：

  1. 加法表第一行数字个数：N
  2. 加法表中的进制：R
  3. 加法表中行、列数：n
  4. 加法表中第 i 列上的二位数（KL、KK \dots ）的个数：s_i,s_{i+1}, \dots ,s_{n-1}
  5. 加法表中第一行 i 列上字母的值，以及第 i 行第一列上字母的值（L、K、V、E \dots）：a_i, a_{i+1}, \dots ,a_{n-1}

0x01 题目大意：

根据给出的加法表，推理出进制和各个数字，若数据不能构成加法表，输出 ERROR!

0x02 具体分析

一、对于 R 的确定：通过观察，可以发现一行中，经过每 N-1 列就要换一次行（可以理解成进一次位），因此我们很容易能注意到 R=n-1=N 。又因为 n >= 3，所以一定存在 a_1 和 a_2，而当a_1 和 a_2取最小，即a_1 = 0, a_2 = 1时，一定会出现0+1=1（也就是发生了一次进位），以此类推可知，最多发生 n-1 次进位，故 R=n-1=N，结论成立。

二、对于 a_i, a_{i+1}, \dots ,a_{n-1} 的确定：通过结合样例观察，我们可以注意到 a_i = s_i。又a_i, a_{i+1}, \dots ,a_{n-1} 从 0 到 n-1，所以该结论显然成立。

三、对于判断能都组成加法表：通过一、二的分析，我们可以将R 和 a_i, a_{i+1}, \dots ,a_{n-1} 确定，因此我们就可以借此反推输入是否成立。例如对于这组数据：

5
+ A B C D
A A B C BC
B B C BC BA
C C C BA BB
D D BA BB BC

我们可以推出 R = 4，A=0,B=1,C=3,D=4\ 所以，A + D = 0 + 4 = 4 \ 因为，在 4 进制中 4 = 10\ 所以，A+D = BA\ 然而，在图中我们可以发现：A+D=BC=13 , 矛盾.\ 因此，这组数据不能组成加法表，应该输出 ERROR!

0x03 代码实现

分析完题意后，代码就好实现了。\ 大致可以分为三个板块：

最后，贴出代码供大家参考

#include <bits/stdc++.h>
using namespace std;
int n,r,t,ss;
string s[100][100];
string ch[100];
int p[100];
unordered_map<string,int> mp; // 用哈希存 字母 与 值的对应关系
unordered_map<int,char> mp2; // 用哈希存 值 与 字母的对应关系

// 十进制转R进制
void f(int num){
    if (num <= 0) return;
    f(num / r);
    ss = ss * 10 + num % r;
}
// R进制加法
int add(int a, int b){
    ss =0;
    int res = a + b;
    f(res);
    res = ss;
    return res;
}
// 判断是否能组成加法表
bool check(){
    for (int i = 2; i<= n; i++){
        for (int j =2; j <= n; j++){
            if (s[i][j].size() == 1){ // 对于一位的情况
                int x=mp[s[i][1]];
                int y=mp[s[1][j]];
                int exp = add(x,y);
                if (exp != mp[s[i][j]]) return 0;
            }
            else{ // 对于两位的情况
                string tmp = "", exptmp = "";
                int x=mp[s[i][1]];
                int y=mp[s[1][j]];
                int exp = add(x,y);
                exptmp = to_string(exp);
                for (auto u : exptmp){
                    tmp += mp2[u-'0'];
                }
                if (tmp != s[i][j]) return 0;
            }
        }
    }
    return 1;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= n; j++){
            cin >> s[i][j];
            if (j >= 2) ch[++t] = s[1][j]; // 将字母存起来
        }
    }
    // 求 R
    r = n-1;
    // 求字母对应的数字
    for (int i = 2; i <= n; i++){
        int cnt = 0;
        for (int j = 1; j<= n; j++){
            if (s[i][j].size() == 2) cnt++;
        }
        p[i-1] = cnt;

    }
    /*
    规律：
    1.每一列有几个二位字母就是每一列的字母的值
    2.进制数R = n-1
    */

    // 构造对应关系
    for (int i = 1; i< n; i++){
        mp[ch[i]] = p[i];
        mp2[p[i]] = ch[i][0];
    }

    // 输出
    if (check()){
        for (int i = 1; i< n; i++) cout << ch[i] << "=" << p[i] << ' ';
        cout << endl << r << endl;
    }
    else cout << "ERROR!" << endl;
    return 0;
}