[NOIP 1998 提高组] 进制位

知识点

进位制、逻辑推导、完整性校验

解题思路

基数为表头字母数n-1。数值x与全部0到基数-1相加时，恰有x次进位，所以每行两位结果的个数就是该行字母的值。推得映射后检查唯一性及每个格子的标准加法表示。

正确性说明

第x行发生进位当且仅当另一个加数≥B-x，这样的加数共有x个。合法表必满足推导值，因此无需搜索。验证数字构成排列且全部格子等于该映射的和，充分保证是对应进制加法表；任一验证失败便无解。

易错点

按输入表头顺序输出；不能只数进位而跳过全表验证；结果须为无多余前导零的标准表示。

复杂度

时间O(n²)，空间O(n²)。

参考代码（GNU C++17）

#include<bits/stdc++.h>
using namespace std;
int main(){int n;cin>>n;vector<vector<string>>s(n,vector<string>(n));for(auto&r:s)for(auto&x:r)cin>>x;int B=n-1;map<char,int>v;vector<char>digit(B);vector<int>seen(B);bool ok=true;for(int i=1;i<n;i++){int x=0;for(int j=1;j<n;j++)x+=s[i][j].size()==2;if(x>=B||seen[x]++)ok=false;else digit[x]=s[i][0][0];v[s[i][0][0]]=x;}if(ok)for(int i=1;i<n;i++)for(int j=1;j<n;j++){int z=v[s[i][0][0]]+v[s[0][j][0]];string expected;if(z>=B)expected+=digit[z/B];expected+=digit[z%B];if(expected!=s[i][j])ok=false;}if(!ok){cout<<"ERROR!\n";return 0;}for(int i=1;i<n;i++)cout<<s[0][i]<<'='<<v[s[0][i][0]]<<(i==n-1?'\n':' ');cout<<B<<'\n';}