十二省联考 2019

佚名 6年前 (2019-04-08) 随笔 718人围观抢沙发百度已收录

由于比较懒，按难度顺序排序

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

D1T1

给一个序列，求前 $k$ 大区间异或和的和

$n \leq 500000,k \leq min(n^2,200000)$

sol：

超级钢琴

对每个 $i$，维护一个三元组 $(l,r,i)$ 表示左端点在 $[l,r]$，右端点在 $i$ 的区间异或最值，维护一个堆，按这个异或最值排序，每次将堆顶拿出来，分裂成最多两个区间，查一下异或最大值即可，区间异或最大值可以前缀和+可持久化 Trie 来解决

#include <bits/stdc++.h>
#define LL long long
#define rep(i, s, t) for(register int i = (s), i##end = (t); i <= i##end; ++i)
#define dwn(i, s, t) for(register int i = (s), i##end = (t); i >= i##end; --i)
using namespace std;
inline LL read() {
    LL x = 0, f = 1; char ch = getchar();
    for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = -f;
    for(; isdigit(ch); ch = getchar()) x = 10 * x + ch - '0';
    return x * f;
}
const int maxn = 5e5 + 10;
int n, k; LL a[maxn];
int root[maxn], ch[maxn << 6][2], idx[maxn << 6], v[maxn << 6], ToT;
void Insert(int &x, int pre, LL val, int LG, int id) {
    x = ++ToT; ch[x][0] = ch[pre][0]; ch[x][1] = ch[pre][1]; v[x] = v[pre] + 1; idx[x] = idx[pre];
    if(LG == -1) { idx[x] = id; return; }
    int px = (val >> LG) & 1; px = px ? 1 : 0;
    Insert(ch[x][px], ch[pre][px], val, LG - 1, id);
}
int query(int x, int pre, LL val, int LG) {
    if(LG == -1) return idx[x]; int px = (val >> LG) & 1; px = px ? 1 : 0;
    if(v[ch[x][!px]] - v[ch[pre][!px]] > 0)  return query(ch[x][!px], ch[pre][!px], val, LG - 1); 
    else return query(ch[x][px], ch[pre][px], val, LG - 1);
}
struct Node {
    int l, r, mxpos, i; LL ret;
    Node() {}
    Node(int _l, int _r, int _i) {
        l = _l, r = _r, i = _i;
        mxpos = query(root[r], root[l - 1], a[i], 31);
        ret = a[i] ^ a[mxpos - 1];
    }
    bool operator < (const Node &b) const { return ret < b.ret; }
}; priority_queue<Node> q;
int main() {
//    freopen("2.in","r",stdin);
    n = read(), k = read(); rep(i, 1, n) a[i] = a[i - 1] ^ read();
    rep(i, 1, n) Insert(root[i], root[i - 1], a[i - 1], 31, i);
    rep(i, 1, n) q.push(Node(1, i, i)); LL ans = 0;
    while(k--) {
        Node cur = q.top(); q.pop(); ans += cur.ret;
        if(cur.l < cur.mxpos) q.push(Node(cur.l, cur.mxpos - 1, cur.i));
        if(cur.r > cur.mxpos) q.push(Node(cur.mxpos + 1, cur.r, cur.i));
    } cout << ans << endl;
}

View Code

D2T2

一棵以 $1$ 号点为根的树，每个点有点权，两个点能放在一堆当且仅当这两个点没有祖先-后代关系，每堆的代价为堆内点权最大值，定义一个方案的代价为一些点组成的一些堆的权值和（如果放完之后还有单点，则这些单点每个算一堆），求所有方案中最小代价

$n \leq 2 \times 10^5$

sol：

考虑一条链（$1$ 号点不一定为链头）的解决方法，显然每堆里有一个左边的点，一个右边的点，那就每次拿出最大的两个合并就可以了

考虑多条链，发现...没什么区别嘛

然后就过了

#include <bits/stdc++.h>
#define LL long long
#define rep(i, s, t) for(register int i = (s), i##end = (t); i <= i##end; ++i)
#define dwn(i, s, t) for(register int i = (s), i##end = (t); i >= i##end; --i)
using namespace std;
inline int read() {
    int x = 0, f = 1; char ch = getchar();
    for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = -f;
    for(; isdigit(ch); ch = getchar()) x = 10 * x + ch - '0';
    return x * f;
}
const int maxn = 200010;
int n, a[maxn], id[maxn], tmp[maxn], _tim;
LL ans;
priority_queue<int> q[maxn];
vector<int> G[maxn];
void dfs(int x, int fa) {
    id[x] = ++_tim;
    for(auto to : G[x]) {
        if(to == fa) continue;
        dfs(to, x);
        if(q[id[to]].size() > q[id[x]].size()) swap(id[x], id[to]);
        int k = q[id[to]].size();
        rep(i, 1, k) {
            tmp[i] = max(q[id[x]].top(), q[id[to]].top());
            q[id[x]].pop(); q[id[to]].pop();
        }
        rep(i, 1, k) q[id[x]].push(tmp[i]);
    } q[id[x]].push(a[x]);
}
int main() {
    n = read();
    rep(i, 1, n) a[i] = read();
    rep(i, 2, n) {
        int fa = read();
        G[fa].push_back(i);
    } dfs(1, 1);
    while(q[id[1]].size()) { ans += q[id[1]].top(); q[id[1]].pop(); }
    cout << ans << endl;
}