比赛的时候愣是没看懂这一题是啥意思,最后队友写完了觉得有问题也木有submit==
前面说了一大串反转路由表,in short之后就是说取个当前子网集合的补集,全集是整个IPV4地址空间。我当时一直纠结main routing table as small as possible是为何,现在觉得是防止两个子网可以用一个子网代替的case吧,比如11100000.0.0.0/4+11110000.0.0.0/4=11100000.0.0.0/3
因为subnet有公共的前缀,所以可以用字典树存储,寻找补集就是遍历字典树,在空节点处返回,另外遍历到现有子网号的末尾亦要返回。因为dfs到第一个空节点就return,所以可以保证是最小的集合。另需注意搜索过程中要恢复现场。
用字典树存储整个IPV4地址空间,需要3W*33个节点。此处是一颗二叉树。
eg.
0.0.0.0/1(subnet:0)
32.0.0.0/3(subnet:001)
224.0.0.0/3(subnet:111)
则对应的trie树如下,黑色节点是中间节点,红色节点是subnet的最后一个节点。
一直WA on test 2,最后对拍发现是val[maxn]数组开小了,写成了val[3W]。%>_<% 居然对着大白书敲模板也能敲错。可为啥不是RE却是WA。。
Trick:参考大神的blog后发现用bitset可以很方便地实现二进制和十进制的互换。
#include<iostream> #include<stdio.h> #include<cstdio> #include<stdlib.h> #include<vector> #include<string> #include<cstring> #include<cmath> #include<algorithm> #include<stack> #include<queue> #include<ctype.h> #include<map> #include<time.h> #include<bitset> using namespace std; //Xi'an Reigonal I const int maxn=30010*33; int T; int n; int a[5]; int ch[maxn][2]; int val[maxn];// val[3w] leads to WA on test 2, which is big test case. int sz; bitset<32>b(0); vector<pair< bitset<32>,int> >ans; void insert(bitset<32>bit,int dep,int v) { int u=0; for(int i=0;i<dep;i++) { int c=bit[32-i-1]; if(!ch[u][c])//ch[u][0] refers to 0, ch[u][1] refers to 1 { memset(ch[sz],0,sizeof(ch[sz])); val[sz]=0; ch[u][c]=sz++; } //cout<<"u: "<<u<<" c: "<<c<<" ch: "<<ch[u][c]<<endl; u=ch[u][c]; } val[u]=v; //cout<<"val "<<u<<" "<<val[u]<<endl; } void traversal(int dep,int u) { if(val[u]==1) { return; } //if(ch[u][0]==0&&ch[u][1]==0) if(dep!=0&&u==0) //if(u==0) { // for(int i=31;i>=0;i--) // { // cout<<b[i]; // } // cout<<endl; ans.push_back(make_pair(b,dep)); return; } b[32-dep-1]=0; traversal(dep+1,ch[u][0]); b[32-dep-1]=1; traversal(dep+1,ch[u][1]); b[32-dep-1]=0;//recover 恢复现场,否则非子网的IP addr部分也会出现1 } int main() { //freopen("input.txt","r",stdin); freopen("data.txt","r",stdin); freopen("out1.txt","w",stdout); scanf("%d",&T); for(int ca=1;ca<=T;ca++) { memset(ch,0,sizeof(ch)); memset(val,0,sizeof(val)); sz=1; ans.clear(); b.reset(); scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%d.%d.%d.%d/%d",&a[0],&a[1],&a[2],&a[3],&a[4]); long long tmp=0; for(int j=0;j<4;j++) { tmp=tmp*256+a[j]; } bitset<32>ip(tmp); insert(ip,a[4],1); } traversal(0,0); printf("Case #%d:\n",ca); if(n==0) { printf("1\n"); printf("0.0.0.0/0\n"); } else { printf("%d\n",ans.size()); for(int i=0;i<ans.size();i++) { bitset<32>ipsub=ans[i].first; for(int j=3;j>=0;j--) { int a=0; for(int k=7;k>=0;k--) { a=a*2+ipsub[j*8+k]; } printf("%d",a); if(j!=0) { printf("."); } } printf("/%d\n",ans[i].second); } } } return 0; }