wordpress新用户站点优秀网页设计

CF1070B Berkomnadzor 题解

解题思路

不难想到将 IP 地址转化为二进制后插入一个字典树中，转化后二进制的长度就是 $x$ 的长度。我们需要记录每个串结尾的颜色，不妨设黑名单为 $1$，白名单为 $0$，初始时每个位置的颜色是 $-1$。

考虑如何判断输出 -1 的情况。不难发现，当在插入当前二进制数的过程中，当前节点到根节点的路径上存在一个颜色不为 $-1$ 且与当前串的颜色不同的点，那么一定存在符合两个名单的 IP 地址。那么我们先把所有的串按照长度排序（没有 $x$ 的长度为 $32$），然后依次插入，这样能够保证在当前串插入前，所有是它前缀的串已经插入了。

接下来考虑如何得到最优黑名单。我们定义 $g(x)$ 表示在以 $x$ 节点为根的子树中，是否存在一个颜色为白色的节点，如果存在，$g(x)=1$，否则等于 $0$。那么我们遍历这棵字典树，贪心地想，深度越小的点一定是更优的，因为如果不将这个点放入黑名单的话，就需要将它的所有儿子放入，那么子网个数一定是大于等于将它作为一个子网的子网个数的。那么，我们遍历的时候，找到第一个满足 $g(x)=0\vee (g(f{a}_x)=1\wedge x=root)$ 的节点，然后暴力向上跳，将这个子网记录到答案中。

AC 代码

#include<set>
#include<map>
#include<queue>
#include<stack>
#include<math.h>
#include<vector>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<valarray>
#include<iostream>
#include<algorithm>
#define B 35
#define N 200005
#define M N<<5
#define inf 2e9+7
struct Net{bool color;int bit=32;bool val[B];Net():color(0),bit(32){}inline bool operator <(const Net &b) const {return bit<b.bit;}inline void read(){char ch;scanf(" %c",&ch);if(ch=='-')color=1;else color=0;int a,b,c,d,x=0;scanf("%d.%d.",&a,&b);scanf("%d.%d",&c,&d);ch=getchar();if(ch=='/')scanf("%d",&bit);x+=a*(1<<24)+c*(1<<8);x+=b*(1<<16)+d*(1<<0);for(int i=31;i>=0;--i)val[32-i]=(x>>i)&1;}inline void print(){puts("_______________________");printf("%d %d\n",color,bit);for(int i=1;i<=32;++i)printf("%d ",val[i]);putchar('\n');puts("-----------------------");}inline void printans(){for(int i=1;i<=4;++i){int x=0;for(int j=1;j<=8;++j){int now=(i-1)*8+j;x=(x<<1)+val[now];} printf("%d",x);if(i!=4) putchar('.');} putchar('/');printf("%d\n",bit);}
}a[N],ans[N];
int n,cnt;
struct LibTree{int depth[M];int tree[M][2];int cntnode,g[M];int color[M],fa[M];LibTree(){ cntnode=0;for(int i=0;i<M;++i)color[i]=-1;}#define ls(x) tree[x][0]#define rs(x) tree[x][1]inline void Insert(Net a){int now=0;for(int i=1;i<=a.bit;++i){if(color[now]!=-1){if(a.color!=color[now])puts("-1"),exit(0);}int next=a.val[i];if(!tree[now][next])tree[now][next]=++cntnode;now=tree[now][next];}if(color[now]!=-1){if(color[now]!=a.color)puts("-1"),exit(0);} color[now]=a.color;}inline void init(int x){if(ls(x)){depth[ls(x)]=depth[x]+1;init(ls(x));fa[ls(x)]=x;g[x]|=g[ls(x)];}if(rs(x)){depth[rs(x)]=depth[x]+1;init(rs(x));fa[rs(x)]=x;g[x]|=g[rs(x)];} g[x]|=color[x]==0;}inline void dfs(int x){if(ls(x)) dfs(ls(x));if(rs(x)) dfs(rs(x));if(g[x]==0&&(g[fa[x]]==1||x==0)){int now=x; ++cnt;ans[cnt].bit=depth[x];int i=depth[x]; while(now){int v=(now==rs(fa[now]));ans[cnt].val[i]=v;now=fa[now]; --i;}}}
}tree;
signed main(){scanf("%d",&n);for(int i=1;i<=n;++i)a[i].read();std::sort(a+1,a+n+1);for(int i=1;i<=n;++i)tree.Insert(a[i]);tree.init(0);tree.dfs(0);printf("%d\n",cnt);for(int i=1;i<=cnt;++i)ans[i].printans();
}