洛谷4006 小 Y 和二叉树
Luogu LOJ 分析 显然最小的 $d_i\leq 2$ 的点会是答案中第一个数。设这个点为 $rt$。 考虑从 $rt$ 开始跳父边。分类讨论一下当前点的情况 如果度数为 $1$，说明已经找到了根。 如果度数为 $2$，则有一条已经确定（是左儿子），我们只需要判断另一条边作为父边还是右儿子更优，只需要比较 $v$ 子树中最小的 $d_i\leq 2$ 的点和 $v$ 的大小即可判断。...
标签 贪心 下的文章
- 首页
- 贪心
CF639E Bear and Paradox
Codeforces Luogu 分析 首先考虑怎么放最优。考虑邻项交换法 于是按照 $\frac{a_i}{t_i}$ 从大到小排序即可。 一个想法是二分答案，check 时按 $a_i$ 排序然后看 $a_i\left(1-\frac{cx}{T}\right)$ 是否满足条件。但很容易发现这个是假的，因为 $\frac{a_i}{t_i}$ 相同的题目无法确定顺序，从而无法确定完成时...
CF1285F Classical?
Codeforces Luogu 分析 下文中的 $A$ 为 $\max_{i=1}^n\{a_i\}$。 考虑枚举答案的 $\gcd$，问题变为求满足 $\gcd(x,y)=g$ 的 $x,y$ 中 $x\times y$ 的最大值。 可以考虑贪心。我们先把所有满足为 $g$ 的倍数的数拿出来并从大到小排序，然后依次扫描，同时开一个栈来维护。对于每个数，我们需要判断栈中有没有与它互质的数，...
ARC096D Sweet Alchemy
AtCoder Luogu 分析 考虑差分，则问题变为每次选择一棵子树，消耗 $\sum m_i$ 的材料，造出 $sz$ 个物品，且每棵不是原树的子树都只能选至多 $D$ 次。 令每棵子树的 $m_i$ 之和为其代价，$sz$ 为其收益，则相当于一个多重背包。 然而 $D$ 在 $10^9$ 级别，直接多重背包显然无法通过。 考虑一个错误的贪心：设 $w_i$ 为收益，$v_i$ 为代价，...
洛谷4694 [PA2013]Raper
Luogu 分析 设 $f(x)$ 为造恰好 $k$ 张光盘的最小花费。感性理解可以发现 $f(x)$ 是一个下凸壳。 考虑 WQS 二分。二分斜率 $m$，求切点相当于最小化 $y$ 轴上的截距，即求出最小的 $f(x)-mx$。 这个最小值的意义就是可以随意造光盘，且每造一张光盘可以赚 $m$ 元时的最小花费（显然它一定非负）。 考虑用堆解决这个问题。 维护一个小根堆，每次将 $a_i$...
CF505E Mr. Kitayuta vs. Bamboos
Codeforces Luogu 分析 二分答案，则我们需要判定是否能够让所有竹子的高度 $\leq mid$。 由于竹子的高度不能小于 $0$，所以正着做不太好做；考虑反过来做，即每根竹子初始高度为 $mid$，每天会变矮 $a_i$，你每天可以选 $k$ 根竹子让他们变长 $p$，判断最后所有竹子的高度是否能 $\geq h_i$，且操作过程中竹子的高度不能 $<0$。 考虑贪心，...
CF1276C Beautiful Rectangle
Codeforces Luogu 分析 考虑枚举短边的长度 $r$。设数 $i$ 有 $cnt_i$ 个，那么我们至多能填 个数到矩形中。因此当短边长度为 $r$ 时长边至多为 $\left\lfloor\frac{s_r}{r}\right\rfloor$。 因为短边长度不超过 $\sqrt{n}$，因此我们可以在 $\mathcal{O}(n\sqrt{n})$ 的时间内求出答案。 现...