CIDR去重

// 务必注意分隔符.需要转义
// 一个IP地址正好可以用一个int表示，符号位不重要，只需要无符号右移
import java.io.*;
import java.util.*;
public class Main{
    static class Addr{
        String addrStr;
        int mask;
        int addr;
        public Addr(String addrStr, int mask, int addr){this.addrStr = addrStr; this.mask = mask; this.addr = addr;}
    }
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        LinkedList<Addr> list = new LinkedList<>();
        while(n-->0){
            String addrStr = br.readLine();
            String[] strs = addrStr.split("/");
            int mask = Integer.parseInt(strs[1]);
            strs = strs[0].split("\\.");
            int addr = (Integer.parseInt(strs[0])<<24) | (Integer.parseInt(strs[1])<<16) | (Integer.parseInt(strs[2])<<8) | Integer.parseInt(strs[3]);
            boolean flag = true;
            for(Iterator<Addr> it = list.iterator(); it.hasNext(); ){
                Addr tmp = it.next();
                if(mask < tmp.mask && ( (addr ^ tmp.addr) >>> (32-mask) == 0) ) it.remove();
                if(mask >= tmp.mask && ( (addr ^ tmp.addr) >>> (32-tmp.mask) == 0) ){flag = false; break;}
            }
            if(flag) list.add(new Addr(addrStr,mask,addr));
        }
        System.out.println(list.size());
        for(Iterator<Addr> it = list.iterator(); it.hasNext(); ){
                Addr tmp = it.next();
                System.out.println(tmp.addrStr);
        }
    }
}

# 用python实现了一下，本题不难，就是list判断与替换。
num = int(input())

ip_list = []

out_list=[]

temp2=[]

for i in range(0, num):

    temp = input()

    num1 = temp.split('/')[1]

    num1 = int(num1)

    temp1 = temp.split('/')[0]

    ip = ""

    for j in range(0, 4):

        item = temp1.split('.')[j]

        item1 = int(item)

        item1 = bin(item1)

        item1 = str(item1)

        num2 = 10 - len(item1)

        for k in range(0, num2):

            ip = ip + '0'

        ip = ip + item1[2:]

    ip = ip[0:num1]

    tag = True

    if len(ip_list) == 0:

        ip_list.append(ip)

        out_list.append(temp)

    else:

        temp2=ip_list.copy()

        temp3=out_list.copy()

        for index in temp2:

            if len(ip) >= len(index) and ip[0:len(index)] == index:

                tag = False

                break

            if len(ip) < len(index) and ip == index[0:len(ip)]:

                num3=temp2.index(index)

                ip_list.remove(index)

                index1=temp3[num3]

                out_list.remove(index1)

        if tag:

            ip_list.append(ip)

            out_list.append(temp)

print(len(out_list))

for n in range(0, len(out_list)):

    print(out_list[n])

#include <iostream>
#include <vector>
#include <string>
#include <sstream>
#include <hash_map>
 
using namespace std;
 
struct ip { // 用一各4个int的vector来保存ip
    vector<int> data;
    ip() {
        data = vector<int>(4);
    }
};
 
struct cidr { // 用起始和结束ip来表示cidr
    ip start; // 起始ip地址
    ip end; //   结束ip地址
};

cidr str2cidr(const string & str) { // 将字符串转换成cidr
    int s = 0;
    int e = str.find('.', s);
    cidr res;
    int i = 0;
    while (e != string::npos) {
        res.start.data[i++] = stoi(str.substr(s, e - s));
        s = e + 1;
        e = str.find('.', s);
    }
    e = str.find('/');
    res.start.data.back() = stoi(str.substr(s, e - s));
    int len = stoi(str.substr(e + 1, str.size() - e));
 
    res.end = res.start;
    int p1 = len / 8;
    int rest = len % 8; // 还有几位相同
    for (int i = p1; i < 4; ++i) {
        res.start.data[i] &= (255 << (8 - rest));
        res.end.data[i] |= ~(-1 << (8 - rest));
        rest = 0;
    }
    return res;
}
 
bool LT(ip a, ip b) { // 判断ip的大小
    for (int i = 0; i < 4; ++i) {
        if (a.data[i] <= b.data[i]) {
            continue;
        } else {
            return false;
        }
    }
    return true;
}
 
bool GT(ip a, ip b) {
    for (int i = 0; i < 4; ++i) {
        if (a.data[i] >= b.data[i]) {
            continue;
        } else {
            return false;
        }
    }
    return true;
}
 
bool cidr_contain(cidr a, cidr b) { // 判断cidr a 是否包含 cidr b
    return a.start.data[0] == b.start.data[0] & LT(a.start, b.start) && GT(a.end, b.end);
}
 
void process(const string & str, vector<string> & cidrs_str, vector<cidr> & cidrs, int & erased) {
    cidr t = str2cidr(str);
    for (int i = 0; i < cidrs.size(); ++i) {
        if (cidrs_str[i].size() > 0) {
            if (cidr_contain(cidrs[i], t)) {
                return;
            }
            if (cidr_contain(t, cidrs[i])) {
                cidrs_str[i] = "";
                erased++;
            }
        }
         
    }
    cidrs_str.emplace_back(str);
    cidrs.emplace_back(t);
}
 
int main() {
    string str = "172.24.68.0/24";
    int n = 0;
    while (cin >> n) {
        vector<string> cidrs_str; // 为空则无效
        vector<cidr> cidrs;
        int erased = 0;
        while (n--) {
            cin >> str;
            process(str, cidrs_str, cidrs, erased);
        }
        cout << cidrs.size() - erased << endl;
        for (auto item : cidrs_str) {
            if (item.size() > 0) {
                cout << item << endl;
            }
        }
    }
}

    #include
    using namespace std;
    pair transInt(string str) {
        int t = 0;
        unsigned int t2 = 0;
        int i = 0;
            for (; i < str.size(); i++) {
                if (str[i] != '.'&&str[i] != '/') {
                    t2 = t2 * 10 + str[i] - '0';
                }
                else {
                    t=t*256+t2;
                    t2 = 0;
                }
                if (str[i] == '/')
                break;
            }
        int mask = 0;
        i++;
        for (; i<str.size(); i++) {
            mask = mask * 10 + str[i] - '0';
        }
        pair p(t, mask);
        return p;
    }
    int judge(pair p1, pair p2) {
        if (p1.second == p2.second) return 0;
        int n = p1.second<p2.second ? p1.second : p2.second;
        n = 32 - n;
        p1.first=p1.first >> n;
        p2.first=p2.first >> n;
        if (p1.first == p2.first) {
            if (p1.second>p2.second)
                return -1;    //-1表示p1应删除
            else
                return 1;
        }
        return 0;
    }
    int main() {
        int k;
        cin >> k;
        vector dOrNot(k, 0);
        vector>> v(k, pair>());
        for (int i = 0; i<k; i++)
        {
            cin >> v[i].first;
            v[i].second = transInt(v[i].first);
        }
        for (int i = 0; i<k; i++) {
            for (int j = i+1; j<k; j++) {
                int flag = judge(v[i].second, v[j].second);
                if (flag == 0)
                    continue;
                if (flag == -1)
                    dOrNot[i] = -1;
                if (flag == 1)
                    dOrNot[j] = -1;
            }
        }
        int num = 0;//剩余个数
        for (auto i : dOrNot) {
            if (i == 0)
                num++;
        }
        cout << num << endl;
        for (int i = 0; i<k; i++) {
            if (dOrNot[i] == 0)
                cout << v[i].first << endl;
        }
        return 0;
    }

    }