[牛客暑期多校第六场][模拟+思想]B-Shorten IPv6 Address

发布于 2019-08-13  888 次阅读


https://ac.nowcoder.com/acm/contest/886/B

一道有点坑点的题 题意 给定一个128位的01字符串 请简化这个字符串
128位 每4位代表一个16进制的数字 每16位代表4个16进制的数字 把128位的字符串转化为128/4=32位的16进制的字符串 其中每4个之间用:分割开 所以一共是32/4=8段 首先每段的前导0可以省略
其次 4个0可以化为0 可以把2个及2个以上的全0段 化简为:: 但是注意只能化简一次
输出最短的 多个相同输出字典序最小的
思路:
首先找出最长的0来 把最长的0段化简 前导0就不说了
但是如果两个长度相等的全0段出现在不同位置 那么就是一个坑点了
0:0:0:x:x:x:x:x ---->::x:x:x:x:x
x:x:x:0:0:0:x:x--->x:x:x::x:x
发现没有!省略中间的会短一个:!
明白了这一点代码就好写了

#include<algorithm>
#include<iostream>
#include<vector>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<string>
#include<ctime>
#include<map>
#include<stack>
#include<set>
#include<cstring>
#include<sstream>
#include<queue>
#include<iomanip>
using namespace std;
typedef long long ll;
 
int Toint(string s)
{
    int ans = 0;
    int k = 1;
    for (int i = 15; i >= 0; --i)
    {
        ans += k * (s[i] - '0');
        k *= 2;
    }
    return ans;
}
 
int a[10];
 
void Solve(string s)
{
    memset(a, 0, sizeof(a));
    for (int i = 0; i <= 112; i += 16)
    {
        string t = s.substr(i, 16);
        a[i / 16] = Toint(t);
    }
    int k = 0;
    int pos = -1;
    int mx = 2;
    for (int i = 0; i < 8; ++i)
    {
        if (a[i] == 0)
        {
            k++;
            if (k >= mx)
            {
                if (pos == 0 || pos + mx - 1 == 7)
                {
                    pos = i - k + 1;
                    mx = k;
                }
                else
                {
                    if (k != mx)
                    {
                        pos = i - k + 1;
                        mx = k;
                    }
                    else
                    {
                        if (i - k + 1 == 0 || i == 7)
                        {
                            if (pos == -1 || pos == 0) pos = i - k + 1;
                            //continue;
                        }
                        else
                        {
                            pos = i - k + 1;
                            mx = k;
                        }
                    }
                }
 
            }
        }
        else k = 0;
    }
    int f = 1;
    for (int i = 0; i < 8; ++i)
    {
        if (f)
        {
            f = 0;
            if (i == pos)
            {
                cout << "::";
                i += mx;
                i--;
                f = 1;
            }
            else cout << hex << a[i];
        }
        else
        {
 
            if (i == pos)
            {
                cout << "::";
                i += mx;
                i--;
                f = 1;
            }
            else
            {
                cout << ':';
                cout << hex << a[i];
            }
        }
    }
    cout << endl;
}
int main()
{
    int T;
    cin >> T;
    for (int i = 1; i <= T; i++)
    {
        string s;
        cin >> s;
        printf("Case #%d: ", i);
        Solve(s);
    }
    return 0;
}

愿风指引你的道路,愿你的刀刃永远锋利。