题目链接:给你n(n<=3e4)个路由地址(注意有子网掩码现象),

路由地址:128.0.0.0/1的形式

要求你输出一个路由集合,其是给定的路由集合的补集,且个数越少越好

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <iostream>
#include <cmath>
#include <stack>
#include <queue>
#include <vector>
#include <bitset>
#define MM(a,b) memset(a,b,sizeof(a));
#define inf 0x3f3f3f3f
using namespace std;
typedef long long ll;
#define CT continue
#define SC scanf
const int N=3*1e5+10;
const int mod=1e9+7;
int L[2*N],R[2*N],dep[2*N],cnt;
bool flag[2*N];
bitset<32> bit_ip; void init()
{
cnt=0;
MM(L,-1);
MM(R,-1);
MM(flag,0);
bit_ip.reset();
} void tree_insert(ll ip,ll deep)
{
bit_ip=ip;
int cur=0;
for(int i=0;i<deep;i++){
if(bit_ip[31-i]){
if(R[cur]==-1) R[cur]=++cnt;
cur=R[cur];
}
else{
if(L[cur]==-1) L[cur]=++cnt;
cur=L[cur];
}
}
flag[cur]=1;
} struct node{
bitset<32> bit_ip;int deep;
}; vector<node> ans;
void dfs(int u,int deep)
{
if(u==-1){
ans.push_back((node){bit_ip,deep});
return;
}
if(flag[u]) return;
bit_ip[31-(deep+1)]=1;
dfs(R[u],deep+1);
bit_ip[31-(deep+1)]=0;
dfs(L[u],deep+1);
} int main()
{
int cas,n,kk=0;
SC("%d",&cas);
while(cas--){
SC("%d",&n);
if(!n) {
printf("Case #%d:\n1\n",++kk);
printf("0.0.0.0/0\n");CT;
}
init();
int p[6],deep=0;
for(int i=1;i<=n;i++){
SC("%d.%d.%d.%d/%d",&p[1],&p[2],&p[3],&p[4],&deep);
ll ip=p[1];
for(int i=2;i<=4;i++) ip=(ip<<8)+p[i];
tree_insert(ip,deep);
} bit_ip=0;
ans.clear();
dfs(0,-1); printf("Case #%d:\n%d\n",++kk,ans.size());
for(int i=0;i<ans.size();i++){
node u=ans[i];
bitset<32> u_ip=u.bit_ip;
for(int i=3;i>=0;i--){
ll tmp=0;
for(int j=7;j>=0;j--) tmp=(tmp<<1)+u_ip[i*8+j];
printf("%lld",tmp);
if(i) printf(".");
}
printf("/%d\n",u.deep+1);
}
}
return 0;
}

  分析:

错因分析:不敢离散化字典树。。。。

解决:

1.既然是都是二进制,且只有32位,那么可以想到利用字典树,但是如果直接给每一位安排一个分叉的话,那么总共要2^32,显然开不了这么大的数组,但是最多只会插入1e4个路由地址,所以可以离散化一下,转变下思维,以前是i是父节点,2*i是左二子,2*i+1是右儿子,,,那么其实只要给每个节点设置一个L[]和R[]数组记录下子节点就好

2.因为牵涉到位运算,可以直接使用STL中的bitset简化运算

最新文章

  1. javascript 获取滚动条高度+常用js页面宽度与高度
  2. iOS开发多线程篇 — GCD的常见用法
  3. SqlServer数据文件增长也很快,到底是哪些表增长造成的呢?
  4. Spring配置MyBatis
  5. h.264的POC计算
  6. [Linux] Linux 中的基本命令与目录结构
  7. java 读取文件的路径
  8. phpstudy连接SQL Server 2008数据库 以及 php使用sql server出现乱码解决方式
  9. 如何重置密码 oracle sys和system
  10. VS2015配置内核WDK7600环境,32位下.
  11. Angular2学习笔记四(之Http通信)
  12. sql2008r2,以前好好可以用的,但装了vs2017后,连接不上了,服务也停了,结果手动也 启动不了, 无法加载或初始化请求的服务提供程
  13. 迁移 Emacs 的自定义设置
  14. react的学习笔记
  15. npm 离线安装依赖
  16. nodejs教程 安装express及配置app.js文件的详细步骤
  17. Python爬虫学习——布隆过滤器
  18. css3属性兼容性
  19. 开源的DirectUI界面库
  20. sublime text2 注册码

热门文章

  1. python学习-6 猜拳小游戏
  2. mysqlbinlog实战
  3. javascript——onsubmit和onreset事件 和开发中常用的方式
  4. UEditor编辑器
  5. .NET Core 创建Windows服务
  6. [NOIP2018模拟10.15]比赛报告
  7. Docker搭建Gitlab代码管理平台
  8. JSP 内置对象的说明
  9. poi的基本导入
  10. Java秒杀实战 (七)安全优化