【CCF 201812-3】CIDR合并（連結清單，位運算）

寫在前面

本題考查的是對

STL::list

的熟練運用，以及對位運算的思考；思路在題目中給出的提示當中已經非常清晰。

解題思路

• 将輸入轉化為

  list<字首IP>

  struct Prefix
  {
    vector<unsigned> ip;
    int len;
  }
             

  這裡要分兩種特殊情況：省略字尾型和省略長度型；

  我們使用的技術包括：字元串流stringstream、子串函數string::substr()、string轉int函數stoi()；

• 對連結清單進行排序

  由于List的疊代器并不是随機通路疊代器，是以我們在這裡不能夠使用STL::sort()，而隻能使用list::sort()；

• 從小到大合并

  考察了對連結清單的周遊操作，更重要的是判斷b是否為a的子集。下面是思路：

  • 将a和b的IP位址計算出來，它們分别是32位的比特。
  • 如果

    b.len > a.len

    ，那麼b必不可能是a的子集。
  • 分别取a和b比特流的前

    a.len

    位，若它們相等則b是a的子集

    具體的方法是計算一個掩碼mask = 111111…00000，前面有a.len個1，後面有(32 - a.len)個0。

    unsigned mask = (a.len == 0) ? 0 : ~((1 << (32 - a.len)) - 1);

• 同級合并

  考察了對連結清單的周遊操作，更重要的是判斷a’是否與a∪b相等。下面是思路：

  • 進行合并的要求為

    a.len == b.len

    ，我們假設a的IP位址的字首是

    0010111

    ，即

    a.len == 7

    。

    按照題目的方法，a_new.len == 6，a_new的字首是

    001011

    。

    那麼b要是多少才有可能讓

    a_new == a∪b

    呢？很顯然了，答案是

    0010110

    。即a和b的字首僅有最後一位是相反的。
  • 用位運算表示為：

    unsigned mask = 1 << (32 - a.len);

    return (ip_b ^ mask) == ip_a;

滿分代碼（C++11，250ms）

// 開啟O3優化
#pragma GCC optimize(3, "Ofast", "inline")

#include <cstring>
#include <iostream>
#include <list>
#include <sstream>
#include <vector>
using namespace std;

struct Prefix
{
    vector<unsigned> ip;
    int len;

    // 構造函數：根據ip字元串解析ip字首
    Prefix(const string &str)
    {
        size_t pos = str.find('/');
        if (pos != string::npos)
        {
            len = stoi(str.substr(pos + 1));    // len

            string ip_str = str.substr(0, pos);
            stringstream ss(ip_str);
            unsigned num;
            while (ss >> num)       // 輸入數字
            {
                ip.push_back(num);
                ss.get();           // 輸入數字後面的"."
            }
        }
        else    // 省略長度型
        {
            stringstream ss(str);
            unsigned num;
            while (ss >> num)
            {
                ip.push_back(num);
                ss.get();
            }
            len = ip.size() * 8;    // 計算len
        }

        // ip位址有4個數字，不足4個在後面補0
        size_t left = 4 - ip.size();
        for (size_t i = 0; i < left; ++i)
            ip.push_back(0);
    }

    // 定義偏序，便于調用sort
    friend bool operator<(const Prefix &a, const Prefix &b)
    {
        if (a.ip != b.ip)
            return a.ip < b.ip;
        return a.len < b.len;
    }

    // 根據vector<unsigned> ip 計算 ip位址
    unsigned get_ip()
    {
        unsigned ip_num = 0, mul = 1;
        for (int i = 3; i >= 0; --i)
        {
            ip_num += mul * ip[i];
            mul *= 256;
        }
        return ip_num;
    }

    // b是否為a的子集
    bool is_subset_of(Prefix &a)
    {
        if (len < a.len)
            return false;

        unsigned ip_a = a.get_ip();
        unsigned ip_b = get_ip();

        unsigned mask = (a.len == 0) ? 0 : ~((1 << (32 - a.len)) - 1);

        return (mask & ip_a) == (mask & ip_b);
    }

    // 輸出ip位址
    void print()
    {
        cout << ip[0] << '.' << ip[1] << '.' << ip[2] << '.' << ip[3] << '/' << len << '\n';
    }
};

// ip字首清單
list<Prefix> pre_list;

// 第二步：按大小合并
void merge_by_size()
{
    for (auto a = pre_list.begin(); a != pre_list.end();)
    {
        auto b = next(a);
        if (b == pre_list.end())    // 如果a後面沒有元素了，則可以退出
            return;
        if (b->is_subset_of(*a))    // 如果b是a的子集，則删除b（注意此時疊代器a不動）
            pre_list.erase(b);
        else
            ++a;
    }
}

// 第三步核心問題：判斷a_new是否可以代替a∪b
bool isMergable(Prefix &a, Prefix &b, Prefix &a_new)
{
    unsigned ip_a = a.get_ip();
    unsigned ip_b = b.get_ip();

    unsigned mask = 1 << (32 - a.len);
    
    return (ip_b ^ mask) == ip_a;
}

// 第三步：同級合并
void merge_with_same_rank()
{
    for (auto a = pre_list.begin(); a != pre_list.end();)
    {
        auto b = next(a);
        if (b == pre_list.end())
            return;

        Prefix a_new(*a);
        if (--a_new.len < 0)    // 如果a'的ip位址不合法，則移動至下一個元素
        {
            ++a;
            continue;
        }

        // 如果a.len == b.len：且可以合并
        if (a->len == b->len && isMergable(*a, *b, a_new))
        {
            *a = a_new;         // 将a替換為a'
            pre_list.erase(b);  // 删除b
            if (a != pre_list.begin())      // 後退一位繼續操作
                --a;
        }
        else
            ++a;
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n;
    cin >> n;
    cin.get();

    // 處理輸入的ip字元串
    string line;
    while (n--)
    {
        getline(cin, line);
        pre_list.push_back(Prefix(line));
    }

    // 三步處理
    pre_list.sort();
    merge_by_size();
    merge_with_same_rank();

    // 列印輸出
    for (Prefix &p : pre_list)
        p.print();

    return 0;
}
           

如果對您有幫助，記得點個贊喲 (＾Ｕ＾)ノ