LA 7043 International Collegiate Routing Contest 路由表 字典树离散化+bitset 银牌题
2024-09-03 18:39:32
题目链接:给你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简化运算
最新文章
- javascript 获取滚动条高度+常用js页面宽度与高度
- iOS开发多线程篇 — GCD的常见用法
- SqlServer数据文件增长也很快,到底是哪些表增长造成的呢?
- Spring配置MyBatis
- h.264的POC计算
- [Linux] Linux 中的基本命令与目录结构
- java 读取文件的路径
- phpstudy连接SQL Server 2008数据库 以及 php使用sql server出现乱码解决方式
- 如何重置密码 oracle sys和system
- VS2015配置内核WDK7600环境,32位下.
- Angular2学习笔记四(之Http通信)
- sql2008r2,以前好好可以用的,但装了vs2017后,连接不上了,服务也停了,结果手动也 启动不了, 无法加载或初始化请求的服务提供程
- 迁移 Emacs 的自定义设置
- react的学习笔记
- npm 离线安装依赖
- nodejs教程 安装express及配置app.js文件的详细步骤
- Python爬虫学习——布隆过滤器
- css3属性兼容性
- 开源的DirectUI界面库
- sublime text2 注册码