HDU 6625 (01字典树)

题意：
给定两个长为n的数组a和b；
重新排列a和b，生成数组c，c[i]=a[i] xor b[i]；
输出字典序最小的c数组。

分析：
将a中的数插入一颗01字典树a中；
将b中的数插入一颗01字典树b中；
在trie树上查找n次，每次同时在a和b中下移一层；
if 能同时走0，则同时走0；
else if 能同时走1，则同时走1；
else if 树a能走0&&树b能走1，则a走0、b走1；
else if 树a能走1&&树b能走0，则a走1、b走0；
else 向c中插入一个新数为这两个节点的异或值；
最后对c排序。
复杂度O（T*n*30）

#include<bits/stdc++.h>

using namespace std;

const int maxn = 1e6+;

typedef long long LL;

struct Trie01{

int ch[ * maxn][];

int cnt[*maxn];

int node_cnt;

inline void init(){

    node_cnt = ;

    memset(ch[],,sizeof(ch[]));

}

inline void Insert(LL x){

    int cur = ;

    for(int i = ;i >= ;--i){

        int idx = (x >> i) & ;

        if(!ch[cur][idx]){

            memset(ch[node_cnt],,sizeof(ch[node_cnt]));

            ch[cur][idx] = node_cnt;

            cnt[node_cnt++]=;

        }

        cur = ch[cur][idx];

        cnt[cur]++;

    }

}

}t1,t2;

vector<int> ans;

void solve(int N){

    int u1,u2;

    while(N--) {

        u1 = u2 = ;

        int x = ;

        for(int p = ; p >= ; p--) {

            if(t1.cnt[t1.ch[u1][]] && t2.cnt[t2.ch[u2][]]) {

                t1.cnt[t1.ch[u1][]]--;

                t2.cnt[t2.ch[u2][]]--;

                u1 = t1.ch[u1][]; u2 = t2.ch[u2][];

            } else if(t1.cnt[t1.ch[u1][]] && t2.cnt[t2.ch[u2][]]) {

                t1.cnt[t1.ch[u1][]]--;

                t2.cnt[t2.ch[u2][]]--;

                u1 = t1.ch[u1][]; u2 = t2.ch[u2][];

            } else if(t1.cnt[t1.ch[u1][]] && t2.cnt[t2.ch[u2][]]) {

                t1.cnt[t1.ch[u1][]]--;

                t2.cnt[t2.ch[u2][]]--;

                u1 = t1.ch[u1][]; u2 = t2.ch[u2][];

                x ^= ( << p);

            } else {

                t1.cnt[t1.ch[u1][]]--;

                t2.cnt[t2.ch[u2][]]--;

                u1 = t1.ch[u1][]; u2 = t2.ch[u2][];

                x ^= ( << p);

            }

        }

        ans.push_back(x);

    }

    return ;

}

int main(){

    int _;scanf("%d",&_);

    while(_--){

        int n;scanf("%d",&n);

        t1.init(),t2.init();

        for(int i=;i<=n;i++){

            int x;scanf("%d",&x);

            t1.Insert(x);

        }

        for(int i=;i<=n;i++){

            int x;scanf("%d",&x);

            t2.Insert(x);

        }

        ans.clear();

        solve(n);

        sort(ans.begin(),ans.end());

        printf("%d",ans[]);

        for(int i=;i<ans.size();i++)

        {

            printf(" %d",ans[i]);

        }puts("");

    }

}

巴特西

HDU 6625 (01字典树)

最新文章

热门文章