CCF CSP 201812-3.CIDR合并

样例输入

2
1
2

样例输出

1.0.0.0/8
2.0.0.0/8

样例输入

2
10/9
10.128/9

样例输出

10.0.0.0/8

样例输入

2
0/1
128/1

样例输出

0.0.0.0/0

---

分析：

按照题目给定的算法求解即可。

1.定义一个类型表示IP前缀：

typedef struct Node {
	// 表示ip地址的32位无符号整数
	string ip;
	// ip地址的点分十进制表示
	int data[4];
	// 前缀长度
	int len;
	Node() {
		this->ip = "";
		this->len = 0;
	}
} IP;

2.在第二步：从小到大合并中，如何判断b的匹配集是否为a的匹配集的子集？

根据匹配的定义可知，前缀长度越大，该IP前缀匹配的IP地址越少。

因此，若a的前缀长度大于b的前缀长度，则b的匹配集不可能是a的匹配集的子集。

如果a.len <= b.len，则判断它们IP地址的前a.len位是否相同。若有一位不同，则b的匹配集不是a的匹配集的子集。

// 判断b是否为a的子集
bool isSubset(IP a, IP b) {
	if (a.len > b.len) {
		return false;
	}
	for (int i = 0; i < a.len; i++) {
		if (b.ip[i] != a.ip[i]) {
			return false;
		}
	}
	return true;
}

3.在第三步：同级合并中，如何判断$a^{’}​$是否合法，以及a的匹配集与b的匹配集的并集是否等于$a^{’}​$的匹配集？

（1）判断$a^{’}$是否合法：根据IP前缀的定义，前缀长度 $len \in [0,32]$，且ip的低(32-len)二进制位为0。

（2）判断a的匹配集与b的匹配集的并集是否等于$a^{’}​$的匹配集：

若a和b的ip地址前a.len-1位均相同，且a.len位不相同，则a的匹配集与b的匹配集的并集等于$a^{’}$的匹配集。

// 判断是否能进行同级合并
bool canMerge(IP a, IP b) {
	if (a.len != b.len) {
		return false;
	}
	a.len -= 1;
	// 若不合法
	if (a.len < 0 || a.ip[a.len] != '0') {
		return false;
	}
	for (int i = 0; i < a.len; i++) {
		if (a.ip[i] != b.ip[i]) {
			return false;
		}
	}
	return a.ip[a.len] != b.ip[a.len];
}

• C++版

#include <iostream>
#include <list>
#include <string>
using namespace std;

typedef struct Node {
	// 表示ip地址的32位无符号整数
	string ip;
	// ip地址的点分十进制表示
	int data[4];
	// 前缀长度
	int len;
	Node() {
		this->ip = "";
		this->len = 0;
	}
} IP;

// 升序排序
bool cmp(IP a, IP b) {
	if (a.ip != b.ip) {
		return a.ip < b.ip;
	}
	return a.len < b.len;
}

// 判断b是否为a的子集
bool isSubset(IP a, IP b) {
	if (a.len > b.len) {
		return false;
	}
	for (int i = 0; i < a.len; i++) {
		if (b.ip[i] != a.ip[i]) {
			return false;
		}
	}
	return true;
}

// 从小到大合并
void merge1(list<IP> &ls) {
	list<IP>::iterator i = ls.begin(), j = ls.begin();
	j++;
	while (j != ls.end()) {
		if (isSubset(*i, *j)) {
			j = ls.erase(j);
		} else {
			i++;
			j++;
		}
	}
}

// 判断是否能进行同级合并
bool canMerge(IP a, IP b) {
	if (a.len != b.len) {
		return false;
	}
	a.len -= 1;
	// 若不合法
	if (a.len < 0 || a.ip[a.len] != '0') {
		return false;
	}
	for (int i = 0; i < a.len; i++) {
		if (a.ip[i] != b.ip[i]) {
			return false;
		}
	}
	return a.ip[a.len] != b.ip[a.len];
}

// 同级合并
void merge2(list<IP> &ls) {
	list<IP>::iterator i = ls.begin(), j = ls.begin();
	j++;
	while (j != ls.end()) {
		if (canMerge(*i, *j)) {
			i->len -= 1;
			j = ls.erase(j);
			if (i != ls.begin()) {
				i--;
				j--;
			}
		} else {
			i++;
			j++;
		}
	}
}

// 转换为8位二进制数
string toBinaryString(int data) {
	string result = "";
	int arr[8] = { 1, 2, 4, 8, 16, 32, 64, 128 };
	for (int i = 7; i >= 0; i--) {
		if (data >= arr[i]) {
			result += '1';
			data -= arr[i];
		} else {
			result += '0';
		}
	}
	return result;
}

int main() {

	int n;
	cin >> n;

	list<IP> ls;
	string line;
	while (n--) {
		IP ip;
		cin >> line;

		// 统计.的个数
		int count = 0;
		int start = 0, end = 0;
		// 是否包含/
		bool hasSeparator = false;
		for (int i = 0; i < line.size(); i++) {
			if (line[i] == '.') {
				end = i;
				ip.data[count] = stoi(line.substr(start, end - start));
				ip.ip += toBinaryString(ip.data[count]);
				count++;
				start = i + 1;
			} else if (line[i] == '/') {
				hasSeparator = true;
				ip.len = stoi(line.substr(i + 1));
				ip.data[count] = stoi(line.substr(start, i - start));
				ip.ip += toBinaryString(ip.data[count]);
			}
		}
		// 若为省略长度型
		if (!hasSeparator) {
			ip.len = 8 * (count + 1);
			ip.data[count] = stoi(line.substr(start));
			ip.ip += toBinaryString(ip.data[count]);
		}
		// 补全省略的后缀
		for (int i = 0; i < 3 - count; i++) {
			ip.data[count + 1 + i] = 0;
			ip.ip += "00000000";
		}

		ls.push_back(ip);
	}

	// 1.排序
	ls.sort(cmp);
	// 2.从小到大合并
	merge1(ls);
	// 3.同级合并
	merge2(ls);

	for (list<IP>::iterator iter = ls.begin(); iter != ls.end(); iter++) {
		for (int i = 0; i < 4; i++) {
			if (i > 0) {
				cout << '.';
			}
			cout << iter->data[i];
		}
		cout << '/' << iter->len << endl;
	}

	return 0;
}