UVALive 7043 International Collegiate Routing Contest（字典樹）

題意：

輸入IPv4地址空間中的一些子網號，構成一個網絡集合。
輸出個數最小的一個網絡集合，要求其與輸入集合沒有交集，且相對與IPv4地址空間全集，與輸入集合互為補集。
輸出集合包含的子網號，格式遵循網絡規范。

解析：

這題可以用Trie樹來搞。
每個IP地址由32位二進制組成。整個地址空間可以表現為一棵二叉樹。
用Trie的節點標記每個二進制串所能抵達的終點，即子網覆蓋的終點位置。
建立Trie樹後，DFS遍歷樹上的分支，輸出沒有被覆蓋的分支即可。

my code

#include 
#include 
#include 
#include 
#include 
#define pb push_back
using namespace std;
typedef long long ll;

const int maxnode = (int)5e5  + 10;
const int sigma_size = 2;

vector ans;

struct Trie {
    int ch[maxnode][2];
    bool val[maxnode];
    int sz;

    void clear() { sz = 1; memset(ch[0], 0, sizeof(ch[0])); }
    Trie() { clear(); }
    int idx(char c) { return c - '0'; }

    void insert(char* s, int len) {
        int u = 0;
        for(int i = 0; i < len; i++) {
            int c = idx(s[i]);
            if(!ch[u][c]) {
                memset(ch[sz], 0, sizeof(ch[sz]));
                val[sz] = false;
                ch[u][c] = sz++;
            }
            u = ch[u][c];
        }
        val[u] = true;
    }

    void setIp(ll ip, int len) {
        int a[4];
        char buf[30];
        for(int i = 3; i >= 0; i--) {
            a[i] = ip % 256;
            ip >>= 8;
        }
        sprintf(buf, %d.%d.%d.%d/%d, a[0], a[1], a[2], a[3], len+1);
        ans.pb(buf);
    }

    void dfs(int u, int dep, ll cur) {
        if(val[u]) return;
        for(int i = 1; i >= 0; i--) {
            ll ip = cur | ((ll)i << (31-dep));
            if(!ch[u][i])
                setIp(ip, dep);
            else
                dfs(ch[u][i], dep+1, ip);
        }
    }
} trie;

int n;
char bit[33];
void trans(char* s, ll ip) {
    for(int i = 31; i >= 0; i--)
        s[31-i] = ((ip >> i) & 1) + '0';
    s[32] = '';
}

ll getIp(ll a, ll b, ll c, ll d) {
    return (1LL << 24) * a + (1LL<<16) * b + (1LL<<8) * c + d;
} 

int main() {
    int T, cas = 1;
    scanf(%d, &T);
    while(T--) {
        trie.clear();
        ans.clear();

        scanf(%d, &n);
        printf(Case #%d:
, cas++);
        if(n == 0) {
            puts(1
0.0.0.0/0);
            continue;
        }

        ll a, b, c, d, len, ip;
        for(int i = 0; i < n; i++) {
            scanf(%lld.%lld.%lld.%lld/%lld, &a, &b, &c, &d, &len);
            ip = getIp(a, b, c, d);
            trans(bit, ip);
            trie.insert(bit, len);
        }
        trie.dfs(0, 0, 0);

        int size = ans.size();
        printf(%d
, size);
        for(int i = 0; i < size; i++) {
            printf(%s
, ans[i].c_str());
        }
    }
    return 0;
}