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$ 即可。

代码

Day 2

春节十二响

简述题意

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

思路

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

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

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

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

代码