洛谷5361 [SDOI2019]热闹的聚会与尴尬的聚会
Luogu LOJ 分析 题目中的条件相当于 $(p+1)(q+1)\geq n$。 第一问可以每次选一个度数最小的点删去，然后更新答案。用堆维护可以做到 $\mathcal{O}(n\log n)$。 第二问是求独立集，也可以每次选一个度数最小的点，然后把它和与它相连的点都删去。 可以证明这样子一定是满足条件的。设第 $i$ 次删掉的点的度数为 $d_i$，那么有 $\sum_{i=1}^...
标签 堆 下的文章
- 首页
- 堆
JOISC2018 部分题解
高速道路の建設 / Construction of Highway 这个操作长得很像 LCT 中的 access。 于是我们每次只要 access 一下并把所有颜色段拿出来，然后树状数组求逆序对数，再把对应的边连上并把整条重链的颜色赋值为 $c_v$。 因为 access 是均摊 $\mathcal{O}(\log n)$ 的，所以每次颜色段数也是均摊 $\mathcal{O}(\log n...
LOJ6405 「ICPC World Finals 2018」征服世界
LOJ 分析 考虑反着看整个过程，那么相当于每个点有 $y_i$ 只老鼠和 $x_i$ 个洞，所有老鼠都必须进洞。 $u,v$ 匹配的代价是 $dep_u+dep_v-2dep_{\operatorname{LCA}(u,v)}$。因此我们开两个堆维护子树中老鼠和洞的 $dep$，每次把儿子的堆合并，然后取堆顶匹配，再把反悔操作加入堆中即可。 然而这样并不能保证所有老鼠都进洞，所以我们把老鼠...
UOJ455 【UER #8】雪灾与外卖
UOJ 分析 这个东西相当于洞有容量上限和额外代价，因此可以考虑模拟费用流。 我们维护两个堆，分别代表洞和老鼠，然后从左往右扫 如果当前是老鼠，取出一个代价最小的洞，代价即为 $x+cost$；后面有可能反悔，即让右边的一个洞匹配这只老鼠，所以要向老鼠堆中加入 $-(x+cost)-x$。 如果当前是洞，取出一只代价最小的老鼠，代价即为 $y+cost+w$；后面有可能反悔，即让右边的一只...
洛谷4698 [CEOI2011]Hotel
Luogu LOJ 分析 先考虑没有 $o$ 的限制怎么做。可以想到贪心，把房间按容量小到大排序、订单按人数从小到大排序，然后依次枚举每个房间，选择能容纳的租金最高的那个订单。正确性比较显然。 现在加入这个限制，可以考虑 WQS 二分。设 $f(x)$ 表示接受 $x$ 个订单的最大收入，感性理解可以知道 $f(x)$ 是凸的。二分斜率 $m$，则我们要求最大的 $b=f(x)-mx$，而这...
CF700D Huffman Coding on Segment
Codeforces Luogu 分析 考虑莫队，维护区间内每个数的出现次数，然后询问时建一棵 Huffman 树即可。然而暴力建树是 $\mathcal{O}(n)$ 的，显然过不了。 考虑根号分治，并维护出现次数为 $i$ 的数的个数，这样子对于出现次数 $\leq B$ 的数，可以直接 $\mathcal{O}(B)$ 扫一遍合并；对于出现次数 $>B$ 的数，显然只有 $\fr...
POI2012 简要题解
Festival 考虑差分约束。设 $dis_{i,j}$ 表示 $X_i$ 至多比 $X_j$ 大多少，则 若 $X_i+1=X_j$，则 $dis_{i,j}=-1,dis_{j,i}=1$，连边 $(i,j,-1)$ 和 $(j,i,1)$。 若 $X_i\leq X_j$，则 $dis_{i,j}=0$，连边 $(i,j,0)$。 考虑无解的情况。一种情况是出现负环，另一种情况是...
洛谷3826 [NOI2017]蔬菜
Luogu LOJ 分析 考虑求出卖了 $i$ 个蔬菜时的最大收益 $ans_i$。 容易想到，我们要先卖贵的菜，且要尽量靠后卖。 用一个堆维护所有还有存货的蔬菜，然后每次选一个收益最大的放在能放的最后的一天。 通过并查集维护每一天往前到哪一天才有没有用掉卖的额度即可求出这一天。 假设最多能卖 $cnt$ 个蔬菜，则前 $i$ 天的答案为 $ans_{\min\left\{cnt,m\tim...
洛谷5470 [NOI2019]序列
Luogu LOJ 分析 至少有 $L$ 个下标相同 $\Longleftrightarrow$ 至多有 $K-L$ 个下标不同。 考虑一个费用流模型，即从源点向 $a$ 中所有点连容量为 $1$、费用为 $a_i$ 的边，从 $b$ 中所有点向汇点连容量为 $1$、费用为 $b_i$ 的边，从 $a_i$ 向 $b_i$ 连容量为 $1$、费用为 $0$ 的边，再新建两个点 $C,D$，从...
CF603E Pastoral Oddities
Codeforces Luogu 分析 首先有一个结论：一个大小为偶数的连通块一定存在一个合法的边集，一个大小为奇数的连通块一定不存在一个合法的边集。 证明： 如果连通块大小为奇数，又因为每个点度数都为奇数，所以总度数为奇数，这是不可能的。 如果连通块大小为偶数，此时我们可以先找到一棵生成树，从下往上构造即可。可以发现一定能构造出解。 于是我们只需要保证图中没有大小为奇数的连通块即可。 ...