CCF 201812-3 CIDR合并
//100分 93ms
#include<stdio.h>//CCF上stdio.h比cstdio快!!!
#include<string.h>
#include<algorithm>
typedef unsigned int UI;
const int N=1e5+;
struct IP{UI val,a[];}ip[N];//a[0]~a[3]表示IP地址,a[4]表示题目中的len
//val表示IP地址的十进制形式（主要作用：IP前缀能表示的数值范围）
char str[];int n;
void dealStr(int id){//字符串点分数字,转换成标准型
scanf("%s",str);
int cnt(),pn(),xn(),len=strlen(str);//pn点的数量，sn斜杠的数量
for(int i=;i<len;i++){
if(str[i]=='.') pn++;else
if(str[i]=='/') xn++;
}
for(int i=;i<;i++) ip[id].a[i]=;
char *p1=str,*p2,tmp[];
for(int i=;i<pn;i++){
p2=strchr(p1,'.');
strncpy(tmp,p1,p2-p1);//strncpy复制从p1中p2-p1长度的字符串到tmp中
tmp[p2-p1]=;
ip[id].a[cnt++]=atoi(tmp);
p1=p2+;
}
if(xn){
p2=strchr(p1,'/');//strchr从p1中查找‘/’第一次出现的位置
strncpy(tmp,p1,p2-p1);
tmp[p2-p1]=;
ip[id].a[cnt++]=atoi(tmp);//atoi 字符串转数字
p1=p2+;
strcpy(tmp,p1);
ip[id].a[]=atoi(tmp);
}
else{
strcpy(tmp,p1);
ip[id].a[cnt++]=atoi(tmp);
ip[id].a[]=cnt*;
}
ip[id].val=;//计算ip十进制值
for(int i=;i<;i++) ip[id].val+=ip[id].a[i]<<*(-i);
}
inline bool cmp(const IP &ip1, const IP &ip2){
for(int i=;i<;i++) if(ip1.a[i]!=ip2.a[i]) return ip1.a[i]<ip2.a[i];
return ;
}
inline void range(IP &ip0,UI &l,UI &r){//计算IP前缀能表示的数值范围
UI len=-ip0.a[];
l=ip0.val>>len<<len;
r=ip0.val|((<<len)-);
}
void union1(){//从小到大合并
int p=;
UI la,lb,ra,rb;
for(int i=;i<n;i++){
range(ip[p],la,ra);
range(ip[i],lb,rb);
if(la>lb||rb>ra) ip[++p]=ip[i];
}
n=p+;
}
inline bool judgeUnion(IP &ip1,IP &ip2,IP &res){//判断同级能否合并
if(ip1.a[]!=ip2.a[]||ip1.a[]<) return ;
res=ip1;res.a[]--;
UI la,lb,lc,ra,rb,rc;
range(ip1,la,ra);
range(ip2,lb,rb);
range(res,lc,rc);
if(la==lc&&rb==rc&&lb<=ra+) return ;
return ;
}
void union2(){
int p=;IP res;
for(int i=;i<n;i++){
if(judgeUnion(ip[p],ip[i],res)){
ip[p]=res;
while(p>&&judgeUnion(ip[p-],ip[p],res)) ip[--p]=res;
}
else{
ip[++p]=ip[i];
}
}
n=p+;
}
int main(){
scanf("%d",&n);
for(int i=;i<n;i++) dealStr(i);
std::sort(ip,ip+n,cmp);
union1();
union2();
for(int i=;i<n;i++) printf("%u.%u.%u.%u/%u\n",ip[i].a[],ip[i].a[],ip[i].a[],ip[i].a[],ip[i].a[]);
return ;
}
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + ;
struct node {
int ip[] , len , ip4[];
unsigned int d;
node(string s) {
bool flag = ;
int cnt = ;
d = len = ;
memset(ip,,sizeof(ip));
for(int i = ; i < s.length() ; i++) {
if(s[i] == '.')continue;
else if(s[i] == '/') {
flag = ;continue;
}
else {
int t = ;
while(isdigit(s[i])) {
t = t * + s[i] - '';
i++;
}
i--;
if(!flag)ip[cnt++] = t;
else len = t;
}
}
if(!len)len = cnt * ;
cnt = ;
for(int i = ; i < ; i++) {
d = d * + ip[i];
int t = ip[i];
for(int j = cnt ; j >= cnt - ; j--) {
ip4[j] = t % ;
t /= ;
}
cnt += ;
}
}
node(){}
bool operator < (const node b) const {
return d < b.d || (d == b.d && len < b.len);
}
};
node a[maxn];
list<node> ans;
bool vis[maxn];
bool judge(node b , node c) {
if(c.len < b.len)return false;
for(int i = ; i < b.len ; i++) {
if(b.ip4[i] != c.ip4[i]) {
return false;
}
}
return true;
}
bool judge1(node b , node c) {
if(c.len != b.len || c.len == )return false;
for(int i = ; i < b.len - ; i++) {
if(b.ip4[i] != c.ip4[i])return false;
}
int len = b.len - ;
if(b.ip4[len] != c.ip4[len]) return true;
else return false;
}
int main() {
int n;
ios::sync_with_stdio();
cin.tie();cout.tie();
cin >> n;
for(int i = ; i < n ; i++) {
string s;
cin >> s;
a[i] = node(s);
}
sort(a , a + n);
for(int i = ; i < n ; ) {
int p = i;
i++;
while(i < n && !vis[i]) {
if(judge(a[p] , a[i])) {
vis[i] = ;
i++;
}
else break;
}
}
for(int i = ; i < n ; i++) {
if(!vis[i])ans.push_back(a[i]);
}
for(auto t = ans.begin() ; t != ans.end() ; t++) {
auto t1 = t;
t1++;
while(t1 != ans.end() ) {
if(judge1(*t , *t1)) {
t -> len = t -> len - ;
ans.erase(t1);
if(t != ans.begin())t--;
t1 = t; t1++;
}
else break;
}
}
for(auto t = ans.begin() ; t != ans.end() ; t++) {
cout << t -> ip[] << "."<< t -> ip[] << "." << t -> ip[] << "." << t -> ip[] << "/" << t -> len<< "\n";
}
return ;
}网上list版代码