[WUST2017]算法竞赛入门经典第四章 K - IP Networks (与二进制的操作有关)

news/2024/2/29 4:15:34

题目:K - IP Networks
Alex is administrator of IP networks. His clients have a bunch of individual IP addresses and he decided to group all those IP addresses into the smallest possible IP network. Each IP address is a 4-byte number that is written byte-by-byte in a decimal dot-separated notation “byte0.byte1.byte2.byte3” (quotes are added for clarity). Each byte is written as a decimal number from 0 to 255 (inclusive) without extra leading zeroes. IP network is described by two 4-byte numbers — network address and network mask. Both network address and network mask are written in the same notation as IP addresses. In order to understand the meaning of network address and network mask you have to consider their binary representation. Binary representation of IP address, network address, and network mask consists of 32 bits: 8 bits for byte0 (most significant to least significant), followed by 8 bits for byte1, followed by 8 bits for byte2, and followed by 8 bits for byte3. IP network contains a range of 2n IP addresses where 0 ≤ n ≤ 32. Network mask always has32 −n first bits set to one, and n last bits set to zero in its binary representation. Network address has arbitrary 32−n first bits, and n last bits set to zero in its binary representation. IP network contains all IP addresses whose 32−n first bits are equal to 32−n first bits of network address with arbitrary n last bits. We say that one IP network is smaller than the other IP network if it contains fewer IP addresses. For example, IP network with network address 194.85.160.176 and network mask 255.255.255.248 contains 8 IP addresses from 194.85.160.176 to 194.85.160.183 (inclusive).
Input
The input file will contain several test cases, each of them as described below. The first line of the input file contains a single integer number m (1 ≤ m ≤ 1000). The following m lines contain IP addresses, one address on a line. Each IP address may appear more than once in the input file.
Output
For each test case, write to the output file two lines that describe the smallest possible IP network that contains all IP addresses from the input file. Write network address on the first line and network mask on the second line.

Sample Input
3 194.85.160.177 194.85.160.183 194.85.160.178
Sample Output
194.85.160.176 255.255.255.248

题意:先输入一个m表示IP地址的个数,之后再输入m个IP地址,然后根据IP地址的那些性质(这个只能看题翻译一下);输出网络地址和子网掩码;

思路:两种:
第一种:用一个二维数组,用一列4个来一个IP地址的四个数,然后再找到最小的和最大的,然后比较最大和最小对应部分是否相等,不相等的那一行就跳出,将其最大和最小的这两个不相等的数转化成二进制的字符串,然后反向比较,找到有多少位是相等,然后不相等的就变成0,在将其转化成10进制,然后就可以得到网络地址和子网掩码了;(用的是二进制字符串
第二种:前面存的方法和第一种一样,但是不用排序,只需要找第一个,然后将第一个依次与后面对应的比,有不相同的就从这个数开始,然后依次进行位运算右移1位,知道相同,然后讲移动的位数记下来,然后再移回来之后就是相同的了,然后就依次得到网络地址和子网掩码。(用的是位运算将多余不相同的给溢出去,然后再移回来的方法);

教训:一开始一直用的是第二种方法,然后就一直WA,然后就改用了第一种方法,不过后来同学帮忙测数据之后才发现是位运算的左移和加1出现了问题;(所以以后在用位运算的时候,左移右移多少位要特别注意一下!!);

代码
第一种:

#include<stdio.h>
#include<iostream>
#include<algorithm>
using namespace std;void change(int *,int );int main()
{int T,i,j,sum,t,x,y;int  s[10],ss[10],a[5][1005];while(scanf("%d",&T)!=EOF){for(i=0;i<T;i++)scanf("%d%*c%d%*c%d%*c%d",&a[0][i],&a[1][i],&a[2][i],&a[3][i]);for(i=0;i<4;i++)sort(a[i],a[i]+T);for(i=0;i<4;i++){y=a[i][0];if(y!=a[i][T-1])break;a[i][T]=a[i][0];a[i][T+1]=255;}change(s,a[i][0]);change(ss,a[i][T-1]);a[i][T]=0;for(x=7;x>=0;x--){if(s[x]!=ss[x])break;a[i][T]=a[i][T]*2+s[x];}for(j=x;j>=0;j--)a[i][T]<<=1;for(j=i+1;j<4;j++)a[j][T]=0;sum=0;//  printf("%d\n",x);for(j=7;j>x;j--){sum=sum*2+1;}for(j=x;j>=0;j--)sum=sum*2;a[i][T+1]=sum;for(t=i+1;t<4;t++)a[t][T+1]=0;printf("%d.%d.%d.%d\n",a[0][T],a[1][T],a[2][T],a[3][T]);printf("%d.%d.%d.%d\n",a[0][T+1],a[1][1+T],a[2][T+1],a[3][T+1]);}return 0;
}void change(int *s,int t)
{int i;for(i=0;i<8;i++){s[i]=t%2;t/=2;}
}

第二种(可以再改进):

#include<stdio.h>int main()
{unsigned int T,i,j,a[1005][5],s,ss,tag,num,tum,sum,t,x,y,ttt;while(scanf("%u",&T)!=EOF){tag=0;for(i=0;i<T;i++)scanf("%u%*c%u%*c%u%*c%u",&a[i][0],&a[i][1],&a[i][2],&a[i][3]);for(i=0;i<4;i++){s=a[0][i];for(j=1;j<T;j++)if(s!=a[j][i]){tag=1;break;}if(tag)break;a[T][i]=a[0][i];a[T+1][i]=255;}num=1;for(x=(a[0][i]>>1);x>=0;x>>=1){ss=1;for(y=j;y<T;y++)a[y][i]>>=1;for(y=j;y<T;y++)if(x!=a[y][i]){j=y;ss=0;num++;break;}if(ss)break;}a[T][i]=x<<num;for(j=i+1;j<4;j++)a[T][j]=0;sum=0;for(j=1;j<=8-num;j++){sum<<=1;sum+=1;}a[T+1][i]=sum<<num;for(t=i+1;t<4;t++)a[T+1][t]=0;printf("%u.%u.%u.%u\n",a[T][0],a[T][1],a[T][2],a[T][3]);printf("%u.%u.%u.%u\n",a[T+1][0],a[T+1][1],a[T+1][2],a[T+1][3]);}return 0;
}

https://www.jiucaihua.cn/news/show-2632675.html

相关文章

ACM模板 数据结构

一并查集二树状数组一维单点更新区间查询一维区间更新单点查询二维单点更新区间查询二维区间更新单点查询技巧双关键字排序预处理 三线段树单点更新区间查询单点更新区间求和单点更新区间求最值 区间更新区间查询区间更新区间求和 一、并查集 const int maxn 300005; int…

关于shell输入 输出重定向

一 下面是关于输入输出重定向的语法格式 二 概述输出输入重定向大于号> &#xff1a;表示输出重定向 (会覆盖原文件)小于号<&#xff1a;输入重定向 &#xff08;如果你输入的是啥&#xff0c;那么就会显示输出的是啥&#xff0c;不会覆盖和追加到原文件里面&#xff09;…

Matlab将结构体struct字段内的数据转化到矩阵中

假设structure1,为一结构体&#xff0c;structure1.name为100个字符串 怎么将这些字符串不用循环一次性赋值到矩阵A?? Astructure1.name 为什么只是将第一个赋值过去&#xff1f; 答案是可以使用cat函数&#xff1a; 可以用cat函数&#xff0c; A cat(1,structur1.name)是按…

开源IM工程“蘑菇街TeamTalk”的现状:一场有始无终的开源秀

为什么80%的码农都做不了架构师&#xff1f;>>> 1、前言 随着云IM的发展&#xff0c;已吸引越来越多有IM需求的APP接入。但考虑到云IM无论从商业模式还是运营模式上&#xff0c;还需经过多年的沉淀&#xff0c;才可能真正实现客户与服务商的运营和服务良性循环的双…

Matlab中regionprops的使用示例

转载自&#xff1a;https://blog.csdn.net/shaoxiaohu1/article/details/40272531 有这样一幅图&#xff0c; 我们想获取其中的连通区域&#xff0c;可以使用以下代码&#xff1a; src_img_name blue_sky_white_clound_002594.jpg; img imread(src_img_name);% get binary …

当一个女人做到这样,她已经变了

那晚&#xff0c;他正和朋友在包厢和朋友唱歌&#xff0c;声音很大。-然后朋友的手机响了&#xff0c;朋友表情怪异的接着电话&#xff0c;-说&#xff0c;好&#xff0c;他在&#xff0c;我给他。-然后把电话递给了他。是妻子。-她说打他电话不接&#xff0c;只好打到朋友手机…

linux基础(8)-颜色显示

echo显示内容-带颜色显示格式&#xff1a;echo -e "\033[字体背景颜色;文字颜色m字符串 \033[0m"实例&#xff1a;echo -e "\n\n \t\t \033[40;32m安装hadoop主界面\033[1m \t\t"其中40的位置代表底色为黑色&#xff0c;32的位置代表字的颜色为绿色&#x…

AR系列路由器域间防火墙实施ACL

先简单说下华为路由器域间防火墙的一些基本特性&#xff1a; 状态化防火墙&#xff08;简单说就是高级别访问低级别会记录状态&#xff09;AR系列可以设置16种区域安全级别0-15&#xff0c;15保留给Loca区域使用位于两个不同级别的安全区域&#xff0c;低级别的默认不能主动访问…

如何在给定的图形上绘制圆形

希望生成一些人工的测试图像数据&#xff0c;在造groundtruth的时候需要在根据在图像上绘制的圆形生成二值的groundtruth.这时候该怎么做呢&#xff1f;一种最简单的方法是利用meshgrid函数&#xff0c;利用圆心和半径之间的关系生成二值图。关键代码如下&#xff1a; imgdoub…

IntelliJ IDEA2017创建web工程并实现远程部署tomcat

刚刚接触IntelliJ IDEA这款神器&#xff0c;很多东西都在摸索中&#xff0c;对于像在eclipse及myeclipse中创建动态web工程那样简单的事在idea中也搞了好久&#xff0c;今天我就分享一下本菜鸟痛苦的学习过程&#xff0c;下面是我的总结&#xff0c;希望对大家有一点帮助。官方…
最新文章