当前位置：首页 > ds >正文

P1013 [NOIP 1998 提高组] 进制位

ds 2025/7/26 23:59:40

题目描述

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

+LKVELLKVEKKVEKLVVEKLKKEEKLKKKV

其含义为：

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≤n≤9）表示行数。

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

若记 si,j 表示第 i 行第 j 个字符串，数据保证 s1,1=+，si,1=s1,i，∣si,1∣=1，si,1=sj,1 （i=j）。

保证至多有一组解。

输出格式

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

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

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

输入输出样例

输入 #1

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

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

说明/提示

NOIP1998 提高组第三题

题目理解

这道题目考察的是进制转换和逻辑推理能力。题目给出一个加法表的一部分，要求我们确定每个字母代表的数字以及这个加法表所使用的进制。

题目重述

给定一个N×N的表格，第一行和第一列是大写字母（代表数字），其余格子是两个字母的组合，表示这两个字母对应数字的和。要求：

确定每个字母代表的数字（0到N-2）
确定加法表使用的进制（N-1进制）
验证表格的正确性

关键点分析

字母与数字的映射：每个字母对应一个唯一的数字
进制确定：表格大小为N×N，则进制为N-1
加法验证：需要验证所有给出的加法结果是否正确

解题思路

基本思路

确定进制：表格有N行N列，则进制为N-1
建立方程：根据加法表建立字母间的数值关系
求解映射：通过逻辑推理确定每个字母对应的数字
验证结果：检查所有加法关系是否成立

解决步骤

预处理输入：读取表格数据，统计所有出现的字母
确定进制：表格大小N决定进制为N-1
建立关系：从简单的加法关系开始推理（如A+A=某个两位数）
逐步推导：利用已知关系推导其他字母的值
全面验证：确保所有加法关系都成立

代码实现

cpp

#include <iostream>
#include <vector>
#include <map>
#include <string>
using namespace std;int main() {int N;cin >> N;vector<vector<string>> table(N, vector<string>(N));// 读取输入表格for (int i = 0; i < N; ++i) {for (int j = 0; j < N; ++j) {cin >> table[i][j];}}// 确定进制int base = N - 1;// 收集所有字母vector<char> letters;for (int j = 1; j < N; ++j) {letters.push_back(table[0][j][0]);}// 建立字母到数字的映射map<char, int> charToNum;// 首先处理A + A的情况（第一行第一列都是A）char firstChar = table[1][0][0];string sumAA = table[1][1];// 情况1：A + A = 1位数if (sumAA.size() == 1) {charToNum[firstChar] = 0; // A=0}// 情况2：A + A = 两位数else {charToNum[firstChar] = 1; // A=1}// 处理其他字母的值// 从B开始（假设第二列是B）if (N > 2) {char secondChar = table[0][2][0];string sumAB = table[1][2];if (sumAB.size() == 1) {charToNum[secondChar] = sumAB[0] - 'A' + 1;} else {// 根据进位情况处理int value = (sumAB[0] - 'A' + 1) * base + (sumAB[1] - 'A' + 1);charToNum[secondChar] = value - charToNum[firstChar];}}// 继续推导其他字母的值...// 这里需要根据具体输入实现更完整的推导逻辑// 验证所有加法关系bool valid = true;for (int i = 1; i < N && valid; ++i) {for (int j = 1; j < N && valid; ++j) {char a = table[i][0][0];char b = table[0][j][0];string sum = table[i][j];int numA = charToNum[a];int numB = charToNum[b];int realSum = numA + numB;// 转换为base进制string expectedSum;if (realSum < base) {expectedSum += (char)('A' + realSum - 1);} else {expectedSum += (char)('A' + realSum/base - 1);expectedSum += (char)('A' + realSum%base - 1);}if (sum != expectedSum) {valid = false;}}}// 输出结果if (valid) {for (char c : letters) {cout << c << "=" << charToNum[c] << " ";}cout << endl << base << endl;} else {cout << "ERROR!" << endl;}return 0;
}