201812 CSP认证 | CIDR合并

本文主要是介绍201812 CSP认证 | CIDR合并，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

CIDR合并
难是真的不难但是也写了我几个小时服了
这道题在有计网的基础上就很好理解了，没有在格式上有任何刁难你的。这里不讲背景了
官网提交结果以及满分代码如下：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<string, int> PSI;
const int N = 1e5 + 10;
int n;
struct node{string ip;int len;ll ten;  //ip前缀的十进制表示:为了方便排序
};
vector<node> ipPool;
vector<node> merge1; //第一轮合并的结果
vector<node> res;   //同级合并的最终结果
int to_int(string str)
{stringstream ssin(str);int x;ssin >> x;return x;
}
string to_str(int m)
{stringstream ssin;ssin << m;string str;ssin >> str;return str;
}
//用于第一步排序
bool cmp(node x, node y)
{if(x.ten == y.ten) return x.len < y.len;else return x.ten < y.ten;
}
//处理一个输入的ip,将其处理后存储到ipPool中
void handle(string str)
{int k = str.find('/');int len = 0; node temp;if(k != -1)  { len = to_int(str.substr(k + 1)); str = str.substr(0, k); }//开始解析ip, 将字符串按照'.'分割开来vector<string> vec;for(int i = 0, j = 0; i < str.size(); i = j + 1){  //将str用'+'分割开来j = str.find('.', i);  //从下标i开始找+号if(j == -1) j = str.size();vec.push_back(str.substr(i, j - i));}if(!len) len = vec.size() * 8;  //省略了长度型的ip书写方式if(vec.size() != 4){int sz = vec.size();for(int i = 1;i <= 4 - sz;i ++){vec.push_back("0");  //补0}}string ip = ""; ll ten = 0;  //将ip转化为十进制的数字for(int i = 0;i < vec.size();i ++) {ip = ip + vec[i] + '.';ll x = to_int(vec[i]);x <<= ((3 - i) * 8);ten += x;}ip = ip.substr(0, ip.size() - 1); //删去最后一个点ip += "/" + to_str(len);temp.ip = ip; temp.len = len; temp.ten = ten;ipPool.push_back(temp);
}//判断ipPool中b位置ip的匹配集是否是a位置ip匹配集的子集
bool subset(int a, int b)
{int lena = ipPool[a].len, lenb = ipPool[b].len;if(lena > lenb) return false;//接下来是lena <= lenb的情况,也就是二者的前lena个bit位置必须相同int delta = 32 - lena;int tena = ipPool[a].ten >> delta, tenb = ipPool[b].ten >> delta;  //只保留前lena位int temp = tena ^ tenb;if(temp) return false;  //前lena个bit位不相同return true;
}
//将ipPool中的元素从小到大进行合并
void small_Large_Merge()
{int a = 0, b = 1;bool st[N]; //考虑某个位置的元素是否存在memset(st, true, sizeof st);while(b < n){    //n也是ipPool的大小if(subset(a, b)){ st[b] = false; b ++; }else{ a = b; b ++; }}for(int i = 0;i < n;i ++){if(st[i]) merge1.push_back(ipPool[i]);}
}
//对merge1进行同级合并
void final_Merge()
{int a = 0, b = 1, sz = merge1.size();bool st[N];memset(st, true, sizeof st);  //功能同前面相同while(b < sz){node t;  //存储中间结果int lena = merge1[a].len, lenb = merge1[b].len;bool flag = false;  //是否能合并if(lena == lenb){//看二者是否能合并, 也就是看前len - 1位置是否完全相同,且最后一位不同int delta = 32 - lena;int tena = merge1[a].ten >> delta, tenb = merge1[b].ten >> delta;int tena2 = merge1[a].ten >> (delta + 1), tenb2 = merge1[b].ten >> (delta + 1);int cnt = 0;   //用来记录前len位有几位不相同int temp = tena ^ tenb;while(temp){cnt ++;temp &= (temp - 1);}temp = tena2 ^ tenb2;if(!temp && cnt == 1){  //前len - 1相同,第len不同,可以合并flag = true;t.ten = merge1[a].ten;t.len = merge1[a].len - 1; //长度不同string ip = merge1[a].ip;int k = ip.find('/');ip = ip.substr(0, k + 1);ip += to_str(t.len);t.ip = ip;}}if(flag){merge1[a] = t; st[b] = false;  //更新; a向前回溯if(a > 0){   //a > 0才有回溯的必要,注意这里st[0]是不可能为false的b = a; a --;while(!st[a]) a --;}else { //无需向前找了while(b < sz && !st[b]) b ++;};}else {a = b;b ++;while(b < sz && !st[b]) b ++;}}for(int i = 0;i < sz;i ++){if(st[i]) res.push_back(merge1[i]);}
}int main()
{ios::sync_with_stdio(false); cin.tie(0);cout.tie(0);cin >> n;for(int i = 0;i < n;i ++){string ip; cin >> ip;handle(ip);}sort(ipPool.begin(),ipPool.end(), cmp);//现在开始从小到大合并small_Large_Merge();//同级合并final_Merge();for(auto x : res){cout << x.ip << endl;}return 0;
}

本题我用了位运算来实现。能否合并的关键就是看前几位是否是相同的，如果前x位相同，第x + 1的异或结果为1的话，此时两个就可以合并成一个。因此我设置了一个len来保存ip地址的十进制数。
但就是这个我改了很久的错误
第62行我的初始代码是：ten += ( x << ((3 - i) * 8) )，结果总是负数
后来又测试了几个如下：

其实就是符号的问题。
如果我直接对128移位置，只在低位补零；此时的x的表示形式就是10000000 0000000 0000000 0000000。从补码的角度来说，因为最高位为1，此时就是负数！！！
而我若先赋值为128，此时这个数据只是存在与x空间的存储形式为00000000 00000000 00000000 10000000，再移位；此时变为00000000 10000000 0000000 0000000 0000000最高位仍然为0

这篇关于201812 CSP认证 | CIDR合并的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---