1. 这道题到底在考什么1.1 从GESP四级真题说起B3870这道题全称是“[GESP202309 四级] 变长编码”如果你去洛谷题库翻它的提交记录能看到不少膜拜字样——这也是膜拜版这个标题的由来。很多第一次刷到这道题的人会被变长编码这个名字唬住以为要上什么高深的压缩算法结果读完题发现它考的就是位运算加进制分组本质上是让你用最底层的思路实现一次编码过程。GESP四级考试面向的是已经学完基本语法、开始接触算法和数据结构的阶段那道真题在考场上有两个典型痛点第一规则看起来绕部分考生读着读着就晕了第二就算读懂规则也容易在哪一位是继续位输出顺序是什么这种细节上栽跟头。所以你看洛谷题解区各种写法都有但真正写得干净利落的并不多。这篇拆解就是想把这道题从头到尾掰开揉碎讲清楚。先说结论这道题不需要数组存储不需要字符串处理甚至不需要递归。只要会用、、|三个位运算十行代码之内就能写完。但如果你搞不懂编码规则背后的设计逻辑背代码也白搭。1.2 变长编码在计算机里有多常见很多人觉得编码方式是个很遥远的概念其实你每天都在用它。最常见的例子是UTF-8一个英文字符占1个字节一个汉字占3个字节UTF-8就是通过每个字节最高位的特殊标记告诉解码器这个字符一共有几个字节。这套思路不止出现在字符编码里MIDI音乐文件的VLQ可变长度数量编码、Protobuf的varint编码、网络协议里的TLV结构全部都是每7个有效位 1个继续标记位的变种。换句话说只要你理解了GESP这道变长编码题的精髓后面碰到这些工程场景你会有一种哎这不就是我考过的那道题吗的熟悉感。所以别小看这题它考的其实是一个影响深远的编码范式。2. 编码规则逐条拆解2.1 7位一组加1位继续标记先把题目规则翻译成人话。变长编码的目标是把一个非负整数从二进制低位开始每7位分成一组然后给每一组额外附加一个最高位这个最高位叫继续位用1表示我后面还有更高位的组用0表示我就是最高位的组。最后按从低到高的顺序把每个组现在是8位了转换成一个十进制数依次输出。举个例子输入127。127的二进制是1111111刚好7位属于最高位组所以继续位是0组装成8位就是01111111十进制输出127。就一个数结束。再比如输入128。128的二进制是10000000一共8位。从低位截取7位得到0000000也就是0但这组后面还有高位所以继续位是1组装后是10000000十进制128剩下高位的1单独一组继续位是0组装成00000001十进制1。输出是128 1。可能你已经发现了编码后的每一组其实就是7个有效二进制位 1个继续位。继续位相当于一个路标告诉解码的人往后再取多少组才能拼出完整数据。2.2 位运算三件套理解了规则就该想怎么用代码表达。位运算三件套是这样的第一步取出低7位n 127。127的二进制是1111111n 127就像用一把七齿梳子把n的二进制从低位开始只留下7个齿能碰到的位其余高位全部清零。第二步判断是否还有高位n 7。右移7位相当于把刚才取走的那7位扔掉露出下一批7位。移位之后如果n变成0说明没有更高位的组了当前组就是最高位组。第三步设置继续位if (n 0) low7 | 128;。128的二进制是10000000用按位或把第8位强制改成1。这里的| 128只改变最高位不影响低7位已经取出来的值。这三步循环到n为0为止。整个逻辑就藏在先取低7位再判断剩余高位这个循环里。2.3 手算推演一个完整例子上面几条规则是用文字描述的真正要理解还差一个实战我们手动跑一遍样例输入123456。先明确二进制的每一位。123456的二进制是11110001001000000长度17位。编码从低位开始一次取7位。第一轮低7位是1000000也就是64取出之后还剩更高位所以这组要继续位1组合结果10000000 | 0100000011000000 192第二轮处理123456 7 964它的低7位是1000100也就是68964右移7位之后变成7说明还有位继续位1组合结果1000100 | 1000000011000100 196第三轮处理964 7 7低7位是0000111也就是77右移7位之后变成0说明这是最高位组继续位0组合结果00000111 7最终输出192 196 7。这个结果和洛谷样例完全一致。注意观察第二轮和第三轮196的低7位是68192的低7位是64中间隔了一个继续位但低7位那部分就是纯数据位一点都没被继续位污染。3. 代码实现与逐步讲解3.1 最简洁的写法下面这段是我个人比较推荐的写法没有用vector也没有预先定义超大数组直接用一个定长数组就够因为即便输入范围到int上限编码后的组数也不会超过5个。#include iostream using namespace std; int main() { long long n; cin n; if (n 0) { cout 0 endl; return 0; } int bytes[10]; int cnt 0; while (n 0) { int group n 127; // 取出低7位 n 7; // 右移判断是否还有更高位 if (n 0) { group | 128; // 还有更高位置继续位为1 } bytes[cnt] group; } for (int i 0; i cnt; i) { cout bytes[i] ; } cout endl; return 0; }注意第7和第8行的long longGESP考场上数据范围通常给到10^9甚至10^18如果用int接收还没开始编码就已经溢出了这是最常见的低级失误。3.2 为什么n 7放这个位置这个代码里面两个相邻语句的顺序特别容易搞错。我的习惯是先n 127取低7位紧接着n 7把已经取走的位丢掉然后再判断n 0决定要不要设置继续位。为什么不能先右移再取低7位如果你先n 7原来的低7位就丢了你再 127拿到的就是第8到第14位的数据。这样第一个输出组就不是最低位组整个输出顺序就全反了。这道题要求从低到高输出所以先取低位再移走低7位必须按顺序来。如果你想把if (n 0)放到右移之前逻辑上倒是成立——右移之前就能判断当前数右移7位后是否还剩值。但那样写需要保存移位前的n多一个变量反而绕。直接在右移之后判断是更清爽的写法。3.3 两种常见写法的对比洛谷题解区还有一种写法是递归大概长这样void encode(long long n) { int group n 127; n 7; if (n 0) { encode(n); group | 128; } cout group ; }这个写法巧妙在它先递归处理更高位组等回归的时候再输出当前组所以输出顺序自然就是正确的。但说实话递归会引入额外的栈开销对这道题来说没有性能问题但迭代写法更直观也更容易让初学者理解从低位到高位处理、从低位到高位输出的过程。3.40绝不能漏if (n 0) { cout 0; }这个特判看着不起眼实际上决定你能不能过样例。因为程序的while循环条件是n 0如果输入0循环一次都不会进入bytes数组就是空的什么都不会输出。而题目明确要求0输出一个0。这里有个隐藏的小知识点0的二进制没有位所以无法进行每7位分组这个操作。编码规则对正整数有完整定义对0就必须单独约定题目约定输出0你要照做。4. 常见问题与排查技巧4.1 位运算结果怎么验证写这种题最怕的就是逻辑对但结果不对又不知道哪里错了。我的排查习惯是先把程序输出的结果打出来再手工推一遍最长的那组数据两边对不上就逐步加cerr或者cout断点观察中间值。以123456为例你可以打印每一轮循环的group和n第一轮group 64n 964第二轮group 68n 7第三轮group 7n 0看到n依次递减为0说明循环条件设置正确看到group分别是64、68、7再手动| 128得到192、196、7就能确认输出无误。这个过程最好在练题的时候做熟而不是考场上才临时打印调试。4.2 边界值速查表我把几组典型边界的编码结果整理成了一张表平时用来对拍也好复习也好都有用输入二进制编码输出000111127111111112712810000000128 125511111111255 1163831111111111111114位255 1271638410000000000000015位128 128 1拿16383来看14位全1分成两组各7位低7位为127高7位也是127低组继续位1变成255高组继续位0还是127输出255 127。16384的二进制是1后面14个0低7位全0加继续位1变成128中7位全0加继续位1变成128最高位那1个1变成1所以输出128 128 1。这张表建议收藏一下里面每一行都是一个边界你写代码的时候拿这些值去测比随机数好用得多。4.3 输出格式的隐藏坑这道题的输出格式是每组数字用空格隔开有极少数考生会在最后一个数后面也加空格OJ一般会判错。卡格式是非常不划算的丢分方式养成输出前判断一下是不是最后一个元素的习惯能少踩很多坑。上面代码里用了最朴素的循环for (int i 0; i cnt; i) { cout bytes[i] ; }这个写法最后会多一个空格。GESP官方评测如果严格比对可能判AC也可能判PE格式错误不同OJ策略不一样。保险起见建议改成for (int i 0; i cnt; i) { if (i 0) cout ; cout bytes[i]; } cout endl;代码多两行但无论碰到多严格的评测机都不会出问题。4.4 数组开多大才够这是我在评论区经常看到的问题。假设题目输入范围是0 ≤ n ≤ 10^9这大约是30位二进制每7位一组最多需要5个字节。就算范围到10^18也就是60位二进制最多也只是9个字节。所以开int bytes[10]在绝大多数情况下是够的。如果你实在担心开int bytes[128]也不会对你造成任何负担。数组是死的人是活的多开一点总比越界好。5. 从考题看工程变长编码的实战位置5.1 和UTF-8、VLQ的异同刷完这道题千万别急于翻下一篇题解花十分钟把它和现实世界的编码方案联系起来收获会大得多。先说UTF-8。在UTF-8编码中一个字符的第一个字节最高几位用来表示这个字符总共占多少字节后续每个字节的最高两位固定为10。这跟GESP的变长编码一样都是靠字节内部的标记位来传递是否还有后续部分的信息。区别在于UTF-8的标记位存在于每个字节的最高位或者最高几位而且数据位分布在不同位置GESP这题更简单直接所有数据位固定用7位标记位固定用1位没有任何花哨。再说MIDI文件里的VLQ编码。它跟这道题几乎一模一样每7位一组每个字节最高位为1表示后续还有字节为0表示这是最后一个字节。唯一的差异在于字节序——MIDI VLQ也按从低到高存储但读取时先从最高字节开始所以解码过程要把每组7位数据依次左移再拼接。GESP这道题相当于只考编码不考解码已经是非常友好的一种考法了。你如果把这道题的代码稍加修饰把输出部分改成收集全部字节、各字节左移对应倍数后合并就能得到变长编码的解码器。编码和解码互为逆运算这个对应关系值得自己亲手推一遍。5.2 为什么7位一组这么巧妙1993年设计UTF-8时采用8位一组是因为要兼容ASCII和字节寻址而GESP这道题选择7位一组背后也是同一个思路传统的字节是8位最高位被用作继续位有效数据位就只剩7位。如果要传输ASCII文本7位的数据位刚好能放下128个字符的编码所以这类方案在早期网络协议中非常流行。今天你在不少高性能序列化库中还能看到这个设计比如Protobuf的varint就用了7位数据 1位继续位的格式只不过它以小端序存储且最大支持64位整数。所以看懂了这道题你其实已经掌握了现代序列化库中最核心的一小部分设计原理。这也是它被选为GESP四级真题的原因——考察面广性价比高。5.3 考场上如何快速确定解法如果你在考场上遇到没见过的编码类题目我的建议是先干三件事第一把题目给的样例全部手算一遍不要直接看答案。自己掰着手指头推出样例的输出你就能完全掌握数据流转的规则。第二把样例倒过来想一想如果给你编码后的序列你能否还原出原始整数这一方面能帮你确认自己的编码规则没有理解偏另一方面也能帮你在代码写不出来的时候通过反推来定位逻辑漏洞。第三写代码之前先在草稿纸上写出大致的循环结构。对这道题而言核心循环只有三句话取低7位右移7位按需置继续位。这三句话写下来代码框架基本就稳了。考场上的状态和平时刷题完全不一样平时可以试错考场上没有那么多时间重来。所以必须通过手算样例建立信心再动键盘。6. 从提交记录里观察到的失败模式我去翻这道题的提交记录时发现一个很有意思的现象很多人WA答案错误的原因并不是编码逻辑出错而是在int和long long的选择上翻车。GESP四级题目的输入数据选手很容易想当然地认为给一个不超过int范围的正整数就够了但实际数据范围从来不写那么友善。以后做任何竞赛题如果题目没有明确说明数据范围看到正整数三个字第一反应就应该是long long这比看到非负整数再去考虑0还重要。还有一种失败模式是输出顺序反了。有人把整个编码流程想反了认为应该从高位开始处理结果输出变成了从高到低和题目要求的低位到高位完全颠倒样例200左右还能勉强看明白数据稍微大一点就全错。解决这个问题的最好办法是回到手算步骤一步步把输出序列写下来看看是从哪个方向推出来的。最后一个常见的坑是继续位设置反了最高位组设置了1非最高位组设置了0。这种错误的本质是没理解继续位的含义。记住一句话继续位为1表示编码还没完后面还有更高位的组继续位为0表示这组就是这个数的天花板。题目里任何一句关于如果后面还有组的描述翻译过来都是这个意思。我在实际测试时最常用的验证样例是128和16384。这两个数都是1后面一堆0的形式最容易暴露继续位和移位顺序的错误。如果你把这两个数测对了这道题就基本稳了。还有一个小技巧你在本地测试的时候可以写一个反向解码函数把编码结果还原成原始数据然后随机生成几万个整数做循环对拍。这招在平时练题中非常实用能一次性找出所有隐藏边界问题比手动用样例测一遍可靠得多。这个习惯我保持了两年几乎所有的位运算题都能靠这一招一次AC。最后再分享一个个人经验这类考点纯粹的题目最忌讳的是把问题想复杂。如果你开始考虑用字符串存储二进制、用递归倒序、甚至写高精度那一定是偏离了出题人的意图。回到位运算本身回到数据本身从低到高按7位切分答案自然就浮出来了。 GESP四级真题拆解：变长编码与位运算实战
1. 这道题到底在考什么1.1 从GESP四级真题说起B3870这道题全称是“[GESP202309 四级] 变长编码”如果你去洛谷题库翻它的提交记录能看到不少膜拜字样——这也是膜拜版这个标题的由来。很多第一次刷到这道题的人会被变长编码这个名字唬住以为要上什么高深的压缩算法结果读完题发现它考的就是位运算加进制分组本质上是让你用最底层的思路实现一次编码过程。GESP四级考试面向的是已经学完基本语法、开始接触算法和数据结构的阶段那道真题在考场上有两个典型痛点第一规则看起来绕部分考生读着读着就晕了第二就算读懂规则也容易在哪一位是继续位输出顺序是什么这种细节上栽跟头。所以你看洛谷题解区各种写法都有但真正写得干净利落的并不多。这篇拆解就是想把这道题从头到尾掰开揉碎讲清楚。先说结论这道题不需要数组存储不需要字符串处理甚至不需要递归。只要会用、、|三个位运算十行代码之内就能写完。但如果你搞不懂编码规则背后的设计逻辑背代码也白搭。1.2 变长编码在计算机里有多常见很多人觉得编码方式是个很遥远的概念其实你每天都在用它。最常见的例子是UTF-8一个英文字符占1个字节一个汉字占3个字节UTF-8就是通过每个字节最高位的特殊标记告诉解码器这个字符一共有几个字节。这套思路不止出现在字符编码里MIDI音乐文件的VLQ可变长度数量编码、Protobuf的varint编码、网络协议里的TLV结构全部都是每7个有效位 1个继续标记位的变种。换句话说只要你理解了GESP这道变长编码题的精髓后面碰到这些工程场景你会有一种哎这不就是我考过的那道题吗的熟悉感。所以别小看这题它考的其实是一个影响深远的编码范式。2. 编码规则逐条拆解2.1 7位一组加1位继续标记先把题目规则翻译成人话。变长编码的目标是把一个非负整数从二进制低位开始每7位分成一组然后给每一组额外附加一个最高位这个最高位叫继续位用1表示我后面还有更高位的组用0表示我就是最高位的组。最后按从低到高的顺序把每个组现在是8位了转换成一个十进制数依次输出。举个例子输入127。127的二进制是1111111刚好7位属于最高位组所以继续位是0组装成8位就是01111111十进制输出127。就一个数结束。再比如输入128。128的二进制是10000000一共8位。从低位截取7位得到0000000也就是0但这组后面还有高位所以继续位是1组装后是10000000十进制128剩下高位的1单独一组继续位是0组装成00000001十进制1。输出是128 1。可能你已经发现了编码后的每一组其实就是7个有效二进制位 1个继续位。继续位相当于一个路标告诉解码的人往后再取多少组才能拼出完整数据。2.2 位运算三件套理解了规则就该想怎么用代码表达。位运算三件套是这样的第一步取出低7位n 127。127的二进制是1111111n 127就像用一把七齿梳子把n的二进制从低位开始只留下7个齿能碰到的位其余高位全部清零。第二步判断是否还有高位n 7。右移7位相当于把刚才取走的那7位扔掉露出下一批7位。移位之后如果n变成0说明没有更高位的组了当前组就是最高位组。第三步设置继续位if (n 0) low7 | 128;。128的二进制是10000000用按位或把第8位强制改成1。这里的| 128只改变最高位不影响低7位已经取出来的值。这三步循环到n为0为止。整个逻辑就藏在先取低7位再判断剩余高位这个循环里。2.3 手算推演一个完整例子上面几条规则是用文字描述的真正要理解还差一个实战我们手动跑一遍样例输入123456。先明确二进制的每一位。123456的二进制是11110001001000000长度17位。编码从低位开始一次取7位。第一轮低7位是1000000也就是64取出之后还剩更高位所以这组要继续位1组合结果10000000 | 0100000011000000 192第二轮处理123456 7 964它的低7位是1000100也就是68964右移7位之后变成7说明还有位继续位1组合结果1000100 | 1000000011000100 196第三轮处理964 7 7低7位是0000111也就是77右移7位之后变成0说明这是最高位组继续位0组合结果00000111 7最终输出192 196 7。这个结果和洛谷样例完全一致。注意观察第二轮和第三轮196的低7位是68192的低7位是64中间隔了一个继续位但低7位那部分就是纯数据位一点都没被继续位污染。3. 代码实现与逐步讲解3.1 最简洁的写法下面这段是我个人比较推荐的写法没有用vector也没有预先定义超大数组直接用一个定长数组就够因为即便输入范围到int上限编码后的组数也不会超过5个。#include iostream using namespace std; int main() { long long n; cin n; if (n 0) { cout 0 endl; return 0; } int bytes[10]; int cnt 0; while (n 0) { int group n 127; // 取出低7位 n 7; // 右移判断是否还有更高位 if (n 0) { group | 128; // 还有更高位置继续位为1 } bytes[cnt] group; } for (int i 0; i cnt; i) { cout bytes[i] ; } cout endl; return 0; }注意第7和第8行的long longGESP考场上数据范围通常给到10^9甚至10^18如果用int接收还没开始编码就已经溢出了这是最常见的低级失误。3.2 为什么n 7放这个位置这个代码里面两个相邻语句的顺序特别容易搞错。我的习惯是先n 127取低7位紧接着n 7把已经取走的位丢掉然后再判断n 0决定要不要设置继续位。为什么不能先右移再取低7位如果你先n 7原来的低7位就丢了你再 127拿到的就是第8到第14位的数据。这样第一个输出组就不是最低位组整个输出顺序就全反了。这道题要求从低到高输出所以先取低位再移走低7位必须按顺序来。如果你想把if (n 0)放到右移之前逻辑上倒是成立——右移之前就能判断当前数右移7位后是否还剩值。但那样写需要保存移位前的n多一个变量反而绕。直接在右移之后判断是更清爽的写法。3.3 两种常见写法的对比洛谷题解区还有一种写法是递归大概长这样void encode(long long n) { int group n 127; n 7; if (n 0) { encode(n); group | 128; } cout group ; }这个写法巧妙在它先递归处理更高位组等回归的时候再输出当前组所以输出顺序自然就是正确的。但说实话递归会引入额外的栈开销对这道题来说没有性能问题但迭代写法更直观也更容易让初学者理解从低位到高位处理、从低位到高位输出的过程。3.40绝不能漏if (n 0) { cout 0; }这个特判看着不起眼实际上决定你能不能过样例。因为程序的while循环条件是n 0如果输入0循环一次都不会进入bytes数组就是空的什么都不会输出。而题目明确要求0输出一个0。这里有个隐藏的小知识点0的二进制没有位所以无法进行每7位分组这个操作。编码规则对正整数有完整定义对0就必须单独约定题目约定输出0你要照做。4. 常见问题与排查技巧4.1 位运算结果怎么验证写这种题最怕的就是逻辑对但结果不对又不知道哪里错了。我的排查习惯是先把程序输出的结果打出来再手工推一遍最长的那组数据两边对不上就逐步加cerr或者cout断点观察中间值。以123456为例你可以打印每一轮循环的group和n第一轮group 64n 964第二轮group 68n 7第三轮group 7n 0看到n依次递减为0说明循环条件设置正确看到group分别是64、68、7再手动| 128得到192、196、7就能确认输出无误。这个过程最好在练题的时候做熟而不是考场上才临时打印调试。4.2 边界值速查表我把几组典型边界的编码结果整理成了一张表平时用来对拍也好复习也好都有用输入二进制编码输出000111127111111112712810000000128 125511111111255 1163831111111111111114位255 1271638410000000000000015位128 128 1拿16383来看14位全1分成两组各7位低7位为127高7位也是127低组继续位1变成255高组继续位0还是127输出255 127。16384的二进制是1后面14个0低7位全0加继续位1变成128中7位全0加继续位1变成128最高位那1个1变成1所以输出128 128 1。这张表建议收藏一下里面每一行都是一个边界你写代码的时候拿这些值去测比随机数好用得多。4.3 输出格式的隐藏坑这道题的输出格式是每组数字用空格隔开有极少数考生会在最后一个数后面也加空格OJ一般会判错。卡格式是非常不划算的丢分方式养成输出前判断一下是不是最后一个元素的习惯能少踩很多坑。上面代码里用了最朴素的循环for (int i 0; i cnt; i) { cout bytes[i] ; }这个写法最后会多一个空格。GESP官方评测如果严格比对可能判AC也可能判PE格式错误不同OJ策略不一样。保险起见建议改成for (int i 0; i cnt; i) { if (i 0) cout ; cout bytes[i]; } cout endl;代码多两行但无论碰到多严格的评测机都不会出问题。4.4 数组开多大才够这是我在评论区经常看到的问题。假设题目输入范围是0 ≤ n ≤ 10^9这大约是30位二进制每7位一组最多需要5个字节。就算范围到10^18也就是60位二进制最多也只是9个字节。所以开int bytes[10]在绝大多数情况下是够的。如果你实在担心开int bytes[128]也不会对你造成任何负担。数组是死的人是活的多开一点总比越界好。5. 从考题看工程变长编码的实战位置5.1 和UTF-8、VLQ的异同刷完这道题千万别急于翻下一篇题解花十分钟把它和现实世界的编码方案联系起来收获会大得多。先说UTF-8。在UTF-8编码中一个字符的第一个字节最高几位用来表示这个字符总共占多少字节后续每个字节的最高两位固定为10。这跟GESP的变长编码一样都是靠字节内部的标记位来传递是否还有后续部分的信息。区别在于UTF-8的标记位存在于每个字节的最高位或者最高几位而且数据位分布在不同位置GESP这题更简单直接所有数据位固定用7位标记位固定用1位没有任何花哨。再说MIDI文件里的VLQ编码。它跟这道题几乎一模一样每7位一组每个字节最高位为1表示后续还有字节为0表示这是最后一个字节。唯一的差异在于字节序——MIDI VLQ也按从低到高存储但读取时先从最高字节开始所以解码过程要把每组7位数据依次左移再拼接。GESP这道题相当于只考编码不考解码已经是非常友好的一种考法了。你如果把这道题的代码稍加修饰把输出部分改成收集全部字节、各字节左移对应倍数后合并就能得到变长编码的解码器。编码和解码互为逆运算这个对应关系值得自己亲手推一遍。5.2 为什么7位一组这么巧妙1993年设计UTF-8时采用8位一组是因为要兼容ASCII和字节寻址而GESP这道题选择7位一组背后也是同一个思路传统的字节是8位最高位被用作继续位有效数据位就只剩7位。如果要传输ASCII文本7位的数据位刚好能放下128个字符的编码所以这类方案在早期网络协议中非常流行。今天你在不少高性能序列化库中还能看到这个设计比如Protobuf的varint就用了7位数据 1位继续位的格式只不过它以小端序存储且最大支持64位整数。所以看懂了这道题你其实已经掌握了现代序列化库中最核心的一小部分设计原理。这也是它被选为GESP四级真题的原因——考察面广性价比高。5.3 考场上如何快速确定解法如果你在考场上遇到没见过的编码类题目我的建议是先干三件事第一把题目给的样例全部手算一遍不要直接看答案。自己掰着手指头推出样例的输出你就能完全掌握数据流转的规则。第二把样例倒过来想一想如果给你编码后的序列你能否还原出原始整数这一方面能帮你确认自己的编码规则没有理解偏另一方面也能帮你在代码写不出来的时候通过反推来定位逻辑漏洞。第三写代码之前先在草稿纸上写出大致的循环结构。对这道题而言核心循环只有三句话取低7位右移7位按需置继续位。这三句话写下来代码框架基本就稳了。考场上的状态和平时刷题完全不一样平时可以试错考场上没有那么多时间重来。所以必须通过手算样例建立信心再动键盘。6. 从提交记录里观察到的失败模式我去翻这道题的提交记录时发现一个很有意思的现象很多人WA答案错误的原因并不是编码逻辑出错而是在int和long long的选择上翻车。GESP四级题目的输入数据选手很容易想当然地认为给一个不超过int范围的正整数就够了但实际数据范围从来不写那么友善。以后做任何竞赛题如果题目没有明确说明数据范围看到正整数三个字第一反应就应该是long long这比看到非负整数再去考虑0还重要。还有一种失败模式是输出顺序反了。有人把整个编码流程想反了认为应该从高位开始处理结果输出变成了从高到低和题目要求的低位到高位完全颠倒样例200左右还能勉强看明白数据稍微大一点就全错。解决这个问题的最好办法是回到手算步骤一步步把输出序列写下来看看是从哪个方向推出来的。最后一个常见的坑是继续位设置反了最高位组设置了1非最高位组设置了0。这种错误的本质是没理解继续位的含义。记住一句话继续位为1表示编码还没完后面还有更高位的组继续位为0表示这组就是这个数的天花板。题目里任何一句关于如果后面还有组的描述翻译过来都是这个意思。我在实际测试时最常用的验证样例是128和16384。这两个数都是1后面一堆0的形式最容易暴露继续位和移位顺序的错误。如果你把这两个数测对了这道题就基本稳了。还有一个小技巧你在本地测试的时候可以写一个反向解码函数把编码结果还原成原始数据然后随机生成几万个整数做循环对拍。这招在平时练题中非常实用能一次性找出所有隐藏边界问题比手动用样例测一遍可靠得多。这个习惯我保持了两年几乎所有的位运算题都能靠这一招一次AC。最后再分享一个个人经验这类考点纯粹的题目最忌讳的是把问题想复杂。如果你开始考虑用字符串存储二进制、用递归倒序、甚至写高精度那一定是偏离了出题人的意图。回到位运算本身回到数据本身从低到高按7位切分答案自然就浮出来了。