P7911 [CSP-J 2021] 网络连接（民间数据）题解

· · 题解

本篇题解将讲解如何判断一个地址是否合法。

首先是格式问题，如何判断地址是否符合 a.b.c.d:e 形式。

我们只需要找这个地址中 . 和 : 的个数，并判断是否有相邻的 . 或者 .: 并且判断是否有 : 在 . 的前面，在考场代码中，我顺便把是否有前导零判断了，代码如下：

    if(s[0]>'9'||s[0]<'0'||s[len-1]>'9'||s[len-1]<'0')
        return false;//卡掉.0.0.0:0
    for(int i=0;i<len;i++)
        if(s[i]=='.'){
            if(s[i+1]=='0'&&s[i+2]!='.'&&s[i+2]!=':'&&i<len-2)
                return false;
            res++;
        }
    if(res!=3)
        return false;//卡掉0.0.0:0
    res=0;
    for(int i=0;i<len;i++)
        if(s[i]==':'){
            if(s[i+1]=='0'&&s[i+2]!='.'&&s[i+2]!=':'&&i<len-2)
                return false;
            res++;
        }
    if(res!=1)
        return false;//卡掉0.0.0.0:0:0
    for(int i=0;i<len-1;i++)
        if((s[i]<'0'||s[i]>'9')&&(s[i+1]<'0'||s[i+1]>'9'))
            return false;//卡掉0..0.0:0
    for(int i=0;i<len-1;i++)
        for(int j=i+1;j<len;j++)
            if(s[i]==':'&&s[j]=='.')
                return false;//卡掉 0:0.0.0.0

其次是处理出 a,b,c,d,e 的数值。按照原题，len\leq25，在极限情况下会卡到 0.0.0.0:99999999999999999\ (10^{18}-1)。也就是开 long long 就不存在精度问题。

我们只需要类似于快读的处理方法即可，代码如下：

int i=0;
    while('0'<=s[i]&&s[i]<='9'&&i<len){
        a=10*a+s[i]-'0';
        i++;
    }
    i++;
    while('0'<=s[i]&&s[i]<='9'&&i<len){
        b=10*b+s[i]-'0';
        i++;
    }
    i++;
    while('0'<=s[i]&&s[i]<='9'&&i<len){
        c=10*c+s[i]-'0';
        i++;
    }
    i++;
    while('0'<=s[i]&&s[i]<='9'&&i<len){
        d=10*d+s[i]-'0';
        i++;
    }
    i++;
    while('0'<=s[i]&&s[i]<='9'&&i<len){
        e=10*e+s[i]-'0';
        i++;
    }
    if(a>MAXA||b>MAXA||c>MAXA||d>MAXA||e>MAXE)
        return false;

这样我们就可以判断一个地址是否合法了。

剩下的工作就是用 map 乱搞了，考场完整代码戳这里。