比赛 NOIP模拟赛1 评测结果 AAAAAAAAAA
题目名称 异或 最终得分 100
用户昵称 Chenyao2333 运行时间 2.317 s
代码语言 C++ 内存使用 31.07 MiB
提交时间 2018-02-08 21:20:50
显示代码纯文本
#include <cstdio>
#include <algorithm>
#include <queue>

using namespace std;

const int kN = 1e5 + 10;

int N, K;

int root[kN];

int t[kN*33][2], tcnt;
int val[kN*33];

int a[kN];

bool get(int v, int i) {
    return (v & (1 << i) ) > 0;
}

void insert(int &x, int fa, int v, int deep) {
    //printf("%d %d %d %d\n", x, fa, v, deep);
    x = ++tcnt;
    t[x][0] = t[fa][0];
    t[x][1] = t[fa][1];
    val[x] = val[fa] + 1;

    if (deep == -1) {
        return;
    }

    bool s = get(v, deep);
    insert(t[x][s], t[fa][s], v, deep-1);
}

struct Ans{
    int XOR;

    int rv;
    int left;
    int k;


    bool operator < (const Ans &ans) const {
        return  XOR > ans.XOR;
    }
};


Ans find(int v, int x, int k) {
    //printf("%d %d %d\n", v, x, k);
    int left = x;
    int K = k;
    int XOR = 0;
    for (int i = 29; i >= 0; i--) {
        bool s = get(v, i);
        //printf("val[t[x][s]] = %d\n", val[t[x][s]]);
        if (val[t[x][s]] >= k) {
            x = t[x][s];
        } else {
            k -= val[t[x][s]];
            x = t[x][!s];
            XOR ^= 1 << i;
        }

        if (i == 0) {
           // printf("XOR: %d v: %d left: %d k: %d val[x]: %d\n", XOR, v, left, k, val[x]);
            if (val[x] >= k) {
                return (Ans){XOR, v, left, K};
            } else {
                return (Ans){-1, -1, -1, -1};
            }
        }
    }
}

int main() {
    freopen("xorxor.in", "r", stdin);
    freopen("xorxor.out", "w", stdout);

    scanf("%d %d", &N, &K);
    for (int i = 1; i <= N; i++) {
        int v;
        scanf("%d", &v);
        insert(root[i], root[i-1], v, 29);
        //printf("root[%d]= %d\n", i, root[i]);
        //fflush()
        a[i] = v;
    }

    //printf("hi\n");


    priority_queue<Ans> q;
    for (int i = 2; i <= N; i++) {
        Ans ans = find(a[i], root[i-1], 1);
        q.push(ans);
    }


    while (q.size()) {
        Ans ans = q.top();
        q.pop();
        K--;
        
        if (K == 0) {
            printf("%d\n", ans.XOR);
            return 0;
        }

        ans = find(ans.rv, ans.left, ans.k+1);
        if (ans.XOR == -1) {
            continue;
        }
        q.push(ans);
    }
    return 0;
}