进制判断 题解

题目分析

本题要求判断给定的字符串能否作为二进制、八进制、十进制或十六进制数。一个数在某种进制下合法，意味着它的每一位上的字符都不能超过该进制允许的最大数字符号：

• 二进制：只允许 0 和 1，最大字符为 '1'
• 八进制：允许 0~7，最大字符为 '7'
• 十进制：允许 0~9，最大字符为 '9'
• 十六进制：允许 0~9 和 A~F（对应十进制 10~15），最大字符为 'F'

因此，只要找出字符串中出现的最大字符，用它和上述四个界限比较，就可以一次性判断出所有可能的进制。

解题思路

1. 读取整数 N。
2. 循环 N 次，每次读入一个字符串 s。
3. 遍历 s 中的每个字符，找到 ASCII 码值最大的那个字符（记为 max_c）。
   • 由于字符 '0'~'9' 的 ASCII 码小于 'A'~'F'，且 'A'~'F' 内部也是按字母顺序递增，直接比较字符大小即可。
4. 根据 max_c 输出四个判断结果：
   • 是否可能为二进制：max_c <= '1'
   • 是否可能为八进制：max_c <= '7'
   • 是否可能为十进制：max_c <= '9'
   • 是否可能为十六进制：max_c <= 'F'（因为合法字符最大就是 F，无论如何都成立，但严谨比较也无妨）
5. 上述表达式的结果本身就是布尔值，在 C++ 中输出时会转为 1（真）或 0（假），用空格分隔即可。

算法说明

核心算法只有一步：找出字符串中的最大字符。
利用字符的字典序（ASCII 码）直接比较大小，不需要把字符转换成数值。对于任意合法的输入（只含数字和大写字母），这种方法简洁且正确。

边界情况说明：

• 字符串可能以 '0' 开头，这不影响最大字符的判断，所以处理方式和普通字符串一致。
• 输入保证字符串非空，且长度不超过 10，因此不必担心性能问题。
• 对于任何字符串，其最大字符一定 ≤ 'F'，因此十六进制总是可能的？需注意输入中字母只可能是 A~F，所以十六进制判断恒为真，但题目逻辑仍可统一处理。

时间复杂度分析

• 对于每个字符串，需要遍历所有字符找最大值，设字符串长度为 L（L ≤ 10），复杂度为 O(L)。
• 总共 N 个字符串（N ≤ 1000），整体时间复杂度为 O(N * L)，在最坏情况下运算次数约为 1000 * 10 = 10^4 次，远小于时间限制 1000ms，可以轻松通过。

空间复杂度方面，只需存储当前字符串和少量变量，为 O(L)，同样非常低。

参考代码

下面是 C++ 实现代码，并附有详细注释。

cpp
复制
1#include <iostream>
2using namespace std;
3
4int main() {
5    int n;
6    cin >> n;                     // 读入数字个数
7    while (n--) {                 // 循环 n 次
8        string s;
9        cin >> s;                 // 读入当前字符串
10        char max_c = '0';         // 初始化最大字符为 '0'
11        for (char c : s)         // 遍历每个字符
12            if (c > max_c)        // 更新最大值
13                max_c = c;
14        // 依次输出是否为二进制、八进制、十进制、十六进制
15        cout << (max_c <= '1') << " "
16             << (max_c <= '7') << " "
17             << (max_c <= '9') << " "
18             << (max_c <= 'F') << endl;
19    }
20    return 0;
21}

代码解释

• max_c 初始化为 '0'，因为所有合法字符都不小于 '0'。
• 范围 for 循环逐个检查字符，如果发现更大的字符就更新 max_c。
• 比较运算符 <= 直接作用于字符，C++ 会使用它们的 ASCII 码进行比较。
• (max_c <= '1') 等表达式的结果为 bool 类型，输出时自动转换为 1 或 0，满足题目要求。
• 四个结果之间用空格隔开，每行结束后输出换行符。

这样，我们仅用一次遍历就完成了所有进制的判断，代码简洁高效，适合竞赛场景。