ccf 2018-12-3 CIDR合并_ghost889的博客-程序员宅基地

这是第一次参加ccf考试,当时考场上只得了50分,思路有点不清晰,回来整理了一下思路

其实考试题目都给了思路了

我的思路就是一个结构体,记录IP地址四段中的每一段的大小,还有一个len记录IP地址的长度

排序操作使用sort函数自动

从小到大合并使用另一个list来存储

统计合并就像进栈出栈一样

其实这两个我都想用list直接删除的好,但并不会这种操作

下面是满分代码,附带了两个自己的测试用例

#include<iostream>
#include<string>
#include<list>
#include<vector>
#include<stack>
#include<algorithm>
using namespace std;
struct IP{
	string ip;
	int a[4]={0,0,0,0};
	int len;
	friend bool operator <(const IP &ip1,const IP &ip2){//用于排序,以IP值为第一关键字,长度为第二关键字 
		if(ip1.a[0]<ip2.a[0])
			return true;
		else if(ip1.a[0]==ip2.a[0]){
			if(ip1.a[1]<ip2.a[1])
				return true;
			else if(ip1.a[1]==ip2.a[1]){
				if(ip1.a[2]<ip2.a[2])
					return true;
				else if(ip1.a[2]==ip2.a[2]){
					if(ip1.a[3]<ip2.a[3])
					    return true;
					else if(ip1.a[3]==ip2.a[3]){
						if(ip1.len<ip2.len)
							return true;
					}
				}
			}
		}
		return false;
	}
};
int sti(string s){//字符串转数字 
	int a;
	char b[20];
	for(int i=0;i<s.length();i++)
		b[i]=s[i];
	sscanf(b,"%d",&a);
	return a;
}
IP toStandard(string str){//标准化 
	int len=0,l1=0,ui=0;
	IP iip;
	int f=str.find('/');
	string su=str;
	if(f!=string::npos){
		string h=str.substr(f+1,str.length()-f-1);
		len=sti(h);
		su=str.substr(0,f);
	} 
	su+=".";
	f=su.find('.');
	while(f!=string::npos){
		iip.a[ui]=sti(su.substr(0,f));
		su=su.substr(f+1,su.length()-f-1);
		ui+=1;
		l1+=8;
		f=su.find('.');
	}
	if(!len) iip.len=l1;
	else iip.len=len;
	return iip;
}
int pow_2(int i){//2的i次方 
	int s=1;
	while(i--){
		s*=2;
	}
	return s;
}
int contain(int &x,int y){
//二进制中是否包含某一位,比如255包含128,即11111111,那么x=255,y=128,就是最高位为1,如果包含,就减去128 
	if(x-y>=0){
		x-=y;
		return 1;
	}
	return -1;
}
bool subset(const IP x,const IP y){//x是否包含y 
	if(x.len>y.len) return false;
	else{
		int x1=x.len,y1=y.len,s=0;
		while(x1>=8){
			if(x.a[s]!=y.a[s])
				return false;
			x1-=8;
			s+=1;
		}
		int xx=x.a[s],yy=y.a[s];
		for(int i=0;i<x1;i++){
			if((contain(xx,pow_2(7-i))*contain(yy,pow_2(7-i)))==1)
				continue;
			else return false;
		}
		return true;	
	}
}
bool sum(const IP x,const IP y){//x,y是否互补 
	if(x.len!=y.len) return false;
	else{
		int x1=x.len,s=0;
		while(x1>8){
			if(x.a[s]!=y.a[s])
				return false;
			x1-=8;
			s+=1;
		}
		int xx=x.a[s],yy=y.a[s];
		for(int i=0;i<x1-1;i++){
			if((contain(xx,pow_2(7-i))*contain(yy,pow_2(7-i)))==1)
				continue;
			else return false;
		}
		if((contain(xx,pow_2(8-x1))==-1&&contain(yy,pow_2(8-x1)))==1)
			return true;
		else return false;	
	}
}
int main(){
	int n;
	list<IP> lis,vec;
	cin>>n;
	getchar();
	while(n--){
		string line;
		getline(cin,line);
		IP ipp=toStandard(line);
		lis.push_back(ipp);
	}//输入并且标准化 
	lis.sort();
	vector<IP> vect;
	vec.push_back(lis.front());
	lis.pop_front();
	for(list<IP>::iterator it=lis.begin();it!=lis.end();it++){
		if(!subset(vec.back(),*it)) vec.push_back(*it);
		else continue;
	}//从小到大合并 
	vect.push_back(vec.front());
	vec.pop_front();
 	while(!vec.empty()){
 		if(sum(vect.back(),vec.front())){
 			vec.pop_front();
 			if(vect.size()==1){
 				vect.back().len-=1;
			 }
			else{
				vec.push_front(vect.back());
 				vec.front().len-=1;
 				vect.pop_back();	
			}
		 }
		else{
			vect.push_back(vec.front());
			vec.pop_front();
		}	
	}//同级合并 
	for(vector<IP>::iterator iter=vect.begin();iter!=vect.end();iter++){
		cout<<iter->a[0]<<"."<<iter->a[1]<<"."<<iter->a[2]<<"."<<iter->a[3]<<"/"<<iter->len<<endl;
	}
} 
/*
5
10.12.16/24
10.12.16.128/25
10.12.16.0/25
10.23.28.224/27
10.23.28.192/27

5
10.12.16.128/25
10.12.16.128/25
10.12.16.0/25
10.23.28.224/27
10.23.28.192/27
*/

 

 

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/qq_41914302/article/details/86538772

智能推荐

【转】C常用字符转换函数_weixin_33705053的博客-程序员宅基地

1 atof(将字符串转换成浮点型数) 2 相关函数 3 atoi,atol,strtod,strtol,strtoul 4 表头文件 5 #include &lt;stdlib.h&gt; 6 定义函数 7 double atof(const char *nptr); 8 函数说明 9 atof()...

Linux学习之---vi和vim_叶清藤的博客-程序员宅基地

Linux学习之-------vi和vimvi和vimvi和vim常用快捷键vi和vim是Linux中的文本编辑器,是用来在Linux中查看或者编辑文本文件,作用和Windows中的记事本类似,vim是vi的增强版本。使用方法:一般模式:用vi或者vim打开文件,进入一般模式,可以查看文件的内容,并且可以通过上下左右移动光标,查看文件某一部分,但不能编辑文件内容。编辑模式:在一般模式下按i键或者a键,进入编辑模式编辑文件,但不能保存,按esc键退出回到一般模式。命令行模式:在一般模式下,按sh

学术英语期末考试_Touale的博客-程序员宅基地

学术英语期末考试——30道选择题考试题型:1 )听力理解(20%) 课外题材2篇,每篇5道选择题,每题2分;2)阅读理解 (40%) 共4篇短文,每篇5道选择题,每题2分。均从课外出题。3)词汇与结构(20%) 共20道选择题,每题1分,均出自教材前六个单元reading1 后面的词汇结构练习题。4)作文(20%) 议论文一篇,字数150-180,考查学生关于comparison-contrast写作技能的掌握。...

ICML2020 文章目录及下载链接_颹蕭蕭的博客-程序员宅基地

2020 年会议线上召开,会议网站也和以往大不相同官网本身就提供了文章的主题分类检索与下载尽管如此,还是希望能够制作一份方便本地查找的目录,毕竟访问外网有点卡下载 json 文件通过网站页面源码分析,发现所有数据都在这份 icml_paper.json 文件中,把它下载下来:https://icml.cc/static/virtual/data/icml_papers.json你要是直接打开的话,就是这个样子,当然我们接下来就用 python 的 json 包来解析它!解析 json 文

linux学习42-HTTP服务和APACHE_你的微笑像茉莉的博客-程序员宅基地

HTTP服务和APACHE1. 跨Internet的主机间通讯要通过Internet进行通信,至少需要一对套接字,其中一个运行在客户端,定义了一个唯一的客户进程,称之为ClientSocket,另一个运行于服务器端面,定义了一个唯一的服务器进程,称为ServerSocket。根据连接启动的方式以及本地要连接的目标,套接字之间的连接过程可以分为三个步骤:服务器监听、客户端请求、连接确认So...

怎么转载别人的博客_PoisonerAj的博客-程序员宅基地

前言  对于喜欢逛CSDN的人来说,看别人的博客确实能够对自己有不小的提高,有时候看到特别好的博客想转载下载,但是不能一个字一个字的敲了,这时候我们就想快速转载别人的博客,把别人的博客移到自己的空间里面,当然有人会说我们可以收藏博客啊,就不需要转载,(⊙o⊙)… 也对。。实现  因为我自己当初想转载的时候却不知道该怎么转载,所以学会了之后就把方法写出来,帮助那些想转载却不知道该怎么转载的人(大神勿笑)。   我们首先打开要转载的博客,然后鼠标右键就会出现下面的菜单:   我们...

随便推点

C标准时间与时间戳的相互转换_一只青木呀的博客-程序员宅基地

话不多说,直接上代码;#include &lt;stdio.h&gt;#include &lt;string.h&gt;#include &lt;time.h&gt;#include &lt;stdlib.h&gt;/*标准时间转换为时间戳*/int standard_to_stamp(char *str_time){ struct tm stm; int iY,iM,iD,iH,iMin,iS; memset(&amp;stm,0,sizeof(stm)); iY = atoi(s

TensorFlowLite GPU加速_最爱吹吹风的博客-程序员宅基地

TF LITE支持移动端GPU加速,特别对android端的支持比较丰富。相对android来说,对IOS的支持就有点差了。从给出的文档也能看出,android的文档也比IOS的丰富。TF LITE明确只支持android和ios端,而且在不同的系统上会有不同表现。即便是可以用GPU,也有可能是部分操作可以应用GPU加速,部分依旧在CPU上,这要看具体系统对GPU操作的支持。TF LITE在运行时会给出log引用官方的解释:不支持的模型和 ops如果一些 ops 并不支持 GPU 代理

网页常见错误~比较简单_丑八怪~的博客-程序员宅基地

每次出现错误很烦,简单整理一下,详细具体大家可以搜索查看400:客户端发送请求服务端接受不了401:未授权403:注解方法调不通,比如跨域,访问被拒绝405:请求方式406:客户端浏览器不接受所请求的页面500:代码写错了200:代码成功...

KITTI数据集学习笔记_IT小白自习室的博客-程序员宅基地

Kitti数据集本文为笔者自我学习的笔记,本人刚入门3D视觉,若有错误的地方恳请各位指正。另外参考了一篇热门博客:https://blog.csdn.net/Solomon1558/article/details/70173223。并使用了其中的一幅图像,侵删。1. 简单介绍​ Kitti数据集致力于提供一个更贴合户外驾驶场景的计算机视觉数据集。Kitti提供了一些自动驾驶场景下具有挑战性的测试基准:立体场景(stereo)、光学流动(optical flow)、视觉测距(visual odomet

python批量提取word指定内容_python批量提取word内信息_weixin_39876145的博客-程序员宅基地

单位收集了很多word格式的调查表,领导需要收集表单里的信息,我就把所有调查表放一个文件里,写了个python小程序把所需的信息打印出来#coding:utf-8import osimport win32comfrom win32com.client import Dispatch, constantsfrom docx import Documentdef parse_doc(f):"""读取d...

使用Android Studio管理项目_netfreeperson的博客-程序员宅基地

使用Android Studio管理项目Android Studio为创建和管理Android项目提供了一个图形化的工具,它包含了定义你的Android应用的每一样东西,从app的源码到构建配置和测试代码。每个项目包含一个或多个不同类型的modules,比如应用模块,库模块和测试模块。 这里指导你如何使用android Studio来创建Android 项目和不同的模块。关于更多的A...