题目大意:
给你一些子网,求它们在整个网段的补集。
思路:
将子网转换成二进制建一棵Trie,直接DFS搜到没有了就记下来输出。注意:所给的子网会有交集,若搜到结尾就不向下搜了。
代码:
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define M 40000
using namespace std;
int cnt,num,a[],flag[M<<],trie[M<<][];
struct node { int len; int d[]; }ans[M<<]; int read()
{
int x=;
char ch=getchar();
while (ch<'' || ch>'') ch=getchar();
while (ch>='' && ch<='') x=(x<<)+(x<<)+ch-,ch=getchar();
return x;
} void wk(int x,int y)
{
for (int l=;l;l--,x/=) a[l+(y<<)]=x%;
} void ins(int l)
{
int now=,i,j;
for (i=;i<=l;now=trie[now][a[i]],i++)
if (!trie[now][a[i]]) trie[now][a[i]]=++cnt;
flag[now]=;
} void sa(long long x,int l)
{
ans[++num].len=l; int i,k=;
for (i=l;i;i--,x>>=) a[i]=x%;
ans[num].d[]=ans[num].d[]=ans[num].d[]=ans[num].d[]=;
for (i=;i<=l;i++)
{
ans[num].d[k]=(ans[num].d[k]<<)+a[i];
if (i%==) k++;
}
if (l%) ans[num].d[k]<<=(-l%);
} void dfs(int k,long long x,int l)
{
if (flag[k]) return;
if (trie[k][])
if (trie[k][]) dfs(trie[k][],x<<,l+),dfs(trie[k][],x<<|,l+);
else sa(x<<|,l+),dfs(trie[k][],x<<,l+);
else if (trie[k][]) sa(x<<,l+),dfs(trie[k][],x<<|,l+);
} int main()
{
int t=read(),ii;
for (ii=;ii<=t;ii++)
{
int n=read(),i,j;
memset(trie,,sizeof(trie));
memset(flag,,sizeof(flag));
for (i=;i<=n;i++)
{
int u=read(),v=read(),w=read(),x=read();
wk(u,),wk(v,),wk(w,),wk(x,),ins(read());
}
num=,dfs(,,);
printf("Case #%d:\n",ii);
if (!n) printf("1\n0.0.0.0/0\n");
else
{
printf("%d\n",num);
for (i=;i<=num;i++) printf("%d.%d.%d.%d/%d\n",ans[i].d[],ans[i].d[],ans[i].d[],ans[i].d[],ans[i].len);
}
}
return ;
}