题目描述
同样是一个背景很复杂的题目，但是这个题把处理思路写出来了，根据他的描述写出相应代码即可。这个题我采用了面向对象的思路，在设计对象成员时充分考虑到未来排序、前缀匹配的需求，将ip地址的真值（即ip地址的32位对应真值）和每一位的0或1（用一个vector bool[32]存储）已经前缀长度作为成员，将几种简写形式的输入放在构造函数里，将下面几步合并需要执行的操作作为成员函数。代码有点长，构造函数那里的代码有点冗余，可以缩略一下，整体由于采用了面向对象的思路，所以代码比较好理解。这个代码以后可能用得上，所以发到博客里
#define _CRT_SECURE_NO_WARNINGS //防止sscanf() VS报错
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;
/*test:
6
192.168
192.168.0.1
192.168.0.0
192.168.0
193
192.128/9
*/
typedef unsigned int ipValue;
int myPow(int x, int n) { //快速求幂
if (n == 1) return x;
if (n == -1) return 1 / x;
if (n == 0) return 1;
if (n % 2 == 0) return myPow(x, n / 2) * myPow(x, n / 2);
else {
if (n < 0) return myPow(x, n / 2) * myPow(x, n / 2) * myPow(x, -1);
else return myPow(x, n / 2) * myPow(x, n / 2) * myPow(x, 1);
}
}
class ip {
private:
ipValue value; //ip真值，用于排序比较
int preLength; //前缀长度
vector<bool> bin; //32位二进制形式,用于前缀判定
public:
void setBinValue(vector<int> four) { //由4段数生成bin和value
//生成bin
for (int i = 0; i < 4; i++) {
int real = four[i];
int fv = 128;
for (int j = 0; j < 8; j++) {
if (real / fv == 1) {
real -= fv;
fv /= 2;
bin.push_back(1);
}
else {
fv /= 2;
bin.push_back(0);
}
}
}
//生成value
long long s = 1; //防止int上溢出
for (int i = 31; i >= 0; i--) {
value += s * bin[i];
s *= 2;
}
}
ip(string s) { //通过三种输入格式构造ip
value = 0;
preLength = 0;
int p = 0;
int a = 0; //a表示'/'的个数
int b = 0; //b表示'.'的个数
while (p < s.length()) {
if (s[p] == '/') {
a++;
break;
}
if (s[p] == '.') b++;
p++;
}
if (a == 1 && b == 3) { //标准型
vector<int> f(4, 0);
sscanf(s.c_str(), "%d.%d.%d.%d/%d", &f[0], &f[1], &f[2], &f[3], &preLength);
setBinValue(f);
return;
}
if (a == 1 && b == 0) { //1段型
vector<int> f(4, 0);
sscanf(s.c_str(), "%d/%d", &f[0], &preLength);
setBinValue(f);
return;
}
if (a == 1 && b == 1) { //2段型
vector<int> f(4, 0);
sscanf(s.c_str(), "%d.%d/%d", &f[0], &f[1], &preLength);
setBinValue(f);
return;
}
if (a == 1 && b == 2) { //3段型
vector<int> f(4, 0);
sscanf(s.c_str(), "%d.%d.%d/%d", &f[0], &f[1], &f[2], &preLength);
setBinValue(f);
return;
}
if (a == 0) { //前缀为8的倍数
if (b == 0) {
preLength = 8;
vector<int> f(4, 0);
sscanf(s.c_str(), "%d", &f[0]);
setBinValue(f);
return;
}
if (b == 1) {
preLength = 16;
vector<int> f(4, 0);
sscanf(s.c_str(), "%d.%d", &f[0], &f[1]);
setBinValue(f);
return;
}
if (b == 2) {
preLength = 24;
vector<int> f(4, 0);
sscanf(s.c_str(), "%d.%d.%d", &f[0], &f[1], &f[2]);
setBinValue(f);
return;
}
if (b == 3) {
preLength = 32;
vector<int> f(4, 0);
sscanf(s.c_str(), "%d.%d.%d.%d", &f[0], &f[1], &f[2], &f[3]);
setBinValue(f);
return;
}
}
}
bool operator<(const ip &s) { //用于sort()
if (value == s.value) return preLength < s.preLength;
return value < s.value; //第一关键字
}
bool shadow(ip &b) { //b的匹配集是否是该成员匹配集的子集
//如果b的前缀长度小于该前缀长度，则b一定不是该成员的子集
if (b.preLength < preLength) return false;
for (int i = 0; i < preLength; i++) {
if (bin[i] != b.bin[i]) return false;
}
return true;
}
ip get_A1() { //生成a'
if (preLength == 0) return ip(*this);
ip a(*this);
a.bin[a.preLength - 1] = false;
a.value -= myPow(2, 32 - preLength);
a.preLength--;
/*a.value = 0;
long long s = 1;
for (int i = 31; i >= 0; i--) {
a.value += s * a.bin[i];
s *= 2;
}*/
return a;
}
bool equPreLen(ip& b) {
return preLength == b.preLength;
}
friend bool same(ip& a, ip& b, ip& a1);
void output() {
vector<int> four(4, 0);
for (int i = 0; i < 4; i++) {
int t = 1;
int c = 0;
for (int j = 8 * i + 7; j >= 8 * i; j--) {
c += bin[j] * t;
t *= 2;
}
four[i] = c;
}
cout << four[0] << "." << four[1] << "." << four[2] << "." << four[3] << "/" << preLength << endl;
}
};
bool same(ip& a, ip& b, ip& a1){ //判断a和b的并集是否与a'等价
for (int i = 0; i < a1.preLength; i++) {
if (!(a1.bin[i] == a.bin[i] && a1.bin[i] == b.bin[i])) return false;
}
return true;
}
int main() {
int n;
cin >> n;
cin.ignore();
vector<ip> ipList; //前缀列表
for (int i = 0; i < n; i++) {
string s;
getline(cin, s);
ipList.push_back(ip(s));
}
//step1:排序
sort(ipList.begin(), ipList.end());
//step2:从小到大合并
for (int i = 0; i < ipList.size() - 1; i++) { //使得ipList[i]后面至少有一个元素
if (ipList[i].shadow(ipList[i + 1])) {
ipList.erase(ipList.begin() + i + 1);
i--; //a,b合并了，下面合并a,c
}
}
//step3:同级合并
for (int i = 0; i < ipList.size() - 1; i++) {
if (ipList[i].equPreLen(ipList[i + 1])) { //前缀长度相等
ip a1 = ipList[i].get_A1();
if (same(ipList[i], ipList[i + 1], a1)) {
ipList.erase(ipList.begin() + i + 1); //删除b
ipList.erase(ipList.begin() + i); //删除a
ipList.insert(ipList.begin() + i, a1);
if (i == 0)
i--; //如果a'是第一个元素，则下次a'开始
else
i -= 2; //否则从a'前面一个元素开始
}
}
}
sort(ipList.begin(), ipList.end());
for (int i = 0; i < ipList.size(); i++) {
ipList[i].output();
}
return 0;
}