【十二省联考 2019】Day 1 / 2 题解

Intro

跑去上海打了这两场考试，结果惨不忍睹 (╯‵□′)╯︵┻━┻

所以我取消了最近几天的行程专心写题 _(:з)∠)_

本文缓慢更新，一些神仙题可能我一辈子都改不出来。

由于洛谷的新版界面丑陋不堪，除非迫不得已，将不提供洛谷的原题链接。

Day 1

异或粽子

简述题意

给定一个数列，求前 $k$ 大的区间异或值的和。

吐槽

它不希望用同样的馅儿的集合做出一个以上的粽子。

这句话被我理解成了 “不希望用同样的馅儿的集合”，以至于我认为所有集合是互斥的。成功爆零。

思路

我们对这个数列做一下前缀异或，令得到的数列为 $s$，问题实际上就是求 $k$ 个数对 $(i,j),1\le i\le j \leq n$，使得 $s[i-1] \ \text{xor} \ s[j]$ 之和最大。

如果我们固定 $j$ ，我们很容易在 $s[1] – s[j]$ 中找到一个 $i$ ，使得 $s[i-1] \ \text{xor} ] s[j]$ 的值为所有 $i$ 中的第 $k$ 大：对 $s[1] – s[j]$ 建立 $\text{Trie}$ 树，并记录子树大小，从根开始贪心查找即可。

首先，我们可以对于每个 $j$，找到最优的 $i$，将这个数对的答案记为 $v$，并且将 $(j,v,1)$ 这个三元组加入以 $v$ 为关键字的堆中。现在我们取出堆顶的三元组 $(j’,v’,p)$，将 $v’$ 计入答案，然后找出第 $p+1$ 优的 $i$ 对应的答案 $v”$，将三元组 $(j’,v”,p+1)$ 加入堆中。重复这个过程 $k$ 次，就可以得到最终的答案。

如果这样写，你需要一棵可持久化 $\text{Trie}$ 树，时空复杂度都不够优秀。

思考一下，我们需要可持久化，是因为数对 $(i,j)$ 里，$1\le i\le j \leq n$ 的限制；如果我们取消这个限制，会发生什么？

一个数对会被统计两次，仅此而已。所以不需要可持久化，找到前 $2k$ 个数对，最后的答案再除以 $2$ 即可。

代码

#include <bits/stdc++.h>
using namespace std;
const int maxn=5e5+1;
typedef long long ll;

ll read(){
    ll x=0;char ch=getchar();
    while(!isdigit(ch)) ch=getchar();
    while(isdigit(ch)) x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
    return x;
}

struct node{
    int id,k;ll val;
    node(int a=0,int b=0,ll c=0){
        id=a,k=b,val=c;
    }
    bool operator < (const node &x) const{
        return val<x.val;
    }
};

int n,k;
ll a[maxn],ans;
int t[maxn<<5][2],siz[maxn<<5],tot;
priority_queue<node>q;

void insert(ll x){
    int pos=0;
    for (int i=31;i>=0;--i){
        int son=(x>>i)&1;
        siz[pos]++;
        if (!t[pos][son])
        t[pos][son]=++tot;
        pos=t[pos][son];
    }
    siz[pos]++;
}

ll query(ll x,int rank){
    int pos=0;ll ans=0;
    for (int i=31;i>=0;--i){
        int son=(x>>i)&1;
        if (!t[pos][son^1])
            pos=t[pos][son];
        else if (rank<=siz[t[pos][son^1]])
            pos=t[pos][son^1],ans|=1ll<<i;
        else rank-=siz[t[pos][son^1]],pos=t[pos][son];
    }
    return ans;
}

int main(){
    n=read(),k=read();
    for (int i=1;i<=n;++i)
    a[i]=read()^a[i-1];
    for (int i=0;i<=n;++i)
    insert(a[i]);
    for (int i=0;i<=n;++i)
    q.push(node(i,1,query(a[i],1)));
    for (int i=1;i<=2*k;++i){
        node u=q.top();
        ans+=u.val;q.pop();
        if (u.k>=n) continue;
        q.push(node(u.id,u.k+1,query(a[u.id],u.k+1)));
    }
    printf("%lld\n",ans/2);
}

Day 2

春节十二响

简述题意

给定一个带点权树，求一种点集划分方案，使得任意集合内不存在两个点为祖先关系，最小化每个集合内点权最大值之和。

思路

可能是本次联考最简单的一道题？

我们从链的部分分得到启发。对于链的数据，因为在同一条从根向下的链上的点必须在不同集合内，我们可以从大到小贪心合并左右两条链。理解了这个做法，我们可以将它推广到一般情况。

给每个点分配一个优先队列，存储由它向下的链上可以被合并的所有点权。那么在树上 DFS 的时候，直接贪心合并一个点每个儿子的优先队列即可。

注意到直接合并是 $\Theta(n^2)$ 的。改为启发式合并，每次合并时两个队列时，保留最长的优先队列，这样复杂度就直接来到了 $\Theta(n\log n)$。

代码

#include <bits/stdc++.h>
#define chkmax(a,b) (b>a?a=b:0)
using namespace std;
const int maxn=2e5+1;
const int inf=1e9+1;
typedef long long ll;

int read(){
    int x=0;char ch=getchar();
    while(!isdigit(ch)) ch=getchar();
    while(isdigit(ch)) x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
    return x;
}

priority_queue<int>q[maxn];
vector<int>son[maxn];

int sta[maxn],top,cnt;
int n,fa[maxn],val[maxn],cur[maxn];
ll ans;

void solve(int u){
    cur[u]=++cnt;
    for (auto v:son[u]){
        solve(v);
        if (q[cur[u]].size()<q[cur[v]].size())
        swap(cur[u],cur[v]);
        top=q[cur[v]].size();
        for (int i=1;i<=top;++i){
            sta[i]=max(q[cur[u]].top(),q[cur[v]].top());
            q[cur[u]].pop();q[cur[v]].pop();
        }
        for (int i=1;i<=top;++i) q[cur[u]].push(sta[i]);
    }
    q[cur[u]].push(val[u]);
}

int main(){
    n=read();
    for (int i=1;i<=n;++i)
    val[i]=read();
    for (int i=2;i<=n;++i)
    son[fa[i]=read()].push_back(i);
    solve(1);
    while(!q[cur[1]].empty())
    ans+=q[cur[1]].top(),q[cur[1]].pop();
    printf("%lld\n",ans);
}