POI2011 简要题解
Conspiracy 考虑如果已经有了一组方案怎么得到其它的方案，可以发现只有以下三种情况：团内的一个点移了出去、团外的一个点移了进来、交换了团内和团外的两个点。只需要求出每个点是不是之和对方集合中的一个点冲突即可。 于是考虑构造一组方案。注意到每个点只能在团内或团外，于是 2-SAT 即可。 可能会有些卡空间。 代码 Lollipop 可以发现如果存在一段和为 $w$，则一定存在一段和为 ...
标签 贪心 下的文章
- 首页
- 贪心
ARC098F Donation
AtCoder Luogu 分析 设 $c_i=\max\left\{0,a_i-b_i\right\}$，则相当于要求任意在 $u$ 点的时刻手中都有至少 $c_u$ 円。 然后可以发现两个结论： 每个点只会在最后一次访问时被捐赠。 $c_i$ 大的会优先捐赠。 那么我们大概是这样捐赠的：首先选一个点 $u$，假设删掉 $u$ 后形成了 $tot$ 个连通块，则先捐赠掉 $tot-1$...
洛谷4698 [CEOI2011]Hotel
Luogu LOJ 分析 先考虑没有 $o$ 的限制怎么做。可以想到贪心，把房间按容量小到大排序、订单按人数从小到大排序，然后依次枚举每个房间，选择能容纳的租金最高的那个订单。正确性比较显然。 现在加入这个限制，可以考虑 WQS 二分。设 $f(x)$ 表示接受 $x$ 个订单的最大收入，感性理解可以知道 $f(x)$ 是凸的。二分斜率 $m$，则我们要求最大的 $b=f(x)-mx$，而这...
洛谷5996 [PA2014]Muzeum
Luogu 分析 不难看出一个最大权闭合子图的模型，然而直接求最大流显然过不了，于是可以考虑模拟最大流。 首先把这个坐标系变换一下。如果警卫 $a$ 能看到手办 $b$，则应有 于是可以把 $(h\times x+w\times y,h\times x-w\times y)$ 作为每个点的坐标，这样子警卫 $a$ 能看到手办 $b$ 当且仅当 $x_b\leq x_a,y_a\leq y_...
CF573E Bear and Bowling
Codeforces Luogu 分析 考虑一个贪心，即每次取贡献最大的一个，这里的贡献是 $k_i\times a_i+b_i$，其中 $k_i$ 表示前面选了的数量，$b_i$ 表示后面选了的 $a_i$ 的和。 那么我们相当于要维护一些直线，支持区间斜率加、截距加和求全局最大值。 考虑分块，对每块维护一个上凸壳，散块修改后重构、整块打标记即可。注意要把当前选出来的数删掉。 代码 // ...
CF700D Huffman Coding on Segment
Codeforces Luogu 分析 考虑莫队，维护区间内每个数的出现次数，然后询问时建一棵 Huffman 树即可。然而暴力建树是 $\mathcal{O}(n)$ 的，显然过不了。 考虑根号分治，并维护出现次数为 $i$ 的数的个数，这样子对于出现次数 $\leq B$ 的数，可以直接 $\mathcal{O}(B)$ 扫一遍合并；对于出现次数 $>B$ 的数，显然只有 $\fr...
洛谷3826 [NOI2017]蔬菜
Luogu LOJ 分析 考虑求出卖了 $i$ 个蔬菜时的最大收益 $ans_i$。 容易想到，我们要先卖贵的菜，且要尽量靠后卖。 用一个堆维护所有还有存货的蔬菜，然后每次选一个收益最大的放在能放的最后的一天。 通过并查集维护每一天往前到哪一天才有没有用掉卖的额度即可求出这一天。 假设最多能卖 $cnt$ 个蔬菜，则前 $i$ 天的答案为 $ans_{\min\left\{cnt,m\tim...
CF1316E Team Building
Codeforces Luogu 分析 有一个显然的状压 DP：设 $dp_{i,S}$ 表示前 $i$ 个人，$S$ 中的位置被选中时的最大力量值，转移枚举当前这个人当观众还是进某个位置即可。 然而 $p+k\leq n$，所以这个做法不太行。 注意到我们一定会选择 $a_i$ 较大的那些人当观众。将所有人按 $a_i$ 从大到小排序，当 $i-|S|>k$ 时 $i$ 显然不会被选...
洛谷4654 [CEOI2017]Mousetrap
Luogu LOJ 分析 为了方便，将陷阱作为根节点。那么冷静分析一下可以得到一些结论（没有证明） 当老鼠走到一个叶节点时，它将被困住。 当老鼠被困住时，将其它岔路口堵住，然后将到根的路径擦干净是最优的。 设 $f_u$ 表示老鼠进入 $u$ 子树后回到 $u$ 的最小操作次数。显然老鼠会找一个 $f$ 最大的子树进去，所以堵住 $f$ 最大的子树最优，此时老鼠会进入 $f$ 次大的子树...
CF1354F Summoning Minions
Codeforces Luogu 分析 有几个比较显然的结论（证明不会）： 一定存在一组最优解，使得所有卡都被摆上去过。感性理解：因为 $b_i\geq 0$ 所以你就算摆上去再拿下来也不会更差。 一定存在一组最优解，满足首先摆上 $k-1$ 张卡，再将 $n-k$ 张卡摆上去后立即拿下来，再将剩下的那张卡摆上去。感性理解：此时 $b_i$ 的贡献是最大的，且 $a_i$ 的贡献没有影响。...