cf1416 C. XOR Inverse（字典树、逆序对、贪心）

本文主要是介绍cf1416 C. XOR Inverse（字典树、逆序对、贪心），对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

题意：

给定数组 \(a[]\)，找一个整数 \(x\)，构造数组 \(b[]\) ，$b_i=a_i \oplus x $使得 \(b[]\) 中的逆序对数最少，其次使得 \(x\) 尽量小。输出最少逆序对数与 \(x\)

\(n\le 3e5, 0\le a_i\le 1e9\)

思路：

看到异或就要考虑一下xor字典树！

贪心从高到低考虑每一位。根据异或的性质，若x的这一位选0则所有数的这一位不变，若x的这一位选1则所有数的这一位取反（这会使所有正序对变成逆序对）

一边往xor字典树中加数，一边记录所有第1~k-1位完全相同的数字，第k位不变会有多少逆序对，第k位取反又会有多少逆序对

字典树的空间应该是一个先等比后相等的数列的和？这题开 30N 即可

（本来的思路是递归，从高位到低位不断把数组划成更小的子段，线性求01数组的逆序对数，后来发现不可行，因为要求的是前缀相同的子序列而非子段的逆序对数）

const int N = 3e5 + 5;

int son[N*30][2], siz[N*30], idx;
ll zh[33], ni[33];
void ins(int x)
{
    int p = 0;
    for(int k = 29; k >= 0; k--)
    {
        int u = (x>>k)&1;

        if(u == 0) ni[k] += siz[son[p][1]];
        else zh[k] += siz[son[p][0]];

        if(!son[p][u]) son[p][u] = ++idx;
        p = son[p][u]; siz[p]++;
    }
}

main()
{
    iofast;
    int n; cin >> n; while(n--) {
        int x; cin >> x; ins(x);
    }

    ll ans = 0, x = 0;
    for(int k = 29; k >= 0; k--)
        if(zh[k] < ni[k]) ans += zh[k], x |= (1<<k);
        else ans += ni[k];
    cout << ans << ' ' << x;
}

这篇关于cf1416 C. XOR Inverse（字典树、逆序对、贪心）的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！