洛谷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;
}
