← INDEX DOCUMENT

【NOIP1998 提高】 进制位

题目

题目背景

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

题目描述

例如：

1
2
3
4
5
+    L    K      V      E
L    L    K      V      E
K    K    V      E     KL
V    V    E     KL     KK
E    E    KL    KK     KV

其含义为：

(L+L=L)，(L+K=K)，(L+V=V)，(L+E=E)

(K+L=K)，(K+K=V)，(K+V=E)，(K+E=KL)

⋯

(E+E=KV)

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

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

输入格式

第一行一个整数 (n(3 \le n \le 9))
以下 (n) 行，每行包括 (n) 个字符串，每个字符串间用空格隔开。
若记 (s_{i,j})表示第 (i) 行第 (j) 个字符串，数据保证 (s_{1,1}=+) , (s_{i,1}=s_{1,i}) , (|s_{i,1}=1|) , (s_{i,1} \neq s_{j,1} (i \neq j))
保证至多有一组解。

输出格式

第一行输出各个字母表示什么数，格式如：(L=0) (K=1 ……)
按给出的字母顺序排序。不同字母必须代表不同数字。
第二行输出加法运算是几进制的。
若不可能组成加法表，则应输出 (ERROR!)。

输入输出样例

输入 #1

1
2
3
4
5
6
5
+ L K V E
L L K V E
K K V E KL
V V E KL KK
E E KL KK KV

输出 #1

1
2
L=0 K=1 V=2 E=3
4

思路

进制数？

一个显然的想法是，字母所代表的数字不重复，所以进制数(l)一定大于等于字母个数(n-1),即(l \geq n-1)
那么到底是几进制？可以考虑枚举，注意数据范围((3 \leq n \leq 9))，如果可以枚举进制数(l)，判断在每个进制下的加法表是否合法，判断加法表考虑一下暴力 (O(n^2)) ，复杂度完全可以接受。
那最大要枚举到多少？最大即为最大的数 ((n-1)*2+1)
最终可得 (l) 枚举的范围 (n-1 \leq l \leq 2n-1) （显然，如果更大，结果是一样的）

每个字母所代表的？

我们先尝试构建个特殊的加法表，设 (a_{i,j}) 所代表的数字为 (digit_{i,j}) ，构造一个字母表 ((digit_{i_1,1} \leq digit_{i_2,1}) , 且 (i_1 \leq i_2),(l=10) )，看看能否找找其中的规律？

1
2
3
4
5
6
7
8
+ 0 1 2 3 4 5 6
0 0 1 2 3 4 5 6
1 1 2 3 4 5 6 7
2 2 3 4 5 6 7 8
3 3 4 5 6 7 8 9
4 4 5 6 7 8 9 10
5 5 6 7 8 9 10 11
6 6 7 8 9 10 11 12

观察每个斜线上的数字，可以发现，在 (2 \leq i,j \leq n) 时，每个数字出现的次数 (cnt) 减去 (1) 就是当前数字。
我们得到了一个特殊的情况，那么该种情况能否向外推？
试着去手玩一下，任意交换两个数字，保证加法表成立，只需要将对应的行与列都交换。
例如将以下加法表 第一个 第二个数字交换

1
2
3
4
5
6
7
8
9
10
11
12
+ 0 1 2 3
0 0 1 2 3
1 1 2 3 4
2 2 3 4 5
3 3 4 5 6
| |
V V
+ 1 0 2 3
1 2 1 3 4 
0 1 0 2 3 
2 3 2 4 5
3 4 3 5 6

显然成立
因为只是交换了数字的位置，是整行整列的交换，而没有直接改变数字，所以每个数字出现的次数(cnt)不变。
（原谅我想不出更加严谨的证明，只能“显然”一下了）
那么扩展到字母，同理，可以得出每个字母代表的数字为其出现的次数 (cnt-1)

实现

对于处理每个字母出现的次数，可以采用 (map) ，可以转为 (ASCII) 码开数组，这里我采用 (map)
先记录次数，再按 (l) 枚举，判断合法性即可

CODE

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <bits/stdc++.h>
using namespace std;
string a[10][10];
map<char,int>cnt;
int main(){
	int n;
	int ans=0;
	cin>>n;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++) cin>>a[i][j];
	for(int i=2;i<=n;i++)
		for(int j=2;j<=n;j++){
			if(a[i][j].size()==1)
			cnt[a[i][j][0]]++;
		}
	for(int l=n-1;l<=10;l++){
		bool f=1;//标记 方案是否合法
		for(int i=2;i<=n;i++){
			for(int j=2;j<=n;j++){
				int sum=0;
				for(int k=a[i][j].size()-1;k>=0;k--){
					sum+=(cnt[a[i][j][k]]-1)*pow(l,a[i][j].size()-k-1);//l进制下的数字转换为10进制 方便比较
				}
				if(sum!=(cnt[a[i][1][0]]-1+cnt[a[1][j][0]]-1)){f=0; break;}//方案非法 可以枚举下一个进制了
			}
			if(!f) break;
		}
		if(!f) continue;
		ans=l;
		break;
	}
	if(ans==0){
		puts("ERROR!");
	}else{
		for(int i=2;i<=n;i++) cout<<a[1][i][0]<<'='<<cnt[a[1][i][0]]-1<<' ';
		puts("");
		cout<<ans<<endl;
	}
}