洛⾕P2815IPv6地址压缩题解
P2815 IPv6地址压缩
题⽬背景
（友情提⽰：IPv6基础知识曾多次出现在NOIP初赛中）Internet Protocol，互联⽹协议，即为我们常说的IP。我们⽬前常说的IP主要指它的第四版，即IPv4，它由IETF于1981年发布。它的地址长度是32个⼆进制位，因此也就有2^32个IP地址可供使⽤，约为43亿，在当时，谁也没有料想到IPv4如此庞⼤的地址长度会有⽤完的⼀天。
在21世纪的今天，互联⽹的蓬勃发展早就了我们如今便利的⽣活。当下，世界⼈⼝已超过70亿，计算机和各种联⽹设备已经⾛⼊千家万户，⽽不再仅是上个世纪80年代科学家们的⼯具。此时便出现了⼈们⽇益增长的联⽹设备需要同落后IPv4地址长度之间的⽭盾。尽管可以通过⽹络地址翻译能技术来共享IP地址，临时解决枯竭的问题，但显然不是长久之计。
IETF也有先见之明，早早地于1998年发布了IPv6协议，从微软2006年发布的Windows Vista开始成为默认安装的⽹络协议。作为IPv4的继任者，它的地址长度为128个⼆进制位，也就是2^128个IP地址可供使⽤。然⽽⾯对这冗长的地址，⼀位记忆⼒不好的⽹络⼯程师⼩明在配置路由表时遇到了许许多多多的困难，现在他到了你，希望你帮忙编写⼀个程序来按照IPv6地址标准的格式压缩规则来压缩IPv6地址。题⽬描述
IPv6格式
IPv6⼆进位制下为128位长度，以16位为⼀组，每组以冒号“:”隔开，可以分为8组，每组以4位⼗六进制⽅式表⽰。
例如：2001:0db8:0000:0000:0123:4567:89ab:cdef 是⼀个合法的IPv6地址。
同时IPv6地址在某些条件下可以压缩：
①每组数字代表的独⽴16进制数可以省略前位的0。
例如上⾯的IPv6地址可被压缩为：
2001:db8:0:0:123:4567:89ab:cdef
②可以⽤双冒号“::”表⽰⼀组0或多组连续的0，但只能出现⼀次
例如上⾯的IPv6地址可被压缩为：
2001:db8::123:4567:89ab:cdef
请你帮助记忆⼒不好的⽹络⼯程师⼩明解决他遇到的问题。
规则补充：
①输⼊数据为完全展开的IPv6地址，确保输⼊的IPv6地址不含双冒号，每组地址省略的0都会被补充上去。
②双冒号只能使⽤⼀次，因此我们压缩最长的全0组
⽐如：2001:0db8:0000:0000:1:0000:0000:0000
我们压缩为2001:db8:0:0:1::，⽽⾮2001:db8::1:0:0:0
③双冒号只能只⽤⼀次，因此我们在我们遇到地址中多个连续全0组长度相同时，我们压缩最前⾯的⼀个。
2001:0db8:0000:0000:ffff:0000:0000:1
压缩为2001:db8::ffff:0:0:1，⽽⾮2001:db8:0:0:ffff::1
④输⼊的IPv6地址可能⽆法被压缩，因此请照原样输出。
提⽰：本题所⽰的压缩规则与macOS(Darwin)默认的IPv6地址显⽰⽅式相同，⽽Windows和Linux只遇
到⼀组全0时不会使⽤:：进⾏压缩。但⽤此⽅法压缩过的IPv6地址⼀样可以被Windows和Linux正确识别。
例如：2001:0db8:ffff:0000:0123:4567:89ab:cdef
Darwin压缩为：2001:db8:ffff::123:4567:89ab:cdef
Linux、Windows压缩为：2001:db8:ffff:0:123:4567:89ab:cdef 输⼊格式
⼀串39个字符的字符串，代表⼀个完全展开的IPv6地址
输出格式
⼀串压缩后的IPv6地址
输⼊输出样例
输⼊ #1
240e:0014:6000:0000:0000:0000:0000:0001
输出 #1
240e:14:6000::1
输⼊ #2
2001:0db8:0000:0000:0000:0000:0000:0001
输出 #2
2001:db8::1
输⼊ #3
2001:4860:4860:0000:0000:0000:0000:8888
输出 #3
2001:4860:4860::8888
输⼊ #4
2400:8900:e000:0010:0000:0000:0000:0000
输出 #4
2400:8900:e000:10::
输⼊ #5
0000:0000:0000:0000:0000:0000:0000:0000
输出 #5
::
输⼊ #6
0000:0000:0000:0000:0000:0000:0000:0001
输出 #6
::1
输⼊ #7
2001:0db8:ffff:0000:0123:4567:89ab:cdef
输出 #7
2001:db8:ffff::123:4567:89ab:cdef
输⼊ #8
1234:5678:9abc:def0 5678:9abc:def0
输出 #8
1234:5678:9abc:def0 5678:9abc:def0
输⼊ #9
0001:0000:0000:0000:0000:0000:0000:0001
输出 #9
1::1
输⼊ #10
0000:0000:0000:0000:0000:0000:0001:0002
输出 #10
::1:2
【思路】
模拟
【题⽬⼤意】
将完整的的IPv6的显⽰⽅式压缩为macOS(Darwin)默认的IPv6地址显⽰⽅式【题⽬分析】
压缩⽅式即为：
将每⼀组数（每⼀组数是没有被：隔开的连续的4个数）的前导0去掉
不过如果是0000那就只能压缩为0
将最长的连续的0000这样的串可以压缩为::
⽐如0000:0000:0000:0000就可以压缩为::
如果有两个相同长度的那就替换前⾯的
【核⼼思路】
先出最长的连续0000串第⼀个数的位置
到时输出输出完成:：之后直接跳到这个串的最后⼀位就好了
总的来说上⾯这个还是⽐较好处理的
去除前导0才是最难的
这个时候就会有⼈说了，这不就是⼀个while循环搞的定的嘛，哪⾥难了
这个时候很容易会Wa掉第⼀个点
本⼈就出在这个问题上⾯
因为⼀般⽤while循环判断是不是这组数的最后⼀个⼀般会⽤下⼀个是不是：来判断但是！
想没想过最后⼀组数的最后⼀位怎么判断？这个后⾯可没有:
很容易被忽略的哦
但是知道问题所在之后稍微特判⼀下就可以了
【提供⼀组⼩数据】
关于第⼀个点错误的样例
abcd:0000:0000 0012:0000:0001:0000
正解： abcd: 12:0:1:0
错解： abcd: 12:0:1:
【完整代码】
#include<iostream>
#include<cstdio>
#include<cstring>.
#include<string>
using namespace std;
string s;
int main()
{
cin >> s;
int l = s.length();
int a = 0;
int js = 0;//记录⽬前0串的长度
int M = 0;//记录最⼤的⼏组0的长度
int wz = -1;//最长0那⼀串中第⼀个0的位置
int last = -1;//上⼀个0串的位置
for(register int i = 0;i < l;i += 5)
{
if(s[i] == '0' && s[i + 1] == '0' && s[i + 2] == '0' && s[i + 3] == '0')//⼀组完整的0
{
if(last == i - 5)
{
last = i;
}
else
{
js = 0;
last = i;
a = i;
}
js ++;
}
if(js > M)
{
M = js;
wz = a;
}
}
int jj = 0;
while(jj < l)
{
if(jj == wz)
{
if(jj == 0)
cout << ":";
jj += M * 5 - 1;
if(jj == l)
cout << ":";
}
else
{
if(jj % 5 == 0)
{
if(jj >= 35)//如果是最后⼀组的话，那就不能根据下⼀个是不是：来判断这个0是不是这组数中最后⼀个数了 {
while(s[jj] == '0' && jj + 1 != l)
{
jj ++;
字符串长度压缩}
}
else
{
while(s[jj] == '0' && s[jj + 1] != ':')
{
jj ++;
}
}
}
cout << s[jj];
jj ++;
}
}
cout << endl;
return 0;
}
/*
2001:0db8:0000:0000:0123:4567:89ab:cdef 012345678901234567890123456789012345678
abcd:0000:0000:abcd:0012:0000:0001:0000
*/
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。
发表评论