【总结】省选云玩家做题笔记
我太菜了，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
北京第三区交通委提醒您：复制千万条，版权第一条。转载删出处，博主两行泪。
0 条评论