【总结】省选云玩家做题笔记

我太菜了，NOIp才拿了个省三，所以没资格去省选，在家当一回云玩家。

2019.04.06

省选Day1，在家写了一上午作业。中午，省选大佬们考完，把题传到了QQ群里，交流思路。看成绩单，Ubospica学长名列全省第二，其他几个学长分也都挺高。

又写了一下午作业，看题，打算自己做一做试试。D1T1第一眼看上去是字典树，第二眼是可持久化字典树。在群里问了一句，的确是。开始码，心想我要是去能切一道题也不错。信誓旦旦敲完调试，过了样例。打开某谷，发现可以交，WA0，一脸懵逼，不做了。说真的我要是去省选不就完犊子。

剩下两道题。T2听PC学长说SA+拓扑乱搞60分，我是不太明白，毕竟我太菜了。T3巨鬼畜，给你所有数据点让你打表，限制你的代码长度。懒得下载测试点做了，反正估计我也就能骗个10分左右。

2019.04.07

省选Day2，在家写了一上午作业，写完了。下午，大佬们考完，看了下结果，三个学长进队了，并且GrayGoods学长Day1炸了才十几分，但是Day2考得好，照样进队，太强了。然后看题，就T2有个骗一条链15分的思路，敲了一发，交到某谷，真是15分。

回头看D1T1，后知后觉，#define int long long，提交，TLE60。我去，我打的应该是正解复杂度啊，怎么才60，难不成卡常？那就常数优化。new太慢，写了个内存池，然后随手关了cin的流同步，提交，TLE80。这么优化常数还过不了，应该是复杂度不对，在某谷讨论版求助一发，睡觉。

2019.04.08

中午到机房，先开某谷，看有没有人鸟我这个蒟蒻。还真有好几个回复的，说我这个复杂度没毛病，洛谷毒瘤卡常，LOJ应该能切。上LOJ交一发，还是这份代码，切了……

D1T1代码如下

// luogu-judger-enable-o2
#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#define int long long

using namespace std;

const int MAXN = 5e5 + 5;

int n, k, a[MAXN], ans;

struct Node{
    Node *ch[2];
    int siz, id;
    Node() {
        ch[0] = ch[1] = NULL;
        siz = id = 0;
    }
};

Node *newNode() {
    static Node *pool = new Node[1 << 20]; static int cnt = -1;
    if (cnt == (1 << 20) - 1) pool = new Node[1 << 20], cnt = -1;
    return &pool[++cnt];
}

Node *rt[MAXN];

void Insert(Node *&now, Node *pre, int bit, int id, int val) {
    now = newNode();
    if (pre) *now = *pre;
    now->siz++;
    if (bit < 0) {
        now->id = id;
        return;
    }
    if ((val >> bit) & 1) Insert(now->ch[1], pre ? pre->ch[1] : NULL, bit - 1, id, val);
    else Insert(now->ch[0], pre ? pre->ch[0] : NULL, bit - 1, id, val);
}

int Query(Node *u, Node *v, int bit, int val) {
    if (bit < 0) return v ? v->id : 0;
    int d = (val >> bit) & 1;
    if ((v && v->ch[d ^ 1] ? v->ch[d ^ 1]->siz : 0) - (u && u->ch[d ^ 1] ? u->ch[d ^ 1]->siz : 0) > 0) return Query(u ? u->ch[d ^ 1] : NULL, v ? v->ch[d ^ 1] : NULL, bit - 1, val);
    return Query(u ? u->ch[d] : NULL, v ? v->ch[d] : NULL, bit - 1, val);
}

struct Data{
    int l, r, x, id, val;
    Data(int l = 0, int r = 0, int x = 0): l(l), r(r), x(x) {
        id = Query(rt[l - 1], rt[r], 31, a[x]);
        val = a[x] ^ a[id - 1];
    }
    bool operator < (const Data &b) const {
        return val < b.val;
    }
};

priority_queue<Data> hp;

signed main() {
    ios :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        a[i] = a[i - 1] ^ x;
    }
    for (int i = 1; i <= n; i++) rt[i] = rt[i - 1], Insert(rt[i], rt[i], 31, i, a[i - 1]);
    for (int i = 1; i <= n; i++) hp.push(Data(1, i, i));
    while (k--) {
        Data u = hp.top(); hp.pop(); ans += u.val;
        if (u.l < u.id) hp.push(Data(u.l, u.id - 1, u.x));
        if (u.id < u.r) hp.push(Data(u.id + 1, u.r, u.x));
    }
    cout << ans << endl;
    return 0;
}

未几，partychicken和GrayGoods两位学长推门进来，立即受到集体%%%。我上去一顿问，问出来了把D2T2的树变成链的思路，但是敲不明白。翻了几篇题解，找了一个简明扼要大概能看懂的学习了一番，闷声开码。敲完，测样例，提交，A了，代码如下。

// luogu-judger-enable-o2
// luogu-judger-enable-o2
// luogu-judger-enable-o2
#include <iostream>
#include <queue>
#include <vector>
#define int long long

using namespace std;

const int MAXN = 2e5 + 5;

int n, a[MAXN], fa[MAXN], tmp[MAXN], id[MAXN], tim;
priority_queue<int> q[MAXN];
vector<int> g[MAXN];

void Dfs(int x) {
    id[x] = ++tim;
    for (int e: g[x]) {
        int y = e; Dfs(y);
        if (q[id[x]].size() < q[id[y]].size()) swap(id[x], id[y]);
        int m = q[id[y]].size();
        for (int i = 1; i <= m; i++) {
            tmp[i] = max(q[id[x]].top(), q[id[y]].top());
            q[id[x]].pop(); q[id[y]].pop();
        }
        for (int i = 1; i <= m; i++) q[id[x]].push(tmp[i]);
    }
    q[id[x]].push(a[x]);
}

signed main() {
    ios :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 2; i <= n; i++) cin >> fa[i], g[fa[i]].push_back(i);
    Dfs(1);
    int ans = 0;
    while (!q[id[1]].empty()) ans += q[id[1]].top(), q[id[1]].pop();
    cout << ans << endl;
    return 0;
}

简单算了一下，我要是去省选的话退役稳了。D1T1忘了开long long爆零，没忘的话看常数80~100不等，D1T2暴力不会打，D1T3能骗个5~15分的测试点。D2T2要是在考场上一条链能码出来15分。总体算来85~130分。我太菜了……

2019.04.12

后记：洛谷改了时限，80分代码AC了，没开内存池的从60变成了80。

版权属于：Noire02

本文链接：https://noire02.moe/archives/0406.html

北京第三区交通委提醒您：复制千万条，版权第一条。转载删出处，博主两行泪。