LA 7043 International Collegiate Routing Contest 路由表 字典树离散化+bitset 银牌题

题目链接：给你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:
1
",++kk);
            printf("0.0.0.0/0
");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:
%d
",++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
",u.deep+1);
        }
    }
    return 0;
}

　　分析：

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

解决：

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

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