2019 Multi-University Training Contest 5 1002 three arrays Trie树+思维题
Trie   发布于 2019-08-06   389人围观  0条评论
Trie   发表于 2019-08-06   389人围观  0条评论

题目大意

给出两个长度为n的序列a,b,重新排列a、b使得两个序列各个位置上的数异或起来得到的序列C字典序最小,并输出最小字典序的c

题解

这题思路甚为巧妙。

关于异或的题目,我们总是分为各个二进制位置上的0/1来看,例如线性基、0/1Trie。此题就是通过0/1Trie来实现的。

首先我们对于两个序列,建立两个0/1Trie。

然后我们首先从第一个Trie中找出一个数,放入当前的候选答案的栈内,之后去另外一棵Trie中找与之异或值最小的数,再放入栈中,再去当前找到的值所在Trie的另一棵Trie中找与之异或值最小的数放入栈中,如此往复。

直到我们找到一个长度为2的环,此时这个长度为2的环中的两个数就是c中的一组答案了。因为他们两个相互为异或的最小值。就把他们存入c,并且从栈中pop掉,并将这两个数在自己的Trie树中删除,继续循环上面的步骤。

按照这种方法,直到我们把所有n个异或值都找出来,后面只需要排一遍序就是我们需要的最终答案了。

至于为什么环的长度一定为2而不可能为更多,这个东西是有证明的,不过暂时还没理解,暂时不写了。

代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
int get_num(){
    int num = 0;
    char c;
    bool flag = false;
    while((c = getchar()) == ' ' || c == '\r' || c == '\n');
    if(c == '-')
        flag = true;
    else num = c - '0';
    while(isdigit(c = getchar()))
        num = (num<<3) + (num<<1) + c - '0';
    return (flag ? -1 : 1) * num;
}
const int maxn = 1e5+10;
int ch[maxn*32][2],cnt[maxn*32][2];
int n,T;
int v,c[maxn];
int tot = 0;
int id;
int t;
int maxl = 29;
void build(int x,int ty){
    int now = 0;
    for(int i = maxl;i >= 0;--i){
        t = (x>>i) & 1;
        if(!ch[now][t]){
            ch[now][t] = ++id;
            cnt[ch[now][t]][ty] = 0;
        }
        now = ch[now][t];
        cnt[now][ty]++;
    }
    return;
}
int ret = 0;
int find(int ty){
    int now = 0;
    ret = 0;
    for(int i = maxl;i >= 0;--i){
        if(ch[now][0] && cnt[ch[now][0]][ty]){
            now = ch[now][0];
        }
        else{
            now = ch[now][1];
            ret |= (1 << i);
        }
    }
    return ret;
}
void del(int x,int ty){
    int now = 0;
    for(int i = maxl;i >= 0;--i){
        t = (x >> i) & 1;
        now = ch[now][t];
        cnt[now][ty] -= 1;
    }
    return;
}
int find_near(int x,int now,int ty){
    ret = 0;
    for(int i = maxl;i >= 0;--i){
        int t = (x>>i) & 1;
        if(ch[now][t] && cnt[ch[now][t]][ty^1]){
            now = ch[now][t];
            ret |= (t<<i);
        }
        else{
            now = ch[now][t^1];
            ret |= ((t^1)<<i);
        }
    }
    return ret;
}
int y;
int st[maxn<<1];
int top = 0;
void find_pair(int now,int ty,int last){
    top++;
    st[top] = now;
    while(top > 0){
        y = find_near(now,0,ty);
        if(y == last){
            c[++tot] = y ^ now;
            del(now,ty);
            top--;
            del(y,ty^1);
            top--;
            if(top == 0)break;
            else if(top == 1){
                last = -1;
                now = st[top];
            }
            else{
                last = st[top-1];
                now = st[top];
            }
        }
        else{
            last = st[top];
            st[++top] = y;
            now = y;
            ty ^= 1;
        }
    }
    return;
}
int main(){
    T = get_num();
    while(T--){
        tot = 0;
        for(int i = 0;i <= id;++i){
            ch[i][1] = ch[i][0] = 0;
            cnt[i][0] = cnt[i][1] = 0;
        }
        id = 0;
        n = get_num();
        for(int i = 1;i <= n;++i)
            st[i] = 0;
        for(int i = 1;i <= n;++i){
            v = get_num();
            build(v,0);
        }
        for(int i = 1;i <= n;++i){
            v = get_num();
            build(v,1);
        }
        while(tot < n){
            int x = find(0);
            find_pair(x,0,-1);
            top = 0;
        }
        sort(c+1,c+n+1);
        printf("%d",c[1]);
        int cnt = 1;
        for(int i = 2;i <= n;++i){
            printf(" %d",c[i]);
        }
        printf("\n");
    }
    return 0;
}


上一篇: APIO 2012 dispatching BZOJ 2809 左偏树

下一篇: 2019 Multi-University Training Contest 1004 equation 思维题

立即登录,发表评论
没有帐号?立即注册
0 条评论