西安公司注册网站,凡科建站怎么收费,贵州省住房和城乡建设厅网,仿站怎么修改成自己的网站CF1070B Berkomnadzor 题解
解题思路
不难想到将 IP 地址转化为二进制后插入一个字典树中#xff0c;转化后二进制的长度就是 x x x 的长度。我们需要记录每个串结尾的颜色#xff0c;不妨设黑名单为 1 1 1#xff0c;白名单为 0 0 0#xff0c;初始时每个位置的颜色是…CF1070B Berkomnadzor 题解
解题思路
不难想到将 IP 地址转化为二进制后插入一个字典树中转化后二进制的长度就是 x x x 的长度。我们需要记录每个串结尾的颜色不妨设黑名单为 1 1 1白名单为 0 0 0初始时每个位置的颜色是 − 1 -1 −1。
考虑如何判断输出 -1 的情况。不难发现当在插入当前二进制数的过程中当前节点到根节点的路径上存在一个颜色不为 − 1 -1 −1 且与当前串的颜色不同的点那么一定存在符合两个名单的 IP 地址。那么我们先把所有的串按照长度排序没有 x x x 的长度为 32 32 32然后依次插入这样能够保证在当前串插入前所有是它前缀的串已经插入了。
接下来考虑如何得到最优黑名单。我们定义 g ( x ) g(x) g(x) 表示在以 x x x 节点为根的子树中是否存在一个颜色为白色的节点如果存在 g ( x ) 1 g(x)1 g(x)1否则等于 0 0 0。那么我们遍历这棵字典树贪心地想深度越小的点一定是更优的因为如果不将这个点放入黑名单的话就需要将它的所有儿子放入那么子网个数一定是大于等于将它作为一个子网的子网个数的。那么我们遍历的时候找到第一个满足 g ( x ) 0 ∨ ( g ( f a x ) 1 ∧ x r o o t ) g(x)0 \vee (g(fa_x)1\wedge xroot) g(x)0∨(g(fax)1∧xroot) 的节点然后暴力向上跳将这个子网记录到答案中。
AC 代码
#includeset
#includemap
#includequeue
#includestack
#includemath.h
#includevector
#includestdio.h
#includestdlib.h
#includestring.h
#includevalarray
#includeiostream
#includealgorithm
#define B 35
#define N 200005
#define M N5
#define inf 2e97
struct Net{bool color;int bit32;bool val[B];Net():color(0),bit(32){}inline bool operator (const Net b) const {return bitb.bit;}inline void read(){char ch;scanf( %c,ch);if(ch-)color1;else color0;int a,b,c,d,x0;scanf(%d.%d.,a,b);scanf(%d.%d,c,d);chgetchar();if(ch/)scanf(%d,bit);xa*(124)c*(18);xb*(116)d*(10);for(int i31;i0;--i)val[32-i](xi)1;}inline void print(){puts(_______________________);printf(%d %d\n,color,bit);for(int i1;i32;i)printf(%d ,val[i]);putchar(\n);puts(-----------------------);}inline void printans(){for(int i1;i4;i){int x0;for(int j1;j8;j){int now(i-1)*8j;x(x1)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(){ cntnode0;for(int i0;iM;i)color[i]-1;}#define ls(x) tree[x][0]#define rs(x) tree[x][1]inline void Insert(Net a){int now0;for(int i1;ia.bit;i){if(color[now]!-1){if(a.color!color[now])puts(-1),exit(0);}int nexta.val[i];if(!tree[now][next])tree[now][next]cntnode;nowtree[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||x0)){int nowx; cnt;ans[cnt].bitdepth[x];int idepth[x]; while(now){int v(nowrs(fa[now]));ans[cnt].val[i]v;nowfa[now]; --i;}}}
}tree;
signed main(){scanf(%d,n);for(int i1;in;i)a[i].read();std::sort(a1,an1);for(int i1;in;i)tree.Insert(a[i]);tree.init(0);tree.dfs(0);printf(%d\n,cnt);for(int i1;icnt;i)ans[i].printans();
}
