CSP認證CIDR合并

這個題已經給出了解決的步驟，按題目的三步走就可以

難點：

• 将ip位址翻譯成long long長整型的整數，進行排序
• 設前一個ip的字首長度為len，前一個ip的前len位==後一個相鄰的ip的前len位，則從ip清單中删除後一個ip字首
• 如果相鄰的兩個ip的字首長度相等，都為len，且則兩個ip的前len位相差1，則兩個ip字首可以合并為一個

代碼喜歡用函數，将複雜的功能分開來寫，便于檢查和了解，代碼長度相應會有些長，大家耐着點性子看哦

#include <iostream>

using namespace std;

#include <string>
#include <list>
#include <math.h>

typedef struct IPBefore{
    long long ip;
    int len;
    int tip;
}IPB;

/*int getPotNum(const string &s) {

}*/

long long getIP(const string &s) {
    long long res = 0, tran;
    int num = 3, i=0;
    while(1) {
        if (s.find('.', i) != s.npos) {
            tran = int(pow(256, num));
            res += stoi(s.substr(i, s.find('.', i)-i))*tran;
            --num;
            i = s.find('.', i)+1;
        } else {
            tran = int(pow(256, num));
            res += stoi(s.substr(i))*tran;
            break;
        }
    }
    return res;
}

int getLen(const string &s) {
    int num=1, i=0;
    if (s.find('/') != s.npos) {
        return stoi(s.substr(s.find('/')+1));
    } else {
        while(s.find('.', i) != s.npos) {
            ++num;
            i = s.find('.', i) + 1;
        }
        return num*8;
    }
}

bool myCompare(IPB p1, IPB p2) {
    if (p1.ip < p2.ip) {
        return true;
    } else if (p1.ip > p2.ip) {
        return false;
    } else if (p1.len < p2.len) {
        return true;
    } else if (p1.len > p2.len) {
        return false;
    } else{
        return true;
    }
}

string toIP(long long num) {
    string s;
    s += to_string(num/int(pow(256, 3))) + ".";
    num = num%int(pow(256, 3));

    s += to_string(num/int(pow(256, 2))) + ".";
    num = num%int(pow(256, 2));
    s += to_string(num/int(pow(256, 1))) + ".";
    num = num%int(pow(256, 1));
    s += to_string(num);
    return s;
}

bool myRemove(IPB pp) {
    return pp.tip == 0;
}

bool isIncludeB(IPB pp1, IPB pp2) {
    long long num = int(pow(2, 32 - pp1.len)), num1, num2;
    num1 = pp1.ip/num;
    num2 = pp2.ip/num;
    return num1 == num2;
}

void heBin1(list<IPB> &l) {   //從小到大合并
    list<IPB>::iterator it1=l.begin(), it2=++l.begin();
    while(1) {
        while(it2 != l.end() && isIncludeB(*it1, *it2)) {
            it2->tip = 0;  //記錄此字首ip被前一個字首ip的比對集所包含
            ++it2;
        }
        if (it2 == l.end() || it2 == --l.end()) {
            break;
        }
        it1 = it2;
        ++it2;
    }
    l.remove_if(myRemove);   //移除多餘的元素
}

bool heFa(IPB pp) {
    long long num = pow(2, 32-pp.len), num1;
    num1 = (pp.ip/num)*num;
    return pp.ip == num1;
}

bool isHeBin(IPB pp, IPB pp1, IPB pp2) {
    long long num, num1, num2;
    if (pp1.len != pp2.len) {
        return false;
    } else if(!heFa(pp)) {
        return false;
    } else {
        num = pow(2, 32-pp1.len);  
        num1 = pp1.ip/num;
        num2 = pp2.ip/num;
        if (num1 - num2 == 1 || num1 - num2 == -1) {  //ip的前len個位相差1則可以代替
            return true;
        } else {
            return false;
        }
    }
}

void heBin2(list<IPB> &l) {
    list<IPB>::iterator it, it1 = l.begin(), it2 = ++l.begin();
    IPB pp;
    while(1) {
        while(1) {
            pp.ip = it1->ip;
            pp.len = it1->len-1;
            pp.tip = 1;
            if (it2 != l.end() && isHeBin(pp, *it1, *it2)) {
                it = l.erase(it1, ++it2);
                it2 = l.insert(it, pp);
            } else {
                break;
            }
            if (it2 == l.begin()) {
                break;
            }
            it1 = --it2;
        }
        if (it2 == --l.end()) {
            break;
        }
        it1 = it2;
        ++it2;
    }
}

void test() {
    int n;
    IPB pp;
    string s;
    list<IPB> l;
    cin >> n;
    for (int i=0; i<n; ++i) {
        cin >> s;
        pp.ip = getIP(s);
        pp.len = getLen(s);
        pp.tip = 1;
        l.push_back(pp);
    }
    l.sort(myCompare);  //對ip字首集進行排序

    heBin1(l);   //從小到大合并
    heBin2(l);   //同級合并

    for(list<IPB>::iterator it=l.begin(); it!=l.end(); ++it) {
        //cout << it->ip;
        cout << toIP(it->ip) << "/" << it->len << endl;
    }
}

int main() {
	ios::sync_with_stdio(false);
	test();
	return 0;
}

           

如果感覺有幫助，記得點個贊，讓我開心開心，哈哈