题注
- 题目传送门
- 这篇题解其实是上一篇题解(Llf0703 同志)证明过程的完善(
其实就是思路一样了啦),来让入门者或追求严谨者对证明过程更加了解。
题目分析
- \(3 \leq n \leq9\),也即数字的个数 \(N \leq 8\)。
- 研究样例发现,\(N\) 与进制 \(R\),以及数字对应两位数个数 \(M\) 与数字本身 \(S\) 具有
的关系,下面给出具体证明。
证明
1. 证:\(N = R\)。
- 由题意可知,每个字母代表着不同的数字,所以 \(R \geq N\) 必然成立。
- 设加法表中每个数字分别为 \(a_i, i \in [0, N - 1]\)。
- 若 \(R > N\),则存在有 \(k \in [0, R - 1]\),满足 \(k \ne a_i, i \in [0, N - 1]\)。
- 因为在 \(R\) 进制下,二数相加最大可以达到 \(T\),而
- 其中 \(r = R - 2\)。
- 例:在 3 进制下,\(T = (2)_3 + (2)_3 = (11)_3\)。
- 所以一定会出现加法表中两数字相加等于 \(k\) 或等于 \((1k)_R\) 的情况,或者 \(k = 1\) 时加和等于 \((1x)_R, x \in [0, R - 2]\) 的情况,使得 \(k\) 出现在加法表上,这与 \(k \ne a_i, i \in [0, N - 1]\) 相矛盾,因此 \(R \ngtr N\)。
- 而由题目分析可知,\(N = R\) 是可以成立的。
- 因此,在加法表合法的情况下,\(N \equiv R\),证毕。
2. 证:\(M = S\)。
- 由 1. 可知,\(N = R\),且加法表中最高为两位数。
- 因为只有在 \(S + x \geq R\) 时,\((S)_R + (x)_R\) 才能为两位数,且 \(x\) 为 \(R\) 进制下的数字,则可列出以下的不等方程组
- 解得方程解集为 \(x \in [R - S, R - 1]\)。
- 所以 \(M = (R - 1) - (R - S) + 1 = S\),证毕。
结论
- 因此,题目分析中的两个猜想都成立,我们以此为基础打出代码。
- 先计算出每个字母所代表的数字(通过猜想 2),然后验证加法表是否匹配即可。
AC代码
#include <bits/stdc++.h>
using namespace std;
int n, S[13], mp[13];
char str[13][13][3];
bool add(int a, int b) {
int sum = S[a] + S[b], ch = str[a][b][0] - 'A' + 1; //计算加和,取第一位
if (sum >= n - 1) { //有进位时,高位一定为1
if (strlen(str[a][b]) != 2 || mp[1] != ch) {
return 0; //若str[a][b]不为两位数或者第一位不为1,返回错误
} else {
sum -= n - 1; //减掉高位,取低位
ch = str[a][b][1] - 'A' + 1;
}
}
if (mp[sum] != ch) {
return 0; //不匹配则返回错误
}
return 1;
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%s", str[1][i]);
}
int M;
bool flag = 0;
for (int i = 2; i <= n; i++) {
M = 0;
for (int l = 1; l <= n; l++) {
scanf("%s", str[i][l]);
if (strlen(str[i][l]) > 1) {
M++; //计算两位数个数
}
}
S[i] = M; //记录字母对应数字
if (flag == 0 && mp[M]) { //查重
flag = 1;
}
mp[M] = str[i][1][0] - 'A' + 1; //记录数字对应字母以查重
}
if (flag) { //重复错误
printf("ERROR!");
return 0;
}
for (int i = 2; i <= n; i++) {
for (int l = 2; l <= n; l++) {
if (add(i, l) == 0) { //加起来检验加法表是否匹配
printf("ERROR!"); //不匹配错误
return 0;
}
}
}
for (int i = 2; i <= n; i++) {
printf("%c=%d ", str[i][1][0], S[i]);
}
printf("\n%d", n - 1);
return 0;
}
标签:进制,int,题解,P1013,mp,str,加法,数字
From: https://www.cnblogs.com/iloveoi/p/18037701