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

题目链接：P1013 [NOIP1998 提高组] 进制位

题意：

著名科学家卢斯为了检查学生对进位制的理解，他给出了如下的一张加法表，表中的字母代表数字。 例如：

$$\def\arraystretch{2} \begin{array}{c||c|c|c|c} \rm + & \kern{.5cm} \rm L \kern{.5cm} & \kern{.5cm} \rm {K} \kern{.5cm} & \kern{.5cm} \rm {V} \kern{.5cm} & \kern{.5cm} \rm {E} \kern{.5cm} \\ \hline\hline \rm L & \rm L & \rm K & \rm V & \rm E \\ \hline \rm K & \rm K & \rm V & \rm E & \rm {KL} \\ \hline \rm V & \rm V & \rm E & \rm {KL} & \rm {KK} \\ \hline \rm E & \rm E & \rm {KL} & \rm {KK} & \rm {KV} \\ \end{array}$$

其含义为：

$L+L=L$，$L+K=K$，$L+V=V$，$L+E=E$

$K+L=K$，$K+K=V$，$K+V=E$，$K+E=KL$

$\cdots$

$E+E=KV$

根据这些规则可推导出：$L=0$，$K=1$，$V=2$，$E=3$。

同时可以确定该表表示的是 $4$ 进制加法。

输入格式：

第一行一个整数 $n$（$3\le n\le9$）表示行数。

以下 $n$ 行，每行包括 $n$ 个字符串，每个字符串间用空格隔开。）

若记 $s_{i,j}$ 表示第 $i$ 行第 $j$ 个字符串，数据保证 $s_{1,1}=\texttt +$，$s_{i,1}=s_{1,i}$，$|s_{i,1}|=1$，$s_{i,1}\ne s_{j,1}$ （$i\ne j$）。

保证至多有一组解。

输出格式：

第一行输出各个字母表示什么数，格式如：L=0 K=1 $\cdots$ 按给出的字母顺序排序。不同字母必须代表不同数字。

第二行输出加法运算是几进制的。

若不可能组成加法表，则应输出 ERROR!。

容易证明，只有 $N$ 进制恰好有 $N$ 个数。

那么我们只要找到有多少数加上当前的数要进位，就可以求出当前的数是多少了

时间复杂度 $\mathcal{O}(n^2)$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)())

int n,ans[15],mp[26]; char s[15][15][3];
bool check(int x, int y)
{
    int sum = ans[x] + ans[y];
    int cur = s[x][y][1] - 'A';
    if(sum >= n - 1 && mp[cur] != 1) return 0;
    if(sum >= n - 1) sum -= n - 1, cur = s[x][y][2] - 'A';
    if(mp[cur] != sum) return 0;
    return 1;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> (s[1][i] + 1);
    for(int i = 2; i <= n; i++)
    {
        int cnt = 0;
        for(int j = 1; j <= n; j++)
        {
            cin >> (s[i][j] + 1);
            cnt += strlen(s[i][j] + 1) >= 2;
        }
        ans[i] = cnt; mp[s[i][1][1] - 'A'] = cnt;
    }
    for(int i = 2; i <= n; i++) 
        for(int j = 2; j <= n; j++)
            if(!check(i, j)) return cout << "ERROR!" << '\n', 0;
    for(int i = 2; i <= n; i++)
        cout << s[i][1][1] << '=' << ans[i] << " \n"[i == n];
    cout << n - 1 << '\n';
    return 0;
}