Perfect Security

Perfect Security

题意

• 给出一个n，两个长度为n的数组（分别记为 a , p ），问如何排列p数组使得a [ i ] ^ p [ i ]的 最后的结果排列字典序最小

分析

• 贪心的想，因为要结果排列字典序最小，那第一个结果得最小，第二个类似....那就可以对每一个a [ i ] 都进行查询操作，求得与他异或结果最小的 p[ i ] ,同时标记 p [ i ] 表示他已经被用过了

代码

#include<bits/stdc++.h>

#define R register
#define ll long long
#define inf INT_MAX

using namespace std;

const int N=3e5+10;

int n,tot;
int a[N],cnt[N*20],tr[2][N*20];

inline void ins(int x)
{
    int rt=0;
    for (int i=30;i>=0;i--)
    {
        bool c=((x>>i)&1);
        if(!tr[c][rt]) tr[c][rt]=++tot;
        rt=tr[c][rt];cnt[rt]++;
    }
}

inline int find(int x)
{
    int ans=0,rt=0;
    for (int i=30;i>=0;i--)
    {
        bool c=((x>>i)&1);
        if(tr[c][rt]&&cnt[tr[c][rt]])
        {
            cnt[tr[c][rt]]--;
            rt=tr[c][rt];
        }
        else
        {
            cnt[tr[c^1][rt]]--;
            ans+=(1<<i);
            rt=tr[c^1][rt];
        }
    }

    return ans;
}

int main()
{
    scanf("%d",&n);
    for (int i=1;i<=n;i++) scanf("%d",&a[i]);
    for (int i=1,x;i<=n;i++)
    {
        scanf("%d",&x);
        ins(x);
    }

    for (int i=1;i<=n;i++)
    {
        printf("%d",find(a[i]));
        if(i!=n) printf(" ");
        else puts("");
    }

    return 0;
}