进制转换 题解

题目分析

题目要求我们对 $N$ 个不同进制的数进行转换，将它们从各自的 $K$ 进制转换为十进制。输入包含 $N$ 行，每行是一个整数 $K$ 和一个用大写字母及数字表示的 $K$ 进制数。$K$ 的范围在 $2$ 到 $16$ 之间，数字的长度不超过 $9$ 位，且不会以 $0$ 开头。输出为每一行对应的十进制数。

这是一道典型的任意进制转十进制问题，核心是根据数位的权值进行求和。题目已经给出了转换公式和两个例子，例如八进制 1362 转为十进制的过程：

对于超过十进制的部分（如十六进制），字母 A~F 分别代表 10~15，在计算时需要将字符转换为对应的数值。

数据范围较小，最多 $1000$ 个数，每个数长度不超过 $9$，$K$ 不超过 $16$，因此即使 $9$ 位的 $16$ 进制数，转换成十进制最大约为：

这个值超出了 int 的表示范围（一般为 $2.1\times10^9$），因此需要使用 long long 存储结果。

解题思路

对于每一个输入的数，按照按权展开求和的方法进行转换：

1. 将数字字符串的每一位从右向左依次编号，最右边为第 $0$ 位，权值为 $K^0=1$，向左权值依次乘以 $K$。
2. 将每一位的字符转换为对应的数值：
   • 如果是数字字符 '0' ~ '9'，数值为 c - '0'；
   • 如果是大写字母 'A' ~ 'F'（本题中 K 最大为 16，所以只到 F），数值为 c - 'A' + 10。
3. 将得到的数值乘以当前位的权值，累加到结果中。
4. 处理完所有位之后，结果即为对应的十进制数。

我们可以编写一个转换函数，输入进制 k 和数字字符串，返回 long long 类型的十进制值。主程序读取 $N$，然后循环处理每一行，调用转换函数并输出结果。

算法说明

字符转数值函数 trans_digit

cpp
复制
1int trans_digit(int k, char c) {
2    if (c <= '9')
3        return (c - '0');
4    return (c - 'A' + 10);
5}

该函数接收进制 k 和一个字符 c，判断 c 是否为数字字符（'0'~'9'）。如果是，直接返回 c - '0' 对应的整数（0~9）。否则，输入保证为大写字母，因此返回 c - 'A' + 10，对应 10~15。虽然参数 k 在此并未使用，但保留它可以方便扩展（比如检查合法性）。

进制转换函数 trans

cpp
复制
1long long trans(int k, char str[]) {
2    int l = strlen(str);
3    long long res = 0, pw = 1;
4    for (int i = l - 1; i >= 0; i--) {
5        res += pw * trans_digit(k, str[i]);
6        pw *= k;
7    }
8    return res;
9}

• 先获取字符串长度 l。
• 初始化结果 res 为 0，当前位的权值 pw 为 1（代表 $K^0$）。
• 从字符串末尾（最低位）开始向前遍历，每处理一位：
  • 将该位字符转换为数值，乘以当前权值 pw，并累加到 res。
  • 将 pw 乘以 k，更新为下一位的权值（相当于 $K$ 的幂次增加 1）。
• 遍历结束，返回累加结果。

主函数 main

cpp
复制
1int main() {
2    int n = 0;
3    cin >> n;
4    for (int t = 0; t < n; t++) {
5        int k = 0;
6        char str[10];
7        cin >> k >> str;
8        cout << trans(k, str) << endl;
9    }
10    return 0;
11}

• 读取整数 n，表示有 n 个数需要转换。
• 循环 n 次，每次读取进制 k 和数字字符串 str，直接输出转换后的十进制结果。

时间复杂度分析

对于每个 $K$ 进制数，设其长度为 $L$（$L \le 9$）。转换过程需要遍历字符串一次，时间复杂度为 $O(L)$。总共有 $N$ 个数，最多 $N \le 1000$，因此总时间复杂度为 $O(N \cdot L)$，在最坏情况下约为 $1000 \times 9 = 9000$ 次操作，可以轻松在规定时间内通过。

空间上仅使用了几个变量和一个字符数组，空间复杂度为 $O(L)$，即常数级别。

参考代码及解释

以下是完整的参考代码（基于题目给出代码略作整理，修正了头文件中的拼写错误 cstring -> cstring 应改为 cstring 或 cstring？实际上应该是 #include <cstring> 或 <cstring>？在标准 C++ 中字符串操作常用 #include <cstring> 以使用 strlen。题目中给的是 #include <cstring> 但写成了cstring？但无伤大雅，下面给出规范写法）：

cpp
复制
1#include <iostream>
2#include <cstring>   // 提供 strlen 函数
3using namespace std;
4
5// 将字符转换为对应的数值
6int trans_digit(int k, char c) {
7    if (c <= '9')
8        return (c - '0');      // 数字字符
9    return (c - 'A' + 10);     // 大写字母 A~F
10}
11
12// K进制字符串转十进制数值
13long long trans(int k, char str[]) {
14    int l = strlen(str);
15    long long res = 0, pw = 1;    // pw 表示当前位的权值，初始为 K^0 = 1
16    for (int i = l - 1; i >= 0; i--) {  // 从低位向高位遍历
17        res += pw * trans_digit(k, str[i]);
18        pw *= k;                 // 权值变为下一个高位对应的 K 次幂
19    }
20    return res;
21}
22
23int main() {
24    int n;
25    cin >> n;
26    while (n--) {
27        int k;
28        char str[10];
29        cin >> k >> str;
30        cout << trans(k, str) << endl;
31    }
32    return 0;
33}

代码解惑：

• 头文件 <cstring> 包含了 C 风格的字符串处理函数，这里使用 strlen 获取字符串长度。
• 转换时直接从字符串末尾开始遍历，利用 pw 变量避免每次计算幂次，更加高效。
• 结果使用 long long 类型，避免较大数据溢出。

通过以上方法，即可顺利完成任意 2~16 进制数到十进制的转换。