CCF CSP认证201812-3 CIDR合并

201812-3 CIDR合并

题目

思路

用long long或者unsigned类型来存储ip地址前缀，再用len表示长度。

结构体

struct cidr{
 	int len;
 	long long ip;//我担心unsigned出错，用的long long
 	bool operator <(const cidr &c) const{//用来排序的比较函数
  		long long a=ip<<(32-len);
  		long long b=c.ip<<(32-c.len);
  		if(a!=b) return a<b;
  		return len<c.len;
 	}
};
           

为了方便合并时候处理，我这里的ip存的只是前缀。

考虑到需要去重和排序，可以用set存储cidr结构体。set迭代器的删除问题可见C++中与迭代器有关的删除操作带来的一些问题。

在ip地址的匹配与合并过程中会用到很多位操作，不过只有"<<“左移与”>>"右移两种。

• 输入ip前缀过程

• ip地址匹配过程

  由于一个ip地址与一个ip前缀匹配的要求是高len（前缀长度）二进制位都相等，而ip前缀的后（32-len）位全为0，

  若一个ip前缀A的匹配集被另一个ip前缀B的匹配集包含，则A的ip值一定小于或等于B的ip值。

long long a=(*it).ip,b=(*it2).ip;
int t=(*it2).len-(*it).len;
if(t<0) break;
b=b>>t;//留下b的*(it).len位，看是否与a相等
if(a==b) pref.erase(it2++);
           

• 同长度的ip前缀合并过程

  只要高len-1二进制位相同，就可以合并

long long a=(*it).ip,b=(*it2).ip;
if((*it).len==(*it2).len&&(a>>1)==(b>>1)){//len相同且高len-1二进制位全部相同
        pref.insert((cidr){(*it).len-1,a>>1});//先插入，否则it会变
        pref.erase(*it2);//先删除后面的，不影响另一个迭代器
        pref.erase(*it);
        it2=it;//删除*it的时候，it后继的迭代器会失效，需要重新赋值
        it2++;
}
           

• 输出也需要进行位操作，八位八位输出，视为256进制。

int k=1<<24;
cout<<a/k;
for(int i=0;i<3;i++){
 	a=a%k;
     	k=k>>8;
      	cout<<"."<<a/k;
}
           

完整代码

#include<iostream>
#include<string>
#include<set>
#include<algorithm>
using namespace std;
struct cidr{
 	int len;
 	long long ip;
 	bool operator <(const cidr &c) const{
  		long long a=ip<<(32-len);
  		long long b=c.ip<<(32-c.len);
  		if(a!=b) return a<b;
  		return len<c.len;
 	}
};
int n;
set<cidr> pref;

int get_num(string str,int s,int t){//取数
 	int x=0;
 	for(int i=s;i<t;i++)
 		 x=x*10+str[i]-'0';
 	return x;
}

void put_in_set(string str){//将各种格式的ip地址转换成统一的结构体
 	int l=0,s=0,t=str.find(".",0);
 	long long temp=0;
 	while(t!=string::npos){
 		temp=(temp<<8)+get_num(str,s,t);//两个'.'之间表示八位二进制
  		l+=8;//每存在一个'.'，len加8
  		s=t+1;
  		t=str.find(".",s);
	 }
 	l+=8;
 	t=str.find("/",s);
 	if(t!=string::npos){
  		temp=(temp<<8)+get_num(str,s,t);
 		temp=temp<<(32-l);//扩展为32位 
  		l=get_num(str,t+1,str.size());
  		temp=temp>>(32-l);//留下前缀 
 	}
 	else 
  		temp=(temp<<8)+get_num(str,s,str.size());
 	pref.insert((cidr){l,temp});
} 

void my_merge(){//删除、合并
 	for(auto it=pref.begin();it!=pref.end();it++){
  		auto it2=it;
  		it2++;
  		while(it2!=pref.end()){//删除多余的ip前缀（被包含）
   			long long a=(*it).ip,b=(*it2).ip;
   			int t=(*it2).len-(*it).len;
   			if(t<0) break;
   			b=b>>t;
   			if(a==b) 
    				pref.erase(it2++);
   			else break;
  		}
 	}
 	for(auto it=pref.rbegin();it!=pref.rend();it++){//合并要逆序进行
  		auto it2=it;
  		it2++;
  		while(it2!=pref.rend()){//合并同长的ip前缀
   			long long a=(*it).ip,b=(*it2).ip;
   			if((*it).len==(*it2).len&&(a>>1)==(b>>1)){
    				pref.insert((cidr){(*it).len-1,a>>1});
    				pref.erase(*it2);
    				pref.erase(*it);
    				it2=it;//删除*it的时候，it后继的迭代器会失效，需要重新赋值
    				it2++;
   			}
   			else break;
  		}
 	}
}

void print(){//输出
 	for(auto it=pref.begin();it!=pref.end();it++){
  		long long a=(*it).ip<<(32-(*it).len);
  		int k=1<<24;
  		cout<<a/k;
  		for(int i=0;i<3;i++){
   			a=a%k;
   			k=k>>8;
   			cout<<"."<<a/k;
  		}
  		cout<<"/"<<(*it).len<<endl;
 	}
}

int main(){
 	cin>>n;
 	string original;
 	for(int i=0;i<n;i++){
  		cin>>original;
  		put_in_set(original);
 	}
 	my_merge();
 	print();
 	return 0;
}