CCF-CSP 80分

写了3个小时多…结果还是有错
发现了一个很神奇的问题, 记录一下

unsigned int c = 0;
unsigned int b = (1<<(32-c))-1;
unsigned int a = (1<<32)-1;
unsigned int d = (1<<(32-0))-1;
printf("%u  %u  %u  %u",a,b,(1<<(32-0)-1)),d;
//输出结果为4294967295  0  2147483648  793128576

被这个问题困扰了很久

更新:有大佬解答了，戳此转

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stack>
#include<regex>
#include<math.h>
using namespace std;
const int N = 1e6+10;
typedef long long LL;
struct ipinfo{
    int ip1=0, ip2=0, ip3=0, ip4=0, len;
    bool operator < (const ipinfo u) const{   //重载<为了排序
        unsigned int  IP = ip1*256*256*256+ip2*256*256+ip3*256+ip4;
        unsigned int  IPu = u.ip1*256*256*256+u.ip2*256*256+u.ip3*256+u.ip4;
        if (IP!=IPu ) return IP < IPu;
        else return len < u.len;
    }
};
int n;
regex pat1("((\\d+).*)+/(\\d+)$");  // 匹配形如101.6.6.0/24，101.6.6/23，101/8
regex pat2("(\\d+)");  //匹配形如101.6, 101.6.32

ipinfo res1[N], res2[N], iplist[N];

inline void toipinfo1(int cnt, int i, int a[])
{
    if(cnt == 2)
        iplist[i].ip1 = a[0], iplist[i].len = a[1];
    else if (cnt == 3)   
        iplist[i].ip1 = a[0], iplist[i].ip2 = a[1], iplist[i].len = a[2];
    else if (cnt == 4)
        iplist[i].ip1 = a[0], iplist[i].ip2 = a[1], iplist[i].ip3 = a[2], iplist[i].len = a[3];
    else if (cnt == 5){
        iplist[i].ip1 = a[0], iplist[i].ip2 = a[1], iplist[i].ip3 = a[2], iplist[i].ip4 = a[3], iplist[i].len = a[4];
    }
}
inline void toipinfo2(int cnt, int i, int a[])
{
    if(cnt == 1)
        iplist[i].ip1 = a[0], iplist[i].len = 8;
    else if (cnt == 2)
        iplist[i].ip1 = a[0], iplist[i].ip2 = a[1], iplist[i].len = 16;
    else if (cnt == 3)
        iplist[i].ip1 = a[0], iplist[i].ip2 = a[1], iplist[i].ip3 = a[2], iplist[i].len = 24;
    else if (cnt == 4)
        iplist[i].ip1 = a[0], iplist[i].ip2 = a[1], iplist[i].ip3 = a[2], iplist[i].ip4 = a[3], iplist[i].len = 32;
}
inline void outip(int cnt2, ipinfo res[])
{
    for(int i = 0; i < cnt2; i++)
        printf("%d.%d.%d.%d/%d\n", res[i].ip1, res[i].ip2, res[i].ip3, res[i].ip4, res[i].len);
}

inline unsigned int calip(ipinfo a)
{
    return a.ip1*256*256*256+a.ip2*256*256+a.ip3*256+a.ip4;
}

inline bool checkSize(ipinfo a, ipinfo b)  //检查b的匹配集是否是a的匹配集
{
    unsigned int ipa1 = calip(a), ipa2 = ipa1 + (1<<(32-a.len))-1;
    unsigned int ipb1 = calip(b), ipb2 = ipb1 + (1<<(32-b.len))-1;
    if(ipa1 <= ipb1 && ipa2 >= ipb2) return false;
    else return true; // true表示b的匹配集不是a的子集
}

inline bool UnionIsSame(ipinfo a, ipinfo b, ipinfo c)
{
    unsigned int ipa1 = calip(a), ipa2;
    unsigned int offseta = a.len ? (1<<(32-a.len))-1 : (1<<32)-1;
    ipa2 = ipa1 + offseta;
    unsigned int ipb1 = calip(b), ipb2;
    unsigned int offsetb = b.len ? (1<<(32-b.len))-1 : (1<<32)-1;
    ipb2 = ipb1 + offsetb;
    unsigned int ipc1 = calip(c),ipc2;
    unsigned int offsetc = c.len ? (1<<(32-c.len))-1 : (1<<32)-1;
    ipc2 = ipc1 + offsetc;
    if(ipa1 - ipb2 ==1 || ipa2-ipb1 == 1 || ipb2 -ipa1 == 1 || ipb1 - ipa2 == 1)
    {
        if(ipc1 <= ipa1 && ipc1 <= ipb1 && ipc2 >= ipb2 && ipc2 >= ipa2) return true;
    }
    return false;
}
void mergeIpSize(int &top) //从小到大排序合并，按照题目中的思路实现
{
    int m = 1;
    res1[0]=iplist[0];
    top = 0;
    while(m<n)
    {
        auto a = res1[top];
        if(checkSize(a,iplist[m])) res1[++top] = iplist[m]; // checkSize(a,b) 检查b的匹配集是否是a的匹配集
        m++;//匹配则直接跳过
    }
}
int lowbit(int x)
{
    return x & (-x);
}
bool islegal(ipinfo a)
{
    LL ip = calip(a);
    if( lowbit(ip) > pow(2, 32-a.len) || (ip == 0 && a.len == 0 )) return true;
    else return false;
}
void mergeIpLevel(int num,int &top)//同级合并
{
    res2[++top] = res1[0];
    int i = 1;
    while(i <= num)
    {
        ipinfo aop = res2[top];//合并规则一：如果 a 与 b 的前缀长度相同，则设 a′ 为一个新的 IP 前缀，其 IP 地址与 a 相同，而前缀长度比 a 少 1
        aop.len = res2[top].len-1; //a'为新的IP前缀
        if(res2[top].len == res1[i].len && UnionIsSame(res2[top],res1[i],aop)  && islegal(aop)) // 检验是否合乎规则 UnionIsSame(a, b, aop)
        {
            res2[top] = aop, aop.len --; //继续从新的IP开始向前考虑，是否可以继续合并
            while((res2[top-1].len == res2[top].len) && UnionIsSame(res2[top],res2[top-1], aop)&& islegal(aop) && top >= 1) // 检验是否合乎规则 UnionIsSame(a, b, aop)
                res2[top-1] = aop, top --, aop.len --; //继续从新的IP开始向前考虑，是否可以继续合并
        }
        else res2[++top] = res1[i]; //不能合并，则直接加入新列表
        i++;
    }
}

int main()
{
    scanf("%d\n",&n);
    smatch result;
    string str;
    for(int i = 0; i < n; i++)
    {
        getline(cin,str);
        if(regex_match(str, result, pat1)) // 正则匹配pat1
        {
            string::const_iterator iterStart = str.begin();
            string::const_iterator iterEnd = str.end();
            string temp;
            int a[6];
            int cnt = 0;
            while(regex_search(iterStart, iterEnd, result, pat2))//正则匹配将ip按格式匹配并存储
            {
                temp = result[0];
                iterStart = result[0].second;   //更新搜索起始位置,搜索剩下的字符串
                a[cnt++] = stoi(temp);
            }
            toipinfo1(cnt, i, a);
        }else{                          // 正则匹配pat2
            string::const_iterator iterStart = str.begin();
            string::const_iterator iterEnd = str.end();
            string temp;
            int a[6];
            int cnt = 0;
            while(regex_search(iterStart, iterEnd, result, pat2))
            {
                temp = result[0];
                iterStart = result[0].second;   //更新搜索起始位置,搜索剩下的字符串
                a[cnt++] = stoi(temp);
            }
            toipinfo2(cnt, i, a);
        }
    }
    sort(iplist,iplist+n);  //排列
    int cnt1 = 0,cnt2 = -1;
    mergeIpSize(cnt1);
    mergeIpLevel(cnt1,cnt2);
    outip(cnt2+1,res2);
}