k+1行, k表示输入的CIDR路由个数
第1行:表示路由个数k
第2~k+1行: 表示一个CIDR路由, 形如 x.x.x.x/x
n+1行, n表示去重后剩下的CIDR路由个数
第1行:n
第2~n+1行: 表示一个去重后的CIDR路由, 输出按照输入顺序
13 192.168.0.0/16 172.24.96.17/32 172.50.137.225/32 202.139.219.192/32 172.24.68.0/24 192.183.125.71/32 201.45.111.138/32 192.168.59.211/32 192.168.26.13/32 172.24.0.0/17 172.24.5.1/32 172.24.68.37/32 172.24.168.32/32
7 192.168.0.0/16 172.50.137.225/32 202.139.219.192/32 192.183.125.71/32 201.45.111.138/32 172.24.0.0/17 172.24.168.32/32
// 务必注意分隔符.需要转义 // 一个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; } } } }
import java.util.Arrays; import java.util.HashSet; import java.util.LinkedList; import java.util.List; import java.util.Scanner; public class Main { private static class IpNode implements Comparable<IpNode> { String ip; String mask; @Override public int compareTo(IpNode o) { return ip.compareTo(o.ip); } } public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int n = scanner.nextInt(); String[] cidrs = new String[n]; for (int i = 0; i < n; i++) { cidrs[i] = scanner.next(); } List<String> list = solve(cidrs); System.out.println(list.size()); for (String string : list) { System.out.println(string); } } private static List<String> solve(String[] cidrs) { HashSet<String> hashSet = new HashSet<>(cidrs.length); IpNode[] ipNodes = new IpNode[cidrs.length]; for (int i = 0; i < cidrs.length; i++) { String[] tmps = cidrs[i].split("/"); String[] ips = tmps[0].split("\\."); int ip = 0; for (int j = 0; j < ips.length; j++) { ip <<= 8; ip ^= Integer.valueOf(ips[j]); } ipNodes[i] = new IpNode(); ipNodes[i].ip = Integer.toBinaryString(ip).substring(0, Integer.valueOf(tmps[1])); ipNodes[i].mask = cidrs[i]; } Arrays.sort(ipNodes); for (int i = 0; i < ipNodes.length; i++) { hashSet.add(ipNodes[i].mask); for (int j = i + 1, index = i; j < ipNodes.length; j++) { if (ipNodes[j].ip.startsWith(ipNodes[index].ip)) { i++; } else { break; } } } List<String> list = new LinkedList<>(); for (int i = 0; i < cidrs.length; i++) { if (hashSet.contains(cidrs[i])) { list.add(cidrs[i]); } } return list; } }
#include <cstdlib> #include <string> #include <iostream> #include <fstream> #include <vector> #include <sstream> #include <unordered_map> #include <unordered_set> #include <map> #include <set> #include <stdio.h> #include <numeric> #include <algorithm> #include <functional> #include <stack> #include <queue> #include <cmath> #include <assert.h> #include <vector> #include <memory> #include <memory.h> using namespace std; typedef long long ll; const int MOD = 1e9 + 7; typedef unsigned char uchar; //#define G_DEBUG uchar reverseBits(uchar n) { n = ((n & 0xAAAAAAAA) >> 1) | ((n & 0x55555555) << 1); n = ((n & 0xCCCCCCCC) >> 2) | ((n & 0x33333333) << 2); n = ((n & 0xF0F0F0F0) >> 4) | ((n & 0x0F0F0F0F) << 4); return n; } int main() { #ifdef G_DEBUG // 调试使用 int N = 0; ifstream file("data.txt"); string s; getline( file, s ); N = atoi( s.c_str() ); vector<string> strs(N); int i = 0; while( getline( file, s )) strs[i++] = s; #else int N = 0; cin >> N; vector<string> strs(N); for (int i = 0; i < N; i++) cin >> strs[i]; #endif vector<int> bit_nums(N, 0); vector<ll> val_nums(N, 0); int idx = 0; int curr_bit = 0; ll curr_val = 0; ll tmp = 0; ll tmp_val = 0; uchar c; for (int i = 0; i < N; i++) { idx = strs[i].find_first_of('/'); bit_nums[i] = atoll(strs[i].substr(idx + 1).c_str()); idx = strs[i].find_first_of('.'); c = atoi(strs[i].substr(0, idx).c_str()); curr_val = (ll)reverseBits(c); tmp = idx; idx = strs[i].find_first_of('.', idx + 1); c = atoi(strs[i].substr(tmp + 1, idx - tmp).c_str()); curr_val = ((ll)reverseBits(c) << 8) | curr_val; tmp = idx; idx = strs[i].find_first_of('.', idx + 1); c = atoi(strs[i].substr(tmp + 1, idx - tmp).c_str()); curr_val = ((ll)reverseBits(c) << 16) | curr_val; tmp = idx; idx = strs[i].find_first_of('.', idx + 1); c = atoi(strs[i].substr(tmp + 1, idx - tmp).c_str()); curr_val = ((ll)reverseBits(c) << 24) | curr_val; curr_val = (((ll)1 << bit_nums[i]) - 1) & curr_val; val_nums[i] = curr_val; } vector<int> removed_idxs; for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { if (i == j) continue; if ((bit_nums[i] >= bit_nums[j] ) && (val_nums[j] == (val_nums[i] & (((ll)1 << bit_nums[j]) - 1))) ) { removed_idxs.push_back( i ); break; } } } int re_idx = 0; cout << (N - removed_idxs.size()) << endl; for (int i = 0; i < N; i++) { if (removed_idxs.size() > re_idx && i == removed_idxs[re_idx]) { re_idx++; continue; } cout << strs[i] << endl; } system("pause"); return 0; }
#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;
}
}