按冒号切成 8 组后分别去前导零，再找最前面的最长连续 0000 段，用一次 :: 替换即可。
OJ: luogu
题目 ID: P2815
难度:入门
标签:字符串模拟
日期: 2026-06-20 16:03
题意
输入一个已经完全展开的 IPv6 地址：
- 一共 8 组
- 每组恰好 4 位十六进制数
- 各组之间用
:分隔
要求按照题目给定的规则进行压缩：
- 每组可以去掉前导零；
- 可以把一段连续的全零组压成一次
::； ::只能用一次；- 要压最长的一段，若并列则压最前面那一段。
思路
先看一个更直接的校验版本：
cpp
#include <bits/stdc++.h>
using namespace std;
string s;
string part[10];
string short_part[10];
string trim_leading_zero(const string &t) {
int i = 0;
while (i < 4 && t[i] == '0') {
i++;
}
if (i == 4) {
return "0";
}
return t.substr(i);
}
string build_answer(int l, int r) {
string left = "";
for (int i = 1; i < l; i++) {
if (!left.empty()) {
left += ':';
}
left += short_part[i];
}
string right = "";
for (int i = r + 1; i <= 8; i++) {
if (!right.empty()) {
right += ':';
}
right += short_part[i];
}
if (l > r) {
if (left.empty()) {
return right;
}
if (right.empty()) {
return left;
}
return left + ":" + right;
}
if (left.empty() && right.empty()) {
return "::";
}
if (left.empty()) {
return "::" + right;
}
if (right.empty()) {
return left + "::";
}
return left + "::" + right;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> s;
int idx = 1;
int last = 0;
for (int i = 0; i <= (int)s.size(); i++) {
if (i == (int)s.size() || s[i] == ':') {
part[idx++] = s.substr(last, i - last);
last = i + 1;
}
}
for (int i = 1; i <= 8; i++) {
short_part[i] = trim_leading_zero(part[i]);
}
string best = build_answer(2, 1); // 表示不使用 ::
int best_len = 0;
int best_l = -1, best_r = -1;
for (int l = 1; l <= 8; l++) {
for (int r = l; r <= 8; r++) {
bool ok = true;
for (int i = l; i <= r; i++) {
if (part[i] != "0000") {
ok = false;
break;
}
}
if (!ok) {
continue;
}
int len = r - l + 1;
if (len > best_len) {
best_len = len;
best_l = l;
best_r = r;
}
}
}
if (best_len > 0) {
best = build_answer(best_l, best_r);
}
cout << best << '\n';
return 0;
}这题本质上就是字符串模拟，没有复杂算法。
第一步：先拆成 8 组
原串保证已经是完整展开形式，所以我们直接按 : 切开即可。
这样就能得到 8 个长度都为 4 的字符串。
第二步：每组去前导零
对每一组：
- 不断删掉前导
0 - 如果整组都是
0，最后保留成"0"
例如：
0840 -> 8400000 -> 0
第三步：找最长的连续 0000 段
这里要注意一个容易混淆的点：
- 能不能参与
::压缩，要看原始分组是不是"0000" - 不能只看去前导零后的结果是不是
"0"
因为只有完整的全零组，才能用 :: 代替。
于是我们在线性扫描中找出：
- 最长的连续
"0000"段
如果有多段长度相同，只在“更长”时更新答案，这样就自然保留了最前面那一段。
第四步：分三段拼接
如果根本没有 "0000" 组：
- 直接把去前导零后的 8 组用
:连起来
否则：
- 左边输出压缩段前面的内容
- 中间输出一次
:: - 右边输出压缩段后面的内容
这样写可以很自然地处理：
::在开头::在结尾- 整个地址都是零
代码
cpp
#include <bits/stdc++.h>
using namespace std;
string s;
string part[10];
string short_part[10];
string trim_leading_zero(const string &t) {
int i = 0;
while (i < 4 && t[i] == '0') {
i++;
}
if (i == 4) {
return "0";
}
return t.substr(i);
}
string join_parts(int l, int r) {
if (l > r) {
return "";
}
string res = "";
for (int i = l; i <= r; i++) {
if (!res.empty()) {
res += ':';
}
res += short_part[i];
}
return res;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> s;
int idx = 1;
int last = 0;
for (int i = 0; i <= (int)s.size(); i++) {
if (i == (int)s.size() || s[i] == ':') {
part[idx++] = s.substr(last, i - last);
last = i + 1;
}
}
for (int i = 1; i <= 8; i++) {
short_part[i] = trim_leading_zero(part[i]);
}
int best_l = -1, best_r = -1;
int best_len = 0;
int i = 1;
while (i <= 8) {
if (part[i] != "0000") {
i++;
continue;
}
int j = i;
while (j <= 8 && part[j] == "0000") {
j++;
}
int len = j - i;
if (len > best_len) {
best_len = len;
best_l = i;
best_r = j - 1;
}
i = j;
}
// 没有任何一组 0000 时，只做去前导零。
if (best_len == 0) {
cout << join_parts(1, 8) << '\n';
return 0;
}
string left = join_parts(1, best_l - 1);
string right = join_parts(best_r + 1, 8);
if (left.empty() && right.empty()) {
cout << "::\n";
}
else if (left.empty()) {
cout << "::" << right << '\n';
}
else if (right.empty()) {
cout << left << "::\n";
}
else {
cout << left << "::" << right << '\n';
}
return 0;
}复杂度
-
时间复杂度：
因为 IPv6 地址固定只有 8 组。 -
空间复杂度：
总结
这题没有算法难点，主要是规则细节：
- 每组先单独去前导零；
::只看原始的0000连续段；- 压最长，若并列取最前；
- 最后用“左 +
::+ 右”的方式拼接。
把这些细节拆开实现，代码就会很稳。