1. 这道题到底在考什么蓝桥杯基础练习里有一道编号 BASIC-12 的题目名字叫“十六进制转八进制”。很多刚接触算法竞赛的朋友第一次看到它第一反应是“进制转换嘛printf(%o)一行搞定”然后兴冲冲提交结果要么答案错误要么运行超时要么干脆连样例都过不了。我自己当年也是这么栽进去的所以特别理解那种“明明思路没错却过不了”的憋屈感。这道题的核心考点其实不是“进制转换”本身而是大数处理和进制转换的中间桥梁选择。题目通常会给出若干个十六进制字符串每个字符串长度可能达到十万位要求你把它转换成对应的八进制字符串输出。注意是字符串不是整数。十万位的十六进制数换算成二进制是四十万位这个量级远远超出了long long甚至__int128的表示范围。所以任何试图用整数类型直接存储再转换的做法都会在数据规模面前崩溃。那为什么这道题值得单独拿出来讲因为它是一个典型的“看起来简单、做起来有坑”的题目。它考察的是你对进制本质的理解十六进制和八进制之间没有直接的幂次关系但两者都和二进制有天然的对应关系——一位十六进制对应四位二进制一位八进制对应三位二进制。这个“四”和“三”的差异就是整道题所有坑的根源。你需要先把十六进制展开成二进制再把二进制按三位一组重新打包成八进制中间还要处理位数不对齐、前导零、输出格式等一系列细节。适合谁来参考这篇内容如果你正在准备蓝桥杯或者类似的算法竞赛刚学完基础语法想找一道题来练手字符串处理和进制转换那这道题非常合适。如果你已经写过但总是卡在某些测试点上这篇会帮你把那些隐藏的边界情况一个个揪出来。就算你暂时不参加比赛单纯想搞清楚“大数进制转换到底怎么做才稳”这里面的思路和代码也可以直接拿去用。2. 为什么不能走捷径方案选型背后的逻辑2.1 直接用整数转换为什么行不通先说说最直观的想法。C语言里有%x和%oPython里有int(s, 16)和oct()这些工具用起来确实爽。但问题在于题目给的十六进制字符串长度可能达到 $10^5$ 级别。一个 $10^5$ 位的十六进制数其数值大小约为 $16^{10^5}$换算成二进制是 $4 \times 10^5$ 位。任何固定宽度的整数类型都装不下这个数。就算你用Python的任意精度整数int(s, 16)本身的时间复杂度是 $O(n^2)$ 级别的朴素实现在十万位的数据面前也会超时。所以这条路从数据规模上就被堵死了。注意有些在线评测平台对Python的时限会放宽但蓝桥杯的C/C组时限通常很紧必须用 $O(n)$ 的字符串算法。2.2 为什么选择“十六进制 → 二进制 → 八进制”这条路线进制转换的通用思路是找一个“公共中间进制”。十六进制和八进制都能和二进制直接对应而且这种对应是逐位展开的不需要做除法取余。具体来说一位十六进制数0~F恰好对应四位二进制数0000~1111一位八进制数0~7恰好对应三位二进制数000~111这种对应关系是“无损”且“定长”的意味着我们可以把整个字符串逐字符展开成二进制串然后再逐三位切分回八进制。整个过程只需要遍历字符串时间复杂度是 $O(n)$空间复杂度也是 $O(n)$完全能扛住十万位的规模。相比之下如果选择“十六进制 → 十进制 → 八进制”就需要做大数除法每次除以8都要遍历整个数字串总复杂度会退化到 $O(n^2)$在竞赛中基本必死。所以中间进制的选择不是随便定的二进制是这道题唯一合理的桥梁。2.3 核心难点位数对齐展开成二进制之后问题来了。十六进制展开成二进制时每一位固定展开成四位所以总位数一定是4的倍数。但八进制要求每三位一组4的倍数不一定是3的倍数。举个例子十六进制F展开成二进制是1111只有四位按三位分组会变成1和111前面那个单独的1需要补两个前导零才能变成001也就是八进制的1。如果不补零直接按1和111分组就会得到错误的结果。所以整道题最关键的细节就是在二进制串前面补零使其长度成为3的倍数。补零的个数是 $(3 - len % 3) % 3$。这个公式看起来简单但很多人第一次写的时候会漏掉取模后的判断导致长度本来就是3的倍数时多补了三个零输出结果前面多出无意义的零。另一个容易忽略的点是输出时的前导零处理。补零之后分组得到的八进制串第一组可能是000对应的八进制数字是0但这个0不应该输出。比如十六进制1展开成二进制是0001补两个零变成000001分组为000和001对应八进制01但正确答案应该是1。所以最后输出时要去掉前导零但要注意如果整个数就是零那还是要输出一个0。3. 从字符到字符完整实现拆解3.1 映射表的建立第一步是建立十六进制字符到四位二进制串的映射。最直接的方式是用一个字符串数组下标对应字符的数值。比如hex_to_bin[0] 0000hex_to_bin[1] 0001一直到hex_to_bin[15] 1111。对于输入的字符如果是0到9数值就是字符减去0如果是A到F数值就是字符减去A再加上10。这样就能快速查到对应的四位二进制串。const char *hex_to_bin[16] { 0000, 0001, 0010, 0011, 0100, 0101, 0110, 0111, 1000, 1001, 1010, 1011, 1100, 1101, 1110, 1111 };这个映射表是整道题的基础写错一个就会导致后续全盘皆输。建议写完之后自己对着0到F逐个核对一遍确保没有手误。3.2 十六进制串展开成二进制串有了映射表展开就很简单了。遍历输入的十六进制字符串对每个字符查表把对应的四位二进制串追加到一个大的二进制字符串后面。这里有一个优化点如果直接用字符串拼接每次strcat都要找末尾总复杂度会变成 $O(n^2)$。更好的做法是预先分配好足够大的字符数组用一个指针记录当前写入位置逐段拷贝。char bin[400005]; // 十万位十六进制最多展开成四十万位二进制 int pos 0; for (int i 0; hex[i]; i) { int val; if (hex[i] 0 hex[i] 9) val hex[i] - 0; else val hex[i] - A 10; memcpy(bin pos, hex_to_bin[val], 4); pos 4; } bin[pos] \0;这里数组大小要开够。题目说十六进制串长度不超过十万那二进制串最长就是四十万加上结尾的\0开400005是安全的。如果开小了就会缓冲区溢出轻则答案错误重则程序崩溃。3.3 补零对齐与三位分组展开完成后计算需要在前面补几个零。补零的目的是让二进制串的长度成为3的倍数这样才能整齐地按三位分组。int len pos; int pad (3 - len % 3) % 3;这个pad的计算要仔细理解。如果len % 3 0说明已经对齐pad为0如果len % 3 1需要补2个零如果len % 3 2需要补1个零。公式(3 - len % 3) % 3正好覆盖这三种情况。补零之后从新的起始位置开始每三位一组计算对应的八进制数字。三位二进制abc对应的值是 $a \times 4 b \times 2 c \times 1$。可以直接用字符判断也可以写个小循环。int start 0; if (pad 0) { // 在bin前面补pad个0实际实现时可以倒着处理或者用新数组 }实际编码时为了避免移动整个数组可以换个思路不真正补零而是在分组时判断当前组的起始位置。如果pad 0第一组只有pad个有效位前面虚拟补零。这样就不需要额外的数组操作。3.4 输出与前导零处理分组计算得到八进制数字后第一个数字如果是0不能直接输出。但要注意如果整个数就是0那还是要输出一个0。所以需要一个标志位记录是否已经输出了非零数字。int started 0; for (int i 0; i groups; i) { int digit ...; // 计算当前组的八进制值 if (digit 0 !started) continue; started 1; putchar(0 digit); } if (!started) putchar(0);这个逻辑看起来简单但实际写的时候很容易在“跳过前导零”和“全零输出”之间搞混。我见过不少人写成了“遇到零就跳过”结果100这种数被输出成了1因为中间的零也被跳过了。所以一定要用started标志只跳过开头连续的零。4. 那些年我踩过的坑常见问题与排查4.1 样例过了但提交WA这是最让人抓狂的情况。样例通常只给一两个简单的数比如1和F这些数展开后位数少补零逻辑不容易暴露问题。但测试数据里会有各种边界情况比如十六进制串全是0比如0000正确答案应该是0十六进制串长度恰好使得二进制长度是3的倍数不需要补零十六进制串长度使得二进制长度模3余1或余2需要补零十六进制串很长达到十万位考验性能和数组大小我当年就是栽在“全零”这个情况上。我的代码输出了空字符串因为所有位都是零started一直是0但最后忘了补输出0。后来加了一行if (!started) putchar(0);才过。4.2 运行超时如果用了strcat或者每次都在字符串前面插入字符复杂度会退化。十万位的数据下$O(n^2)$ 的算法可能需要几秒钟甚至更久直接超时。解决办法就是用预分配数组加指针写入或者用std::string的reserve加append。C 里std::string的操作均摊是 $O(1)$ 的也可以用。4.3 数组开小了这个问题在本地测试时可能不会暴露因为本地数据小。但提交后遇到长数据就会越界表现为答案错误或者运行时错误。建议直接开到题目上限的1.5倍。十万位十六进制二进制最多四十万位八进制最多约十三万三千位所以二进制数组开400005八进制数组开140005是稳妥的。4.4 字符大小写问题题目通常说十六进制串由0-9和A-F组成但有些题目会混入小写a-f。如果你的映射只处理了大写遇到小写就会算错。保险起见可以在读入后统一转成大写或者在判断时同时处理大小写。if (hex[i] a hex[i] f) hex[i] hex[i] - a A;4.5 多组输入的换行处理这道题通常是先读一个整数 $n$表示有 $n$ 组测试数据然后每组读一个十六进制串。输出时每组占一行。如果忘了在每组输出后换行或者多输出了空行都会导致格式错误。建议用puts或者手动putchar(\n)确保每组输出后恰好一个换行。问题现象可能原因排查方法样例过但WA全零未处理、前导零逻辑错误手动测试0、00、000运行超时字符串拼接复杂度过高检查是否用了strcat或头部插入运行时错误数组越界检查数组大小是否够长数据答案部分正确大小写未统一测试小写输入格式错误换行处理不当检查每组输出后的换行5. 性能优化与代码模板5.1 时间与空间复杂度分析整个算法只遍历了输入字符串一次展开成二进制再遍历二进制串一次分组转八进制总时间复杂度是 $O(n)$其中 $n$ 是十六进制串的长度。空间上需要存储二进制串和八进制结果也是 $O(n)$。对于十万位的输入这个复杂度完全够用C语言实现通常能在几十毫秒内跑完。5.2 一份可直接复用的C语言模板下面这份代码是我自己反复打磨过的版本处理了全零、前导零、大小写、多组输入等所有边界情况可以直接拿去用。#include stdio.h #include string.h const char *hex_to_bin[16] { 0000, 0001, 0010, 0011, 0100, 0101, 0110, 0111, 1000, 1001, 1010, 1011, 1100, 1101, 1110, 1111 }; char hex[100005]; char bin[400005]; char oct[140005]; int main() { int n; scanf(%d, n); while (n--) { scanf(%s, hex); int hlen strlen(hex); int pos 0; for (int i 0; i hlen; i) { int val; if (hex[i] 0 hex[i] 9) val hex[i] - 0; else if (hex[i] A hex[i] F) val hex[i] - A 10; else val hex[i] - a 10; memcpy(bin pos, hex_to_bin[val], 4); pos 4; } bin[pos] \0; int pad (3 - pos % 3) % 3; int opos 0; int started 0; // 处理第一组可能不足三位 int first_len (pos pad) % 3; if (first_len 0) first_len 3; int idx 0; // 虚拟补零前pad位视为0 int digit 0; for (int i 0; i first_len; i) { int bit; if (i pad) bit 0; else bit bin[idx] - 0; digit digit * 2 bit; } if (digit ! 0 || pos 0) { oct[opos] 0 digit; started 1; } // 处理剩余组 while (idx pos) { digit 0; for (int i 0; i 3; i) { digit digit * 2 (bin[idx] - 0); } if (digit ! 0 || started) { oct[opos] 0 digit; started 1; } } if (!started) oct[opos] 0; oct[opos] \0; puts(oct); } return 0; }这份代码里第一组的处理稍微绕一点因为要处理虚拟补零。如果你觉得不好理解也可以选择真正在bin前面插入pad个0然后用统一的三位分组逻辑。两种写法都可以关键是逻辑要自洽。5.3 用Python快速验证思路如果你只是想验证自己的思路对不对用Python写个短版本会快很多。虽然Python在大数据下可能超时但用来对拍小数据非常方便。n int(input()) for _ in range(n): h input().strip() b .join(bin(int(c, 16))[2:].zfill(4) for c in h) pad (3 - len(b) % 3) % 3 b 0 * pad b o for i in range(0, len(b), 3): o str(int(b[i:i3], 2)) print(o.lstrip(0) or 0)这段Python代码只有十几行但把核心逻辑全包含了。zfill(4)负责补足四位lstrip(0) or 0负责去前导零并处理全零情况。你可以用它来生成测试数据然后和C语言版本对拍确保两边结果一致。6. 从这道题延伸出去还能学到什么6.1 任意进制转换的通用框架这道题虽然只涉及十六进制到八进制但它的思路可以推广到任意进制之间的转换。只要两个进制都能和某个公共进制通常是二进制或十进制建立逐位对应关系就可以用类似的“展开-重组”方法。比如三进制到九进制因为 $9 3^2$一位九进制对应两位三进制也可以逐位展开再重组。关键是要找到两个进制与公共进制之间的幂次关系。如果两个进制之间没有这种幂次关系比如十进制到七进制那就只能走“大数除法”的路线复杂度会高很多。这时候就需要用高精度除法每次除以目标进制取余数最后倒序输出。那道题在蓝桥杯里也有对应的练习难度比这道高不少。6.2 字符串处理中的“虚拟操作”技巧这道题里有一个很实用的技巧虚拟补零。我们并没有真的在二进制串前面插入零而是在分组时通过判断索引来“假装”前面有零。这种技巧在处理字符串对齐、格式化输出时非常常见可以避免大量的数组移动操作。类似的还有“虚拟反转”“虚拟截断”等核心思想都是通过索引计算来模拟物理操作从而降低时间复杂度和代码复杂度。6.3 竞赛中的调试方法论这道题很适合用来练习“对拍”这种调试方法。你可以写一个暴力版本比如用Python的大整数转换再写一个优化版本C语言的字符串算法然后随机生成大量测试数据比较两个版本的输出。如果发现不一致就把那个最小的不一致用例拿出来分析。这种方法比盯着代码干想要高效得多也是很多竞赛选手的标配技能。提示对拍时要注意生成的数据要覆盖各种边界比如全零、全F、长度模3余0/1/2、大小写混合等。可以写个脚本自动生成这些情况。6.4 实际工程中的进制转换虽然在实际工程中很少遇到十万位的进制转换但类似的“大数处理”思想在密码学、区块链、科学计算等领域很常见。比如RSA加密里的大数模幂运算就需要处理几百上千位的整数用的也是类似的字符串或数组表示法。所以这道题虽然是一道竞赛题但它背后的“用字符串模拟大数运算”的思路在真实工程里是有用武之地的。我个人在实际操作中的体会是这道题最大的价值不在于“学会进制转换”而在于“学会在数据规模面前放弃直觉方案选择适合规模的算法”。很多人写代码时习惯性地想“有没有现成函数”但竞赛和工程中经常遇到现成函数扛不住的情况这时候就需要自己动手实现。这种“从需求出发选择方案”的能力比记住某个具体算法更重要。最后再分享一个小技巧如果你在比赛中遇到类似的字符串处理题可以先在纸上画一个简单的例子把每一步的中间结果写出来然后再写代码。比如十六进制2A展开成二进制是00101010补零后是00101010长度8模3余2补1个零变成000101010分组为000、101、010对应八进制052去前导零后是52。把这个过程手动走一遍代码逻辑就清晰了。