蓝桥杯练习系统基础练习里的“BASIC-12 十六进制转八进制”是我带过好几届同学刷题时绕不开的一道题。放在“基础练习”这个标签下它看上去平平无奇打开题目界面描述只有短短几行很多人心里先松一口气进制转换不是送分题吗结果一提交问题就来了——要么用错类型直接溢出要么写出来的代码只够应付小数据要么被输出的前导0折腾到怀疑人生。这道题真正想考察的不是你会不会查表而是你对进制本质的理解以及面对“数据范围远超常规”时敢不敢跳出惯性思维。我打算把这道题的完整拆解、实测代码和踩坑记录都整理出来给正在刷题或者准备比赛的同学一份能直接用的参考。1. 题目到底在考什么拆解 BASIC-12 的隐含要求1.1 从题目描述说起题目内容很简单输入一个十进制整数 n表示接下来有 n 行每行是一个十六进制数要求把每个十六进制数转换成对应的八进制数输出。单看这两句话你会觉得这是蓝桥杯入门级别的题毕竟进制转换在人教版教材里就有连计算机基础课都会讲。但注意最后一句话“每个十六进制数长度不超过 100000 位。”这句话才是整个题目的题眼。如果它只要求输入几个正常的十六进制数比如“A5F”或者“1A2B3C”那用Long.parseLong或者strtol都能轻松应付。可 100000 位是什么概念就算全是最小的十六进制位它的数值范围也远远超出了任何 64 位整数能表示的上限64位整数最多也就表示 16 个十六进制位。这意味着你根本没机会把这个数读进一个整数变量里只能把它当字符串处理。这一下题目就从“会不会查表”升级成了“有没有处理大数的思维”。1.2 隐藏的深水区为什么不能用常规进制转换函数很多同学的第一反应是找现成函数C里没有直接把十六进制字符串转成八进制字符串的标准库函数只有stoi、stol这类先转成整数的东西而它们到 64 位就到头了。Java里虽然有个BigInteger可以把任意长度的十六进制字符串转成十进制整数再转八进制但这题放在“基础练习”里目的绝不是让你打卡式秒过——用BigInteger当然能过可它恰恰避开了题目真正想让你练的东西手工处理大数、字符串、位模式之间的关系。而且BigInteger也不是完全没有坑100000 位十六进制换算成二进制大约是 400000 位也就是 50KB 级别的整数BigInteger能处理但如果你是在 C/C 环境里考试根本没有这个可依赖的现成大数类所以手写算法是必须掌握的基本功。注意蓝桥杯的练习系统和正式比赛是同一套环境做题时编译器不会给你任何“额外大数库”能靠的只有语言自身特性和你自己的代码。2. 先搞懂数学原理16 和 8 之间为什么隔着个二进制2.1 从“进制”的本质说起我们在十进制里数数满十进一在十六进制里满十六进一在八进制里满八进一。进制不同本质上是对同一个数值的不同“记法”。理论上任何进制之间都能互转但互转的方式不一样代价也不一样。十进制转二进制要不断除 2 取余二进制转八进制却只要三位一组地分段原因在于8 是 2 的三次方16 是 2 的四次方。因为 16 2^4所以十六进制的每一位恰好都对应二进制的四位不多不少。因为 8 2^3所以二进制的每三位恰好对应八进制的一位也是不多不少。进制间有这种 2 的幂次关系时转换就完全不需要做乘除法只需要做“查表”加“分组”的字符串操作这是整道题最核心的数学背景。2.2 8421 法十六进制到二进制的快捷通道先把十六进制的每个字符展开成 4 位二进制。方法很简单每一位对应 8、4、2、1 四个权值加起来等于该位的值。比如字符 AA 代表 10拆成 8 0 2 0所以二进制就是 1010。字符 F代表 15拆成 8 4 2 1二进制就是 1111。数字 3 就是 0011。我把完整的映射表列在这里后面写代码时要反复用十六进制字符十进制值二进制展开4位000000110001220010330011440100550101660110770111881000991001A101010B111011C121100D131101E141110F151111以输入样例“39”为例3 展开成 00119 展开成 1001拼起来就是二进制串 00111001也就是十进制的 57。2.3 二进制到八进制的三位分组二进制转八进制的规则是从右往左每三位一组。为什么是从右往左因为八进制的最低位对应三位二进制的最低位进位关系决定高位在前、低位在后。比如 111001从右往左分组是001 和 111 两组不对111001 从最右边开始第一个三位是 001左边剩下 111所以分组结果是“111 001”。每一组分别算成十进制111 是 7001 是 1拼在一起就是八进制数 71。这样 39十六进制就变成了 71八进制完全正确。如果二进制串的长度不是 3 的倍数怎么办从左端补 0。比如只有一个十六进制字符 F展开是 1111四位不是三的倍数就在最左边补两个 0变成 001111再分成 001 和 111得到八进制 17。补 0 是因为高位补 0 不改变数值大小只是把位数凑整齐方便分组。3. 两条技术路线暴力转换法与大数分组法3.1 路线一用 BigInteger 直接转能过但别依赖Java 里确实有一行秒杀的方案System.out.println(new BigInteger(hex, 16).toString(8));BigInteger接收一个字符串和基数把它解析成一个大整数再输出成指定基数的字符串。这行代码能处理 100000 位十六进制数实测不会超时因为 JVM 内置的大整数运算做了很多底层优化对于 10 万位的规模仍然在可接受范围内。但我不推荐把它作为主要学习路径。原因很简单你会了这个说明你“会用库”而不是“会这道题”。如果比赛环境不是 Java或者题目稍作变化改成二进制转十进制BigInteger也一样救不了你。另外BigInteger内部是 32 位为单位存储的转进制时要做大整数除法本质上比字符串分组法更重只是常数优化让它看起来还行。3.2 路线二字符串映射 按位分组推荐方案推荐的方案就是前面原理里推导出来的方法十六进制字符串 - 二进制字符串 - 三位一组 - 八进制字符串。整个过程的时间复杂度是 O(n)n 是十六进制字符串长度因为这个过程只是逐字符展开和逐三位拼接没有进位、没有递归、没有大整数除法。这个方案还有两个好处一是 C、Java、Python 甚至任意语言都能轻松实现二是过程中你能清晰看到进制之间的位模式关系对后续学习位运算、IP地址换算、字符编码都有帮助。我个人判断这道题放在“基础练习”里就是希望你掌握这种字符串分组处理的能力而不是单纯考一个 API 调用。4. 完整代码实现C 和 Java 双版本4.1 C 实现#include iostream #include string using namespace std; int main() { int n; cin n; while (n--) { string hex; cin hex; // 第一步十六进制转二进制 string bin ; for (char c : hex) { switch (c) { case 0: bin 0000; break; case 1: bin 0001; break; case 2: bin 0010; break; case 3: bin 0011; break; case 4: bin 0100; break; case 5: bin 0101; break; case 6: bin 0110; break; case 7: bin 0111; break; case 8: bin 1000; break; case 9: bin 1001; break; case A: bin 1010; break; case B: bin 1011; break; case C: bin 1100; break; case D: bin 1101; break; case E: bin 1110; break; case F: bin 1111; break; } } // 第二步左边补0让二进制长度是3的倍数 int pad (3 - bin.size() % 3) % 3; if (pad 1) bin 0 bin; else if (pad 2) bin 00 bin; // 第三步每三位一组转八进制 string oct ; for (size_t i 0; i bin.size(); i 3) { int val (bin[i] - 0) * 4 (bin[i1] - 0) * 2 (bin[i2] - 0); oct char(0 val); } // 第四步去掉前导0 size_t pos oct.find_first_not_of(0); if (pos string::npos) { cout 0 endl; } else { cout oct.substr(pos) endl; } } return 0; }这段代码有几个细节值得说。switch 映射是整个程序的根基写的时候最容易出错的点集中在 B、D、F 三个字符上B 是 1011D 是 1101F 是 1111字母 A 到 F 的映射别背混。第二步补 0 只可能补 1 个或 2 个因为二进制长度对 3 取余只可能是 0、1、2。第三步中(bin[i] - 0) * 4 (bin[i1] - 0) * 2 (bin[i2] - 0)本质上是把三位二进制数当成一个 0 到 7 的值来算这里用的是权值 4、2、1和十进制转二进制时的 8421 是同一个道理。第四步去掉前导0 的时候要小心如果整个八进制串全是 0find_first_not_of(0)会返回string::npos此时必须输出一个“0”否则会输出空行。4.2 Java 实现import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc new Scanner(System.in); int n sc.nextInt(); while (n-- 0) { String hex sc.next(); StringBuilder bin new StringBuilder(); for (char c : hex.toCharArray()) { switch (c) { case 0: bin.append(0000); break; case 1: bin.append(0001); break; case 2: bin.append(0010); break; case 3: bin.append(0011); break; case 4: bin.append(0100); break; case 5: bin.append(0101); break; case 6: bin.append(0110); break; case 7: bin.append(0111); break; case 8: bin.append(1000); break; case 9: bin.append(1001); break; case A: bin.append(1010); break; case B: bin.append(1011); break; case C: bin.append(1100); break; case D: bin.append(1101); break; case E: bin.append(1110); break; case F: bin.append(1111); break; } } int pad (3 - bin.length() % 3) % 3; if (pad 1) bin.insert(0, 0); else if (pad 2) bin.insert(0, 00); StringBuilder oct new StringBuilder(); for (int i 0; i bin.length(); i 3) { int val (bin.charAt(i) - 0) * 4 (bin.charAt(i 1) - 0) * 2 (bin.charAt(i 2) - 0); oct.append((char) (0 val)); } String res oct.toString().replaceFirst(^0, ); if (res.isEmpty()) res 0; System.out.println(res); } } }Java 版的整体思路完全一样唯一值得强调的差异是必须用StringBuilder而不是直接对String做。字符串是不可变对象每做一次拼接都会产生一个新的字符串10 万位的输入意味着至少要几万次拼接用String会反复创建对象性能和内存都很难看StringBuilder底层是可变字符数组append 是平摊 O(1) 的操作这一点是 Java 写大字符串处理时的基本素养。去前导 0 我用的是正则replaceFirst(^0, )如果全为 0替换结果为空串再单独补成“0”。4.3 代码走读与复杂度分析拿输入FFFF来走一遍流程。FFFF展开成二进制是 16 个 11111111111111111长度 16对 3 取余是 1所以左边补 2 个 0变成 001111111111111111。再从前往后每三位分组001 111 111 111 111 111。每一组转成十进制数1 7 7 7 7 7拼起来是 177777。整个过程中没有出现任何进位借位操作因为二进制本身就是十六进制和八进制之间的天然桥梁。复杂度上十六进制长度为 n二进制长度为 4n八进制长度为 4k/3整体空间复杂度 O(n)时间复杂度 O(n)。对于 100000 的上限这个复杂度非常安全实测在练习系统上运行时间在个位数毫秒级别性能没有任何压力。反倒是那些试图先转十进制再转八进制、用普通整型运算的人会在测试点直接爆掉——不是运行错误就是答案错误。5. 踩坑实录测了 30 组数据才发现的细节5.1 前导 0 的坑最容易被忽略的边界第一组边界数据输入0000。按照正常流程展开二进制是 16 个 0补 0 后分组八进制串是0000如果直接输出就会在第一个测试点翻车。正确结果是输出单个0。这个坑我见过不止一个同学踩原因很简单人脑处理十进制时默认不会写前导 0但字符串处理时前导 0 就是实实在在的字符。第二个边界数据输入0001。期望输出是1但如果你只在处理全 0 时特判在普通情况下忘记删除前导 0那么分组结果是000 000 000 001转出来是0001照样会出错。所以无论什么情况去前导 0 这一步都不能省。5.2 输出格式的坑Presentation Error 也是错蓝桥杯的判题系统对格式很敏感多一个空行、少一个空行都会提示格式错误。我见过有人把while (n--)写成while (n) { ... n--; }时不小心多输出了一行也见过有人在每行结束多加了一个空格。这道题的要求就是每个结果占一行不要有任何多余字符。你在本地测试时用diff比对输出文件就能发现这种问题但在练习系统里就直接报 Presentation Error。5.3 性能与内存别在小字符串上栽大跟头100000 位十六进制转成二进制串是 400000 个字符如果切换语言不规范比如 Java 用String String拼接就可能触发大量字符串对象创建导致时间超限。C 的在 C11 之后通常有优化但如果你非要用insert(0, ...)在头部反复插入最坏情况下会退化成 O(n^2)。正确做法是在尾部拼接最后只在开头补一次 0或者干脆先算好总长度再一次性处理。5.4 映射表的记忆技巧实际写代码时不用死记硬背整张表有一个推导方法四位二进制的权值是 8、4、2、1把十六进制字符对应的十进制数拆成这四个权值的和。A 是 1010 8 2所以是 1010B 是 1111 8 2 1所以是 1011C 是 1212 8 4所以是 1100D 是 1313 8 4 1所以是 1101E 是 1414 8 4 2所以是 1110F 是 1515 8 4 2 1所以是 1111。数字 0 到 9 则是字面量转四位二进制比如 5 4 1就是 0101。现场推导比背表可靠得多还不容易错。6. 举一反三从这道题延伸出去的技能点6.1 分组转换法的迁移能力“十六进制 - 二进制 - 八进制”这个方法本质上利用了 2 的幂次关系。同理八进制转十六进制也很简单先把八进制每一位展开成 3 位二进制再把这个二进制串从右往左每 4 位一组转成十六进制。只要两个进制都是 2 的幂次转换就能用“展开 分组”两个字符串操作完成不需要任何算术运算。比如八进制数 177777每一位展开1 - 0017 - 1117 - 1117 - 1117 - 1117 - 111拼起来是 001111111111111111去掉前导 0 就是 1111111111111111每 4 位一组1111 1111 1111 1111每个都是 F得到 FFFF。正好和前面的例子互为逆过程。6.2 对比十六进制转十进制为何不能这样展开如果把题目改成“十六进制转十进制”10 不是 2 的幂次你就没法用简单的三位分组或四位分组来完成。此时 100000 位的十六进制转换成十进制必须依赖大数乘法模拟竖式每一位乘以 16 然后累加或者直接用内置大整数库。这也是为什么这道题偏偏是转八进制而不是转十进制——它设计得让你用位模式关系来解而不是硬算乘除法。认识到这一层你才算真正理解出题人的意图。6.3 用 Python 写对拍脚本验证正确性本地测试时我强烈建议写一个 Python 脚本做对拍。Python 自带大整数和进制转换三行就能求出标准答案def hex_to_oct(hex_str): return oct(int(hex_str, 16))[2:]对拍流程有两种方式。一种是你把 C 程序编译好Python 用subprocess调用它给同一份输入然后对比输出另一种是你先随机生成大量十六进制字符串用 Python 算出期望结果存成文件再和 C 程序的输出文件做diff。随机数据里要特意包含全 0、超长 AAAA、以 0 开头等边界情况这样能快速找出前导 0 和映射错误。7. 写在最后的一点心得我刷了很多年的算法题也帮不少同学看过代码说实话BASIC-12 这道题论难度排不上号但它之所以能在“基础练习”里占一个位置就是因为它在最简单的外壳下藏了一个“大数”内核。很多人贪图快直接调用库函数转完交上去代码只有一行也能拿满分——这当然没问题比赛就是看结果。但如果只是练手我仍然建议你亲手写一遍字符串分组版本哪怕只用一次你也会对十六进制和二进制之间的 8421 关系有肌肉记忆。以后遇到 IP 地址换算、Modbus 协议报文解析、字符编码转换这些看似八竿子打不着的场景里你都会发现当年这道基础题教给你的东西一直在起作用。最后提醒一句做题前一定先看清数据范围它往往才是题目的真正难度所在。