GESP 题解库 / 3 级题解 / [GESP202309 三级] 进制判断 · 第 20 / 28 题
GESP202309 三级 · B3868 · 入门

进制判断

判断每个数字串是否可能表示二进制、八进制、十进制、十六进制数,输出 4 个 0/1。

📊
N ≤ 1000
数据组数
🔤
长度 ≤ 10
字符串长度
⚡
O(N × L)
时间复杂度
🎯
最大数字判据
核心算法
01
题目拆解
把题目拆成一块块,看清全貌

📝 题目原文

N 进制数逢 N 进一。十六进制用 A ~ F 表示 10 ~ 15。

给定 N 个由数字和大写字母组成的字符串(可能以 0 开头),分别判断它们是否可能表示二进制、八进制、十进制、十六进制数。输出 4 个 0/1,1 表示可能、0 表示不可能。

例如 15A6F 只可能是十六进制,输出 0 0 0 1;1011 四种都可能,输出 1 1 1 1。

💡
人话翻译:一个 B 进制数里,每一位数字都必须小于 B。所以只要找出这个串里最大的那个数字,看它是否小于 2 / 8 / 10 / 16 就行了。不用真的去转换进制。

🔍 关键词提取

进制基础最大数字判据字符转数值四路判断

已知条件

项目说明
输入第一行 N;随后 N 行每行一个字符串
输出每行 4 个 0/1,分别对应 2、8、10、16 进制
数据范围N ≤ 1000,串长 ≤ 10
字符集数字与大写字母,可能以 0 开头
字母含义A = 10、B = 11、…、F = 15(十六进制惯例)

需要解决的问题

02
思维导图
整理解题思路的全貌
🔢 只看最大数字
📥 读入
N 个字符串
逐个独立判断
可能以 0 开头(无影响)
长度 ≤ 10
🔍 求最大数字
'0'~'9' → 0~9
'A'~'Z' → 10~35
遍历取最大值 maxDigit
O(L)
✅ 四路判断
2 进制:maxDigit < 2
8 进制:maxDigit < 8
10 进制:maxDigit < 10
16 进制:maxDigit < 16
⚠️ 易错点
误以为要真的转换
字母转换公式写错
输出顺序搞反
十六进制基数写成 15
03
样例手算推导
样例 6 个字符串逐个判断

🧮 逐串求最大数字并判断

我们把两组样例里的 6 个字符串都算一遍。先明确映射规则:'0' → 0,'9' → 9,'A' → 10,'F' → 15,'G' → 16。

1
15A6F

各字符数值:1、5、10、6、15

最大 = 15

2 进制:15 < 2?否

8 进制:15 < 8?否

10 进制:15 < 10?否

16 进制:15 < 16?是

输出 0 0 0 1

2
1011

各字符数值:1、0、1、1

最大 = 1

1 < 2 ✅、1 < 8 ✅、1 < 10 ✅、1 < 16 ✅

输出 1 1 1 1

3
FF

各字符数值:15、15

最大 = 15

只有 16 进制满足(15 < 16)

输出 0 0 0 1

4
GG

各字符数值:16、16

最大 = 16

16 < 16?不成立(必须严格小于基数)

输出 0 0 0 0(连十六进制都不行)

📊 汇总表

字符串最大数字2 进制8 进制10 进制16 进制
15A6F15(F)0001
101111111
123456770111
1234567880011
FF150001
GG160000
🔑
两个关键点:① 判据是"严格小于"基数——所以 GG 的最大数字是 16,而 16 进制要求每位 < 16,于是连十六进制都不成立;② 二进制的基础判据是 < 2,所以只有由 0 和 1 组成的串才可能是二进制数。
04
解法对比
最大数字判据 vs 逐位尝试转换

⚔️ 解法对比

🟢 最大数字判据(推荐) 推荐

求出串中最大数字,与 2、8、10、16 逐个比较

  • 时间 O(N × L)
  • 只需一次遍历
  • 不需要任何进制转换
  • 代码 12 行
💡
为什么等价:"该串是合法的 B 进制数"⇔"每一位数字都 < B"⇔"最大数字 < B"。三种说法完全等价,取最好算的那个。

🟠 真的去转换进制

把字符串按各进制尝试转换,看是否溢出或报错

  • 需要处理溢出判断
  • 代码复杂得多
  • 结果还受数值范围影响
  • 完全不必要
⚠️
注意:题目问的是"是否可能表示",重点在数字位是否合法,与数值大小无关。比如 1111111111(十个 1)远超 int,但它确实可能是二进制数。

📈 性能对比

方案代码量是否需转换
最大数字判据约 12 行不需要
真实转换约 30 行以上需要
05
算法流程图
求最大数字 → 四路比较
开始读入 N处理每一个字符串 s遍历 s,把每个字符转成数值,记录最大值 maxD依次比较:maxD < 2、< 8、< 10、< 16输出 4 个 0/1(用空格分隔)N 个字符串都处理完了吗?结束还有字符串 → 继续判断
← 左右滑动查看完整流程图
06
动手算一算
自己输入数据试试看

🔢 进制可能性判断器

每行输入一个由数字和大写字母组成的串,程序会给出它在 2/8/10/16 进制下是否可能。

结果会显示在这里

点按钮开始 →

07
代码精讲
逐段拆解,彻底搞懂

💻 完整 C++ 代码

#include <bits/stdc++.h>
using namespace std;

// 字符 -> 数值:'0'~'9' 为 0~9,'A'~'Z' 为 10~35
int charToVal(char c) {
    if (c >= '0' && c <= '9') return c - '0';
    return c - 'A' + 10;
}

int main() {
    int N;
    scanf("%d", &N);

    char s[20];
    while (N--) {
        scanf("%s", s);

        int maxD = 0;
        for (int i = 0; s[i]; i++) {
            int v = charToVal(s[i]);
            if (v > maxD) maxD = v;
        }

        // 依次判断 2、8、10、16 进制是否可能
        printf("%d %d %d %d\n",
               maxD < 2  ? 1 : 0,
               maxD < 8  ? 1 : 0,
               maxD < 10 ? 1 : 0,
               maxD < 16 ? 1 : 0);
    }
    return 0;
}
🔑
判据为什么是"严格小于"?B 进制里可用的数字是 0 ~ B−1,共 B 个。所以每一位都必须 ≤ B − 1,也就是 < B。例如八进制只能用 0 ~ 7,出现 8 就不合法。

📖 关键几行怎么看

代码作用为什么这样写
c - '0'数字字符转数值'0' 的 ASCII 是 48,相减即得数值
c - 'A' + 10字母转数值A 对应 10,所以减 'A' 后加 10
maxD < 2 ? 1 : 0三目判断一行输出一个结论,简洁
for (int i = 0; s[i]; i++)遍历字符串以 '\0' 为结束标志,字符串题常用写法
⚠️
三个坑:① 把十六进制基数写成 15(应该是 16);② 输出顺序不是"二进制、八进制、十进制、十六进制";③ 用 <= 代替 <,会把 GG(最大数字 16)误判成合法十六进制数。
08
边界测试 & 易错点
把坑都踩一遍,考试不翻车

🧪 边界测试用例表

写完程序后,用这些数据自查一遍:

输入答案考察点
15A6F0 0 0 1含 F(15),只可能是十六进制
10111 1 1 1全是 0/1,四种都可能
12345670 1 1 1最大 7,八进制起可能
123456780 0 1 1最大 8,八进制不行了
FF0 0 0 1最大 15
GG0 0 0 0最大 16,连十六进制都不满足(要求 < 16)
✅
自查清单:① 拿到的是最大数字吗?② 比较用的是严格小于吗?③ 四个输出顺序对吗?

🚨 易错点清单

⚠️
边界写成 <=:必须严格小于。GG 的最大数字是 16,16 < 16 不成立,所以输出 0 0 0 0。
⚠️
字母转换公式写错:是 c - 'A' + 10,漏掉 +10 会把 F 算成 5。
⚠️
输出顺序记错:题目要求按 二进制、八进制、十进制、十六进制 的顺序。
09
复杂度分析
算算效率怎么样

📊 复杂度四宫格

时间复杂度
O(N × L)
空间复杂度
O(L)
N 最大
1000
L 最大
10

时间怎么算的?

空间都用在哪?

只需要存当前字符串(长度 ≤ 10)。

✅ 最多 1 万次字符处理,瞬间完成。

10
知识拓展
学一道题,会一类题

🔗 常用技巧小抄

// 字符与数值互转(进制题必备)
int charToVal(char c) {
    if (c >= '0' && c <= '9') return c - '0';
    return c - 'A' + 10;          // A=10 … Z=35
}
char valToChar(int v) {
    if (v < 10) return char('0' + v);
    return char('A' + v - 10);
}

// 判断一个串在 B 进制下是否合法
bool validInBase(const string &s, int B) {
    for (char c : s) if (charToVal(c) >= B) return false;
    return true;
}

// 任意进制转十进制(了解即可)
long long toDecimal(const string &s, int B) {
    long long r = 0;
    for (char c : s) r = r * B + charToVal(c);
    return r;
}

🌟 举一反三

把这道题用到的基本功拆出来,它们能迁移到很多同类问题上。

能力点本题怎么用还能迁移到
字符与数值互转数字/字母统一映射到数值所有进制相关题目
"边界即判据"用最大数字判断进制合法性进制判断、编码校验题
严格小于合法数字范围是 0 ~ B−1所有涉及"取值范围"的判断
🌟
思考题:如果题目改成"判断字符串是否恰好是某进制的规范表示"(比如不允许前导零、且首位不能是 0),判据要加什么条件?(提示:再加一条"如果长度 > 1 则首位不能是 '0'"即可。)