HDU6625： three arrays （字典树处理xor）

题意：给出A数组，B数组，你可以对A和B分别进行重排列，使得C[i]=A[i]^B[i]的字典序最小。

思路：对于这类题，显然需要建立字典树，然后某种形式取分治，或者贪心。假设现在有了两颗字典树A，B，显然尽量让同方向的先匹配。

而且同一棵树的左右两边相互不影响，所以可以直接贪：如果A树上出发左走有x个数字，B左走有y个数字，那么一定会左匹配min(x,y)；右匹配同理；剩下的交叉匹配；

看代码应该就会看懂了：add建立字典树。

dfs进行匹配； (i,j)从前往后分别是，(0,0) (1,1),(0,1) (1,0)保证了相同的先匹配。

#include<bits/stdc++.h>

#define rep(i,a,b) for(int i=a;i<=b;i++)

using namespace std;

const int maxn=;

int ch0[maxn*][],ch1[maxn*][],tot0,tot1;

int ans[maxn],num,sum0[maxn*],sum1[maxn*];

void init()

{

    rep(i,,tot0) rep(j,,) ch0[i][j]=;

    rep(i,,tot1) rep(j,,) ch1[i][j]=;

    tot0=tot1=num=;

}

void add(int ch[][],int sum[],int x,int &tot)

{

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

        int t=(x>>i)&;

        if(!ch[now][t]) ch[now][t]=++tot;

        now=ch[now][t];

        sum[now]++;

    }

}

void dfs(int now0,int now1,int cost,int dep)

{

    int e=min(sum0[now0],sum1[now1]);

    sum0[now0]-=e; sum1[now1]-=e;

    if(dep==-) {

        rep(i,,e) ans[++num]=cost;

        return ;

    }

    rep(k,,){

        int i=k&,j=i^; if(k<=) j=i;

        if(sum0[ch0[now0][i]]&&sum1[ch1[now1][j]])

          dfs(ch0[now0][i],ch1[now1][j],cost+(i==j?:(<<dep)),dep-);

    }

}

int main()

{

    int T,N,x;

    scanf("%d",&T);

    while(T--){

        init();

        scanf("%d",&N);

        rep(i,,N){

            scanf("%d",&x);

            add(ch0,sum0,x,tot0);

        }

        rep(i,,N){

            scanf("%d",&x);

            add(ch1,sum1,x,tot1);

        }

        dfs(,,,);

        sort(ans+,ans+N+);

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

        printf("%d\n",ans[N]);

    }

    return ;

}

巴特西

HDU6625： three arrays （字典树处理xor）

最新文章

热门文章