CF1220D Alex and Julian
Codeforces 分析 考虑两个数 $a,b$ 要满足什么条件才可以同时留下。 可以发现，$a,b$ 可以构出一个 $0\to a\to \cdots\to\operatorname{lcm}(a,b)\to \operatorname{lcm}(a,b)-b\to\cdots 0$ 的环，这个环的大小是 显然可以根据 $a,b$ 的奇偶性进行讨论： 若 $a,b$ 都为奇数，则上式...
标签 贪心 下的文章
- 首页
- 贪心
JOI 2018 Final 简要题解
寒冬暖炉 同 CF1110B Tape。 先令每个客人来的时刻都开暖炉，其它时刻关暖炉。那么每次选最短的一段间隔不关直到只有 $k$ 段即可。 代码 美术展览 显然将所有艺术品按 $A_i$ 排序后答案一定是连续的一段。 设 $sum_i$ 表示 $\sum_{j=1}^iB_j$，那么题目给的那个式子可以拆成 $sum_r-sum_{l-1}-A_r+A_l$。 因此我们从后往前扫，维护 ...
CF521D Shop
Codeforces Luogu 分析 首先可以知道，我们执行操作的顺序一定是赋值 $\to$ 加 $\to$ 乘。 先考虑只有乘的情况。因为我们要最大化所有数的积，因此直接选最大的 $m$ 个即可。 再考虑有加的情况，我们想办法把加转化为乘。对于每一个位置，我们把对它的加操作按权值从大到小排序，显然我们选的会是一段前缀，因此我们可以转化为一些乘 $\displaystyle\frac{\s...
JOI 2019 Final 简要题解
传送门 勇者比太郎 看懂题后可以发现，我们要求每个 J 右边的 O 的数量乘下面的 I 的数量之和。 预处理前缀和后枚举每个 J 计算即可。 代码 画展 先以 $V_i$ 为第一关键字、$S_i$ 为第二关键字对所有画排个序，以 $C_i$ 为关键字对所有画框排序。 然后从后往前扫，如果当前的画能装进没有装画的 $C$ 最大的画框里，就把它装进去。 正确性比较显然？反正我不会证 代码 有趣的...
ARC083E Bichrome Tree
AtCoder Luogu 分析 首先注意到黑色还是白色并不重要，因为黑白可以互换。因此我们染一棵子树的根节点时可以强制让它为黑色。 那么，当染一棵子树的根节点 $u$ 时，子树中黑点的权值和应为 $X_u$ ，白点的权值和应该尽量小。 这里白点权值和尽量小是贪心的思想，因为权值尽量小是一定能通过一些更改满足条件。 于是可以考虑 DP。设 $f_u$ 表示以 $u$ 为根的子树中白点权值和最...
CF332C Students' Revenge
Codeforces 分析 贪心地想可以知道，主席一定优先做 $b$ 最大的，如果 $b$ 相同会做 $a$ 最小的。 那么我们把所有任务排序，使得优先级越高的越靠后。 现在假设我们选了 $p$ 个任务出来，那么一定存在一条分界线，使得线前的主席都不做，线后的主席都做。 于是我们可以枚举分界线的位置，然后选出线前 $b$ 最大的 $p-k$ 个和线后 $a$ 最大的 $k$ 个，这就是这条线...
CF1039D You Are Given a Tree
Codeforces 分析 首先询问只有一个的时候很简单，差不多就是 NOIP2018D1T3 ，直接贪心即可。 考虑根号分治： 对于链长 $\leq B$ 的询问，直接暴力求。时间复杂度 $O(nB)$ 。 对于链长 $>B$ 的询问，可以发现答案只有至多 $\frac{n}{B}$ 种，直接二分出相同的段即可。时间复杂度 $O(n\frac{n}{B}\log n)$ 。 可以...
洛谷4437 [HNOI2018]排列
Luogu 分析 首先，如果 $a[j]=k$ ，那么 $k$ 一定在 $j$ 的前面。 考虑从 $a[j]$ 向 $j$ 连边，构成一个图。显然，如果有环的话是无解的， 那么现在就是，如果要选子节点，必须要先选父节点。$i$ 节点第 $T$ 个选出来的话，贡献是 $Tw[i]$ 。 考虑贪心。设当前权值最小的节点为 $i$。 如果 $i$ 没有父节点的话，显然当前会选 $i$ 。 如果 ...
APC001F XOR Tree
AtCoder 分析 考虑把边权转为点权。设每个点的点权为所有与它相连的边的边权的异或和。 那么可以发现，$u$ 到 $v$ 的路径上的边权异或 $w$，相当于 $u$ 和 $v$ 的点权异或一个 $w$。 于是问题变成给你一些数，每次可以选出两个数并让它们异或一个数，求让所有数变为 $0$ 的最小操作次数。 显然可以先贪心地去消，把所有相同的先消掉。这样子会剩下至多 $15$ 个互不相同的...
BZOJ2457 [BeiJing2011]双端队列
BZOJ 分析 正着很难想，考虑反着做。 已知一个非降序列，将其分成尽量少的几段，使得每一段对应一个合法的双端队列。 然后发现一个合法的双端队列，一定满足下标先递减再递增。 然后就可以先sort，再贪心地凑。 对于相同的数，它们的顺序是可以交换的。显然下标递增或递减时最优。 然后就可以按照相同的数去划，每一个区间往后放，尽量的使得这样的单谷区间少。 举一个样例的例子： $A=[[0],[3,...