B - Shorten IPv6 Address
题意
给你(128)位的二进制，转换为十六进制。
每(4)位十六进制分为(1)组，每两组用一个(“:”)分开。
每一组的十六进制要去掉前导(0)。
如果存在连续两组以上的(0)要转换为(“::”)。比如，(0:0:0、0:0)都可以转换成("::")。
但是最多只能转换一次，要求在长度最短的条件下字典序最小。
思路
- 先把二进制串转换为16进制串
- 找到最长连续的(0)的位置转换为(“::”)，如果长度相等，头和尾优先选尾，头和尾和中间，优先选中间。（长度相同，选中间会比选头或者尾短一个长度）
三种不同的选法（明显中间最短，且最优）
0:0:1:0:0:1:0:0
前：::1:0:0:1:0:0
后：0:0:1:0:0:1::
中：0:0:1::1:0:0
一些数据
1
00000000000000000000000000000000000000000000111100000000000000000000000000000000000000001111111100000000000000000000000000000000
Case #1: 0:0:f::ff:0:0
一些乱七八糟的感想
其实就是一个模拟啦，刚开始暴力选长度最长，相等全部给我往后走，然后就(WA)了， 作为一个专业划水选手，我就在旁边看着队友的代码一步步从(50)行到(100)行，到最后接近(200)行，三个人找不到错误，找到上面这个样例之后，发现还是(WA)，最后还是用暴力找全部，然后找答案。看了题解之后发现好像没有其他的坑。嗯。。。吸取队友的经验，还是尝试写了一下代码，锻炼一下写代码的能力？，嗯。。。好像没有比赛的时候想的那么麻烦。嗯。。还是要努力呀，不能老是拖后腿呀。
AC 代码
#include<bits/stdc++.h>
using namespace std;
const int maxn = 200;
char ch[maxn];
int a[10][6];
int main(){
int T, Cas = 1;
scanf("%d", &T);
while(T--){
scanf("%s", ch+1);
int cnt = 0;
for(int i = 1; i <= 128;){
cnt++;
for(int k = 1; k <= 4; k++){ //每4个十六进制为1组
a[cnt][k] = 0;
for(int j = 3; j >= 0; j--,i++){ //每4位二进制转换一个十六进制
a[cnt][k] += (ch[i]-'0')*(1<<j);
}
}
}
int l, r, wl, wr; //变成::的位置
l = 1;r = 0;wl = 0, wr = -1;
for(int i = 1; i <= cnt; i++){
int flag = 0;
for(int j = 1; j <= 4; j++){
if(a[i][j] != 0){
flag = 1;
break;
}
}
if(!flag){ //当前为0
r++;
}
if(flag || i == cnt){ //当前不为0或者读到末尾
if(r-l+1 > wr-wl+1 && r-l+1 >= 2){
wl = l;wr = r;
}
else if(r-l+1 == wr-wl+1 && r-l+1 >= 2 && (r != cnt || wl == 1)){
wl = l;wr = r;
}
l = i+1;r = i;
}
}
printf("Case #%d: ", Cas++);
for(int i = 1; i <= cnt; i++){
if(i == wl){
if(i == 1)
printf(":");
printf(":");
if(wr == cnt)
printf("
");
i = wr;
}
else{
int flag = 0;
for(int j = 1; j <= 4; j++){
char s = a[i][j] >= 10?a[i][j]-10+'a':a[i][j]+'0';
if(!flag && (a[i][j] != 0 || j == 4)){ //去前导0
flag = 1;
}
if(flag)
printf("%c", s);
}
printf("%c", i == cnt?'
':':');
}
}
}
return 0;
}