贪心问题丢树上-＞利用决策唯一+贪心完后缩点为一个子问题：0909T1
贪心问题丢树上-＞利用决策唯一+贪心完后缩点为一个子问题：0909T1
本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132795053
不考虑上树，就是个经典的贪心，也就是按 排序。
丢树上，要求父亲必须比儿子先选，也就是多了一种限制条件。
但此时先从全局出发，对于某个节点若其 为全局最大，那么 选完父亲后必须选他 ，因为选择走其他地方必然没有走这里更优。
然后此时对于这个父亲节点，他现在的 决策唯一
然后我们就可以把这个点和父亲节点 缩 在一起，继续做上述过程。
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 zhangxixi的博客！
相关推荐
2023-12-21
定二分所谓的界+调整法：[AGC045B] 01 Unbalanced
定二分所谓的界+调整法：[AGC045B] 01 Unbalanced 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135125239 https://www.luogu.com.cn/problem/AT_agc045_b 考虑0为1，1为-1，然后就是使前缀和极差最小。（套路1） 一个常见思路是二分，也就是定上界M，使下界尽可能大，但此题不满足单调性，所以不能够二分。 我们考虑调整法。我们先让所有？为-1 然后求出当前max值为Z。则M的下界为Z。 如...
2024-01-01
反向贪心决定博弈+博弈论中条件改变人的决策满足单调性：1229A
反向贪心决定博弈+博弈论中条件改变人的决策满足单调性：1229A 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135329131 http://cplusoj.com/d/senior/p/SS231229A 结论： 人们倒着来，每个人去掉当前对自己最不利的 因此我们有了 O(n3)O(n^3)O(n3) 考虑当一个人变了后，每个人的决策必然满足单调性，因此就可以平方了 12start coding at 20:19passing at 21:18 123...
2022-01-20
【CF1304C Air Conditioner】题解
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15826957.html 题目 Gildong owns a bulgogi restaurant. The restaurant has a lot of customers, so many of them like to make a reservation before visiting it. Gildong tries so hard to satisfy the customers that he even memorized al...
2023-10-11
巧妙设计状态+不断对拍寻找合适贪心策略：P8341
巧妙设计状态+不断对拍寻找合适贪心策略：P8341 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133780272 https://www.luogu.com.cn/problem/P8341 场上看错题了… 考虑维护几个东西： a[x],b[x]a[x],b[x]a[x],b[x] 表示完整匹配，半完整匹配的数量。 p[x]p[x]p[x] 表示某条向上路径在 xxx 完成任务，可以变成 bbb 。 然后如果 xxx 位置有向上的话，我们贪心希望它和 ...
2022-01-08
【ZR #540. 【19普转提4】串串】题解
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15778576.html 题目链接 题目 给定两个长度为 nnn 的只包含’a’,‘b’,'c’的字符串s,ts,ts,t。 请打乱串 sss，使得 ∀i,si≠ti\forall i,s_i \not= t_i∀i,si=ti，且 sss 字典序最小。 思路 对于 ttt 串中从前往后每一个字母，在 sss 的剩余可选字母中选字典序最小的。 如果 sss 的剩余字母中没了，就往前找第一个可以替换的替换。 最后再对每种 ttt 中的字母按...
2023-09-30
贪心找性质+DP表示+矩阵表示+线段树维护：CF573D
贪心找性质+dp表示+矩阵表示+线段树维护：CF573D 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133437456 比较套路的题目 首先肯定贪心一波，两个都排序后尽量相连。我一开始猜最多跨1，但其实最多跨2，考虑3个人的情况： 我们发现第3个人没了，所以可以出现跨2的情况 然后直接上dp，由 i−1,i−2,i−3i-1,i-2,i-3i−1,i−2,i−3 转移过来。 然后这显然可以拿矩阵表示。 然后显然可以拿线段树维护。 后面三部分都是比较套路...