做洛谷 P2815 的时候我第一反应是这不就是把 IPv6 地址按规则压缩一下嘛有什么难的结果第一次提交直接 WA 了两个点。后来静下来重新读题才发现这道题真正想考的并不是“会不会压缩 IPv6”而是能不能把一个需要全局比较的最优区间问题转化成能用线性扫描解决的逻辑。题解区很多人用暴力枚举连续零段也能过因为 IPv6 地址只有 8 组怎么折腾都不超时。但如果你想把代码写得更稳、更贴近题目训练的思路用标记数组配合滑动窗口去实现是最清晰的做法。这篇文章就把我的完整思路、代码和踩过的坑都摊开讲适合正在刷洛谷普及组/提高组滑动窗口类型的同学也适合刚接触 IPv6 地址规则、想搞明白“压缩”到底是怎么一回事的读者。1. 题目到底在考什么1.1 从一道 OJ 题说起P2815 的题面很简短给你一个完整的 IPv6 地址8 个用冒号分隔的 16 位组每组固定是 4 位十六进制数可能带有前导零。要求输出压缩后的最短表示。这句话拆开看有三层意思输入一定是完整地址不会出现::每组固定 4 位。 这一点很重要意味着不用去解析可变长格式。输出要“最短”而不是“合法”就行。 最短意味着你要在多个可选压缩位置里做出选择。压缩规则不是随便定的而是有明确标准的。很多同学看到“最短”两个字就开始慌觉得要动态规划。 其实不用。 IPv6 地址只有 8 组你只需要找一段“最值得压缩”的连续全零组。 为什么 因为压缩连续零组时段越长省掉的字符越多。 所以“最短”等价于“找最长连续全零组”。 这个问题用滑动窗口扫一遍就能解决。1.2 被很多人忽略的 RFC 5952如果你只把题目当作字符串处理题可能会忽略这些规则背后的来源。 IPv6 地址压缩规则在 RFC 5952 里写得很清楚核心就三条每个 16 位组里的前导零可以省略但至少要留一个字符。 比如0db8写成db80042写成42。连续两个及以上的全零组可以用::替换但整个地址里只能出现一次::否则无法确定省略了多少组。如果存在多处长度相同的连续零段必须压缩最左边的那一段保证同一个地址只有一种规范写法。这三条规则直接决定了算法设计。 第一条对应预处理时去掉每组的前导零第二条决定了你必须在所有连续零段里选最长的一段第三条决定了当最长段有多个时选起点最靠前的。我在第一次写代码时就觉得“连续两个及以上”是废话直接把阈值设成了 1结果被一个只有单个全零组的测试点教做人了。 后面会详细说这个坑。1.3 理解“最短”的真正含义有人可能会问如果某段连续零组很长压缩它一定能缩短字符串。 但如果零组只有一段但是和前后非零组组合后压缩和不压缩的长度差多少我们来粗略算一下。 假设有k个连续全零组写成明文是0:0:...:0每个零组占 1 个字符组间分隔符占 1 个字符总长度是k (k-1) 2k - 1。 压缩成::后占 2 个字符。 节省的字符数是2k - 3。 这个数随着k增大而增大所以k越大越短。 当k 2时节省 1 个字符当k 1时节省-1也就是反而变长了。 这从长度上也解释了为什么单个零组不允许用::压缩。所以“最短”这个问题本质上就是找k最大的连续全零段。 如果最大k小于 2那就一个都不压缩只做前导零省略。2. 为什么是标记数组和滑动窗口2.1 暴力枚举的问题在哪里先看看最直觉的做法把每组都转成压缩后的字符串然后用两层循环枚举每一段的起点和终点如果这一段里的所有组都是0就记下长度。 最后找出最长的那段。这个做法完全可行因为 8 组数据最多 28 个子段枚举成本极低。 但它有几个缺点代码里容易把“组的下标”和“字符下标”搞混尤其是拼接::时。两层循环里要反复检查这一整段是否全是零写起来啰嗦。如果以后想迁移到“在数组里找最长连续满足某个条件的子段”这类问题纯暴力的思路没有通用性。标记数组和滑动窗口的组合能把这个问题拆成两个独立的子问题每个子问题都很简单而且这种思路在更大数据量下也能保持线性复杂度。2.2 标记数组把地址变成 0/1 序列核心思想是先把“能不能参与::压缩”这个属性单独提出来存到一个长度为 8 的数组里。我用的是zero[i]如果第i组原始的 4 个字符全是0那么zero[i] true。否则zero[i] false。为什么不在压缩后的字符串上判断 其实也可以因为非全零组压缩后至少有一个非零字符全零组压缩后是0。 但用原始标记数组的好处是把“去前导零”和“找连续零段”两件事完全解耦了。 你去前导零的时候顺便把标记打好后面滑动窗口只看标记数组不用再去关心字符串内容。这个思路很像很多题里的“差分标记”先把条件抽象成布尔序列再用滑动窗口去扫描连续true的最长段。 以后你遇到“最长连续有效括号”“最长连续空闲内存块”这类问题都可以用同一套模板。2.3 滑动窗口找最长连续零段的利器滑动窗口在这里不需要维护什么和值、哈希表之类的东西它本质上是双指针扫描连续区间。具体逻辑是用两个指针i和j。从前往后找zero[i] true的起点。从i开始往后延伸直到遇到false或数组结束得到一段连续true的区间[i, j-1]。记录这段的长度len j - i和全局最优比较。然后令i j继续找下一段。因为每一段只被扫描一次所以复杂度是 O(n)。 这里的n是 8但就算n是几十万这个写法也一样有效。很多同学会问这真的是“滑动窗口”吗 在我看来滑动窗口的核心就是“窗口的右端点不断向右扩展左端点跳跃式前进窗口内的状态只更新一次”。 这里虽然没有常见的while循环收缩窗口但双指针向外扩展、跳跃前进的骨架已经在了。 更准确地说这道题用到的是一种“扫描连续块”的双指针技巧和滑动窗口的思维是一脉相承的。2.4 这题的零段选择规则有了标记数组选择规则就很好表达了如果最长连续零段长度maxLen 2就压缩这一段。如果maxLen 2不压缩任何零段。如果有多个长度相等的最长段选最左边的那一段。最后一个规则在代码里体现在更新条件上。 扫描是从左往右的当你用len bestLen更新最优段时第一次遇到的最长段会被保存后面遇到同样长度的段因为len bestLen不成立不会被替换自然就保留了左边的。 这也是一个很典型的“严格大于”用法。3. 完整实现与逐步拆解3.1 输入解析与分组题目输入是完整 IPv6 地址用cin s直接读字符串就行因为地址里没有空格。 如果题目数据里可能有空行建议用getline(cin, s)前先确保前面没有残留换行符。分组时我的做法是遍历字符串遇到冒号就把当前累积的cur放进groups然后清空否则把字符追加到cur。 遍历结束后再把最后一个cur放进去。string s; cin s; vectorstring groups; string cur; for (char c : s) { if (c :) { groups.push_back(cur); cur.clear(); } else { cur c; } } groups.push_back(cur);这里有一个小细节如果输入是完整的 8 组groups.size()一定是 8。 如果你不放心可以在分组后检查一下不是 8 就说明输入格式有异常但 OJ 数据一般不会这样。3.2 预处理去前导零与打标记分组之后对每一组做两件事去前导零、打全零标记。去前导零时最忌讳把全零组处理成空串。 我见过不少同学这里写了个substr(pos)结果全零组直接变成后面输出就各种报错。我的处理方式是int n groups.size(); vectorint zero(n, 0); vectorstring comp(n); for (int i 0; i n; i) { int pos 0; while (pos groups[i].size() groups[i][pos] 0) { pos; } if (pos groups[i].size()) { comp[i] 0; zero[i] 1; } else { comp[i] groups[i].substr(pos); zero[i] 0; } }zero[i] 1表示这一组原始全是零将来可以参与::压缩。 注意这里判断的是“原始是否全零”不是压缩后是否等于0。 比如0000压缩后是0但标记为全零而0001压缩后是1不能参与压缩。3.3 滑动窗口扫描逻辑这段代码只有十几行但整个题的核心都在这里int bestStart -1; int bestLen 0; int i 0; while (i n) { if (!zero[i]) { i; continue; } int j i; while (j n zero[j]) { j; } int len j - i; if (len bestLen) { bestLen len; bestStart i; } i j; } if (bestLen 2) { bestStart -1; }这个循环为什么能保证“等长选左” 因为只有当len bestLen时才更新。 从左往右扫如果第一段和第二段长度一样第一段已经存进了bestLen和bestStart第二段无法通过len bestLen的条件所以不会被覆盖。如果bestLen等于 1说明最长连续全零段只有 1 个按 RFC 5952 不能压缩所以把bestStart置为 -1。 这里如果不处理后面会进入压缩分支输出错误结果。3.4 重建输出的边界处理重建输出是这道题最容易翻车的地方。 先把压缩区间记作[L, R]其中R bestStart bestLen - 1。如果没有压缩区间直接输出全部comp用冒号连接if (bestStart -1) { for (int k 0; k n; k) { if (k) cout :; cout comp[k]; } cout \n; return 0; }如果有压缩区间需要分成前缀、::、后缀三段拼接int L bestStart; int R bestStart bestLen - 1; // 输出前缀 [0, L-1] for (int k 0; k L; k) { if (k) cout :; cout comp[k]; } cout ::; // 输出后缀 [R1, n-1] for (int k R 1; k n; k) { if (k R 1) cout :; cout comp[k]; } cout \n;这里最关键的注意点是后缀循环里第一个后缀组前面不要加额外的冒号。 因为::本身已经提供了分隔作用。 如果加了就会输出成:::...必错。前缀循环里k从 0 开始当k0时不加冒号。 前缀最后一项后面不加冒号因为后面直接跟::而且::的前一个冒号正好扮演分隔符。 你可能会觉得2001:db8::里::前面的冒号就是分隔符所以不需要单独补。3.5 完整代码C17把上面所有部分拼起来就是一份能直接提交的代码#include bits/stdc.h using namespace std; int main() { string s; cin s; vectorstring groups; string cur; for (char c : s) { if (c :) { groups.push_back(cur); cur.clear(); } else { cur c; } } groups.push_back(cur); int n groups.size(); vectorint zero(n, 0); vectorstring comp(n); for (int i 0; i n; i) { int pos 0; while (pos groups[i].size() groups[i][pos] 0) pos; if (pos groups[i].size()) { comp[i] 0; zero[i] 1; } else { comp[i] groups[i].substr(pos); zero[i] 0; } } int bestStart -1; int bestLen 0; int i 0; while (i n) { if (!zero[i]) { i; continue; } int j i; while (j n zero[j]) j; int len j - i; if (len bestLen) { bestLen len; bestStart i; } i j; } if (bestLen 2) bestStart -1; if (bestStart -1) { for (int k 0; k n; k) { if (k) cout :; cout comp[k]; } cout \n; return 0; } int L bestStart; int R bestStart bestLen - 1; for (int k 0; k L; k) { if (k) cout :; cout comp[k]; } cout ::; for (int k R 1; k n; k) { if (k R 1) cout :; cout comp[k]; } cout \n; return 0; }这份代码在洛谷上实测是能过的。 如果用 Python 写逻辑完全一样只是分组可以用s.split(:)去前导零可以用str(int(part), x)之类的转换但要注意int()会把很大的十六进制转成十进制然后再转回来稍微绕一点。 更直接的写法是手动去前导零。4. 易错点与调试实录4.1 “单个 0 到底能不能压缩”这是我认为这道题最阴险的陷阱。按照 RFC 5952::不能只表示一个全零组。 你可以理解为::是一种“省略号”它至少省略了两个组否则省不省没有意义而且会导致地址表示不唯一。如果题目没有特别说明绝大多数情况下都应该按 RFC 5952 来。 我在代码里用了if (bestLen 2) bestStart -1;这一行来兜底。 没有这一行的话遇到下面这样的输入就会错2001:0db8:0000:0001:0002:0003:0004:0005压缩组是2001:db8:0:1:2:3:4:5只有一个零组。 如果错误地把0压缩成::输出会变成2001:db8::1:2:3:4:5从视觉上看似乎更短但不符合规范。 判题程序如果按标准做你这一分就没了。4.2 冒号拼接翻车现场我调试时遇到过一种很隐蔽的错误前缀为空时输出的字符串多了个冒号。比如输入是全零开头0000:0000:0000:0000:0000:0000:0000:0001正确输出应该是::1因为前缀为空::直接跟后缀第一个组。但如果有人在后缀循环里写成了for (int k R 1; k n; k) { cout : comp[k]; }那么::后面会先输出一个冒号变成:::1。 这个问题在只有前缀为空或后缀为空时特别容易暴露。 所以重建字符串时一定要想清楚::本身就是一个完整的边界分隔符后面不需要再补分隔符。我个人的习惯是先把前缀拼出来再拼::最后拼后缀。 后缀循环里用一个bool first true或if (k R 1)来控制是否加冒号这样最安全。4.3 等长零段靠左还是靠右再来看一个例子1:0:0:2:0:0:3:4这里有两段长度相同的全零段分别是组 1~2 和组 4~5。 按规则必须压缩最左边那段所以正确输出是1::2:0:0:3:4而不是1:0:0:2::3:4如果你在更新最优段的时候用了len bestLen那么扫描到第二段时会因为len bestLen而覆盖掉第一段从而输出后者。 这也是为什么必须用严格大于。这个坑非常隐蔽因为很多“最长”问题都是取最后一个最长段但 IPv6 压缩规则偏偏要最左边。 所以每次看到“如果长度相同取靠前/靠后”这种附加条件就要马上检查比较符号。4.4 输入格式里的隐藏坑题目说每组固定 4 位但有些测试点可能给的是大写字母。 比如ABCD。 我们的代码不区分大小写因为去前导零只看字符是不是0处理大写和小写没有区别。 但如果题目要求输出小写那就需要在输出前统一转小写。 我记得洛谷原题的数据没有在这个地方卡人不过稳妥起见可以在预处理时把所有字母转成小写。另外有些同学会用scanf(%x)之类的读入方式把每组十六进制直接读成整数。 这样也可以但要注意读成整数后你仍然需要把它转回十六进制字符串而且必须保留有效位不能丢掉0。 比如原始组0000读成整数 0转回字符串也是0没问题原始组0abc读成整数转回字符串要补零吗 不需要因为去前导零后本来就是abc。 所以这个方案也可以但秒数不如字符串处理直观。4.5 用随机数据验证思路调试字符串拼接类题目最有效的办法就是自己写一个随机测试工具。我当时写了一个脚本生成 8 组随机的四位十六进制数拼成完整地址然后分别跑“正确实现”和“我要调试的实现”对比输出。 跑了 10 万组随机数据很快就定位到了单个零组压缩的问题。具体做法是在 C 里用rand()生成每组值组装成字符串调你的函数同时自己手写一个非常朴素、按规则枚举所有零段的暴力版本作为基准。 如果两个版本结果不一致就打印这条测试数据。 这个过程看似简单但能省下大量手工构造样例的时间。5. 一点实战心得这道题让我印象最深的不是 IPv6 本身而是“标记数组 滑动窗口”这种组合的普适性。 你可以把任何“在一串元素中找最长连续满足某条件子段”的问题都套进这个框架先用一个布尔数组把条件固化再用双指针扫出所有连续段最后在连续段里做选择。 无论这个问题是找最长全零段还是找最长连续空闲内存还是找最长连续递增区间思路都一样。另外写这类题一定要对“边界条件”有执念。 单个 0 能不能压、前缀为空怎么拼、等长段选左还是右这些不是题目故意刁难你而是真实网络协议中必须明确约定的事情。 代码可以写得快但要想得慢。最后分享一个小技巧如果你在洛谷交了这道题建议把样例的几种特例都手动过一遍特别是::1、2001:db8::这种压缩段落在开头或末尾的情况。 其实你不用背题只需要记得一句话::是边界不是普通的分隔符拼接时把它当成一个整体来对待错误率能降低一大半。