题解 P2815 【IPv6地址压缩】
0AND1STORY
2019-01-26 21:14:14
看到很多大佬都在用
```cpp
scanf("%x:%x:%x:%x:%x:%x:%x:%x",&s[1],&s[2],&s[3],&s[4],&s[5],&s[6],&s[7],&s[8]);
```
读入16进制，我就纯粹读入一个**字符串**然后处理也可做到一样的效果
通过题目很容易就想到做法，步骤如下
1. 去掉前导零
```cpp
s = ":" + s; //先在s前加一个`:`便于去掉前导零
for (int i = 1; i < s.size(); i ++)
{
//如果在`:`后有`0`则有前导零，进行删除
if (s[i - 1] == ':' && s[i] == '0')
s.erase(s.begin() + i, s.begin() + i + 1),
i --;
}
s.erase(s.begin(), s.begin() + 1); //删掉先前加的`:`
```
2. 将连续零个数最多的地方换成`::`
```cpp
for (int i = s.size() - 1; i >= 0; i --)
{
//因为前面删掉了冒号后的所有0，所以判断连续冒号数即可判断连续0的个数
if (s[i] == ':')
f[i] = f[i + 1] + 1;
else
f[i] = 0;
if (f[i] >= maxl) //更新最优解
maxp = i,
maxl = f[i];
}
//删除冒号即可将连续0改为`::`
for (int i = 2; i < maxl; i ++)
s.erase(s.begin() + maxp, s.begin() + maxp + 1);
//将原来删掉的0000还原为0(即在s中的两个冒号中加上0，压缩后的双冒号除外)
for (int i = 0; i < s.size() - 1; i ++)
{
if (s[i] == ':' && s[i + 1] == ':' && i != maxp)
s.insert(s.begin() + i + 1, '0');
}
```
### AC代码如下：（通过，但不全对）
```cpp
#include <iostream>
#include <string>
using namespace std;
//读入的ipv6地址
string s;
//用模拟找最多连续0的地址
int f[50], maxp, maxl;
int main()
{
ios::sync_with_stdio(false); //读入优化
cin >> s;
s = ":" + s; //先在s前加一个`:`便于去掉前导零
for (int i = 1; i < s.size(); i ++)
{
//如果在`:`后有`0`则有前导零，进行删除
if (s[i - 1] == ':' && s[i] == '0')
s.erase(s.begin() + i, s.begin() + i + 1),
i --;
}
s.erase(s.begin(), s.begin() + 1); //删掉先前加的`:`
for (int i = s.size() - 1; i >= 0; i --)
{
//因为前面删掉了冒号后的所有0，所以判断连续冒号数即可判断连续0的个数
if (s[i] == ':')
f[i] = f[i + 1] + 1;
else
f[i] = 0;
if (f[i] >= maxl) //更新最优解
maxp = i,
maxl = f[i];
}
//删除冒号即可将连续0改为`::`
for (int i = 2; i < maxl; i ++)
s.erase(s.begin() + maxp, s.begin() + maxp + 1);
//将原来删掉的0000还原为0(即在s中的两个冒号中加上0，压缩后的双冒号除外)
for (int i = 0; i < s.size() - 1; i ++)
{
if (s[i] == ':' && s[i + 1] == ':' && i != maxp)
s.insert(s.begin() + i + 1, '0');
}
if (s[s.size() - 1] == ':' && s[s.size() - 2] != ':') //修复BUG用的小补丁
s += '0';
cout << s << endl;
return 0;
}
```
### AC代码（完全正确）：
```cpp
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
//读入的ipv6地址
string s;
//用模拟找最多连续0的地址
int f[50], maxp, maxl;
int main()
{
ios::sync_with_stdio(false); //读入优化
cin >> s;
s = ":" + s; //先在s前加一个`:`便于去掉前导零
for (int i = 1; i < s.size(); i ++)
{
//如果在`:`后有`0`则有前导零，进行删除
if (s[i - 1] == ':' && s[i] == '0')
s.erase(s.begin() + i, s.begin() + i + 1),
i --;
}
for (int i = s.size() - 1; i >= 0; i --)
{
//因为前面删掉了冒号后的所有0，所以判断连续冒号数即可判断连续0的个数
if (s[i] == ':')
f[i] = f[i + 1] + 1;
else
f[i] = 0;
if (f[i] >= maxl) //更新最优解
maxp = i,
maxl = f[i];
}
//删除冒号即可将连续0改为`::`
for (int i = 2; i < maxl; i ++)
s.erase(s.begin() + maxp, s.begin() + maxp + 1);
s.insert(s.begin() + maxp + 1, '*');
s.erase(s.begin(), s.begin() + 1); //删掉先前加的`:`
//将原来删掉的0000还原为0(即在s中的两个冒号中加上0，压缩后的双冒号除外)
for (int i = 0; i < s.size() - 1; i ++)
{
if (s[i] == ':' && s[i + 1] == ':')
s.insert(s.begin() + i + 1, '0');
}
//以下都是修复BUG用的小补丁
if (s[0] == ':' && s[1] != '*')
s.insert(s.begin(), '0');
for (int i = 0; i < s.size(); i ++)
if (s[i] == '*')
{
if (i != 0)
s.erase(s.begin() + i, s.begin() + i + 1);
else
s[i] = ':';
break;
}
if (s[0] == ':' && s[1] != ':')
s.erase(s.begin(), s.begin() + 1);
if (s[s.size() - 1] == ':' && s[s.size() - 2] != ':')
s += '0';
cout << s << endl;
return 0;
}
```
### 另外附上我调试用的对拍程序：
```cpp
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <windows.h>
using namespace std;
//不用在意这些宏定义，方便写代码
#define main int main
#define init_rand srand(time(NULL));
#define LPFILE FILE*
#define infile(name) fopen(name, "w");
#define for(x, l, r) for(int x = l; x <= r; x ++)
#define end return 0;
main()
{
init_rand
while (true)
{
LPFILE fin = infile("test.in")
for (i, 1, 7)
fprintf(fin, "%04x:", rand() % 2 ? rand() % 0x10000 : 0);
fprintf(fin, "%04x\n", rand() % 0x10000);
fclose(fin);
system("type test.in");
system("my.exe < test.in > my.out");
system("right.exe < test.in > right.out");
if (system("fc my.out right.out"))
//弹出一个窗口，方便挂机查看
MessageBox(NULL, "找到差异，请查看！", "找到差异", MB_OK | MB_ICONERROR),
system("pause");
}
end
}
```