Greedy

贪心整合包 ARC076D Exhausted? 简要题意：有 \(n\) 个人 \(m\) 张椅子，第 \(i\) 个人只愿意坐在第 \(L_i\) 个椅子之前或第 \(R_i\) 个椅子之后，求至多有几个人坐下来。\(n,m\le 2\times 10^5,0\le L_i<R_i\le m+1 ......

贪心算法是以动态规划方法为基础的，在每个贪心算法之下，几乎总有一个更繁琐的动态规划算法。 贪心算法和动态规划不同之处在于：是否需要考虑子问题的解 贪心算法并不考虑子问题，直接在当前步骤中做出选择 动态规划无论是自底向上， 贪心算法设计步骤 将最优化问题转化为这样的形式：对其做出一次选择后，只剩下一个 ......

题目背景 Farmer John has MM cows, conveniently labeled 1…M1…M, who enjoy the occasional change of pace from eating grass. As a treat for the cows, Farmer ......

本来前面还有一点内容的，但是今天手残把文件从U盘里误删了，费了好大功夫恢复出来的时候发现前面一点内容已经被一段不知名且缺胳膊少腿的代码覆盖了，所以就只能这样了。这启发我没事多备份备份以防悲剧发生。 \(\color{red}{\text{CF1661F *2600}}\) 可以推广到许多函数上。所以 ......

ABC212F 暴力就是直接跳，显然不可过。 考虑对暴力进行优化，发现整个图是不会改变的，容易想到使用倍增。 显然是对边进行倍增的，令 \(f_{i, j}\) 表示从第 \(i\) 条边开始，跳了 \(2^j\) 条边后，到的是哪一条边，如果不存在，则设为 \(-1\)。 然后就是很显然的倍增了， ......

# [P4090 [USACO17DEC] Greedy Gift Takers P](https://www.luogu.com.cn/problem/P4090) 我们可以发现构成循环的一定是前面的任意一个前缀。 考虑二分答案。 然后，我们对于这个分界点 $mid$，我们需要知道他是否能被移动到 ......

CF1439C 考虑修改操作，由于序列是单调的，所以只需要线段树二分出修改的区间即可。 考虑查询，一定是若干个连续段，设一开始是 \(y\)，这个连续段结束后，\(y\) 至少减去一半，所以连续段个数是 \(\log\) 级别。 在线段树上遍历即可。 ......

如果只考虑选哪些奶牛吃派和奶牛吃派的顺序，就会陷入僵局，我们不妨考虑派的情况。 令 \(f_{i,j}\) 表示 \(i\sim j\) 这一段派，能满足一些奶牛，它们的最大可能体重。因为一头奶牛至少吃一个派，我们只关心区间内奶牛吃派的相对顺序，所以转移可以枚举当前区间最后吃的这头奶牛吃的某个派 \ ......

题目传送门：P5851 [USACO19DEC] Greedy Pie Eaters P - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 这题第一眼一头雾水，就从它求最值的方向开始想，不是dp就是贪心，想了一会儿，这道题没法用贪心，因为我们无论是按牛的体重贪心还是按吃派个数贪心都是 ......

简单题。 $i$ 向 $i$ 后**第一个** $j$，$a_j$ 比 $a_i$ 大的点连边，不难发现最后形成了一棵森林，并且一个点的父亲 $\text{fa}_i>i$。 题目变成了取 $[l,r]$ 中的点为起点，向祖先方向走去并且终点编号 $\le r$ 的最长链长度。 考虑离线，维护从每个 ......

[洛谷传送门](https://www.luogu.com.cn/problem/AT_keyence2021_e "洛谷传送门") [AtCoder 传送门](https://atcoder.jp/contests/keyence2021/tasks/keyence2021_e "AtCoder ......

**发表时间：**2021 **文章要点：**这篇文章给AlphaZero设计了一个新的value targets，AlphaZero with greedy backups (A0GB)。 AlphaZero的树里面有探索，而value又是所有结果的平均，所以并不准确。而选动作也是依概率选的，但真 ......