哈夫曼树/合并果子中具有的单调性：牛客65157/F
哈夫曼树/合并果子中具有的单调性：牛客65157/F
本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132912243
正常哈夫曼树实现是用优先队列的
但是我们发现新建的节点大小满足单调性
那么我们就可以直接拿个队列来维护
但是一开始的节点和新的节点会混在一起
那就拿两个队列维护呗
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 zhangxixi的博客！
相关推荐
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...
2021-12-04
【Loj #10007. 「一本通 1.1 练习 3」线段】题解
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15643524.html 题目链接 题目 数轴上有 nnn 条线段，选取其中 kkk 条线段使得这 kkk 条线段两两没有重合部分，问 kkk 最大为多少。 思路 按右端点排序，贪心选可行的最左右端点。 由于右端点最小可以保证为后面留出更多空间。 Code 12345678910111213141516171819202122232425262728293031323334353637383940414243// Problem: #10007....
2021-11-14
【洛谷P2134 百日旅行】 题解
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15552404.html 题目描述 小明和小红还剩下N天的假期，小明可以安排旅行的计划。如果连续X天旅游，小明需要花旅行费用PXX元；如果连续X天不旅游，小明需要请小红吃饭，花费为Q*X元。（P,Q都是输入的常数） 请你帮小明写一个程序，计算出假期里他至少需要花费多少元。 只会贪心做法… 首先可以明确一点，在天数相同的情况下，吃饭天数连不连续不重要，旅行天数能分开就分开。 于是我们可以直接枚举吃饭天数 iii，剩下的 n−in-in−i 天旅游...
2022-04-25
【GDOI2022PJD2T4 机器人】题解
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/16191401.html D2T4 机器人 题目 刚上初一的小纯特别喜欢机器人，这周末，她报名了学校的“小机器人俱乐部”，而进入俱乐部需要通过一场考试。 考试场地可以看作一个 n×mn \times mn×m 的网格图，行从上往下标号为 1,…,n1, \dots, n1,…,n，列从左往右标号为 1,…,m1, \dots , m1,…,m。每个格子有三种可能：空地，障碍物，机器人（有且只有一个），分别用“.”、“*”、“R”表示。现在小纯需要...
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 转移过来。 然后这显然可以拿矩阵表示。 然后显然可以拿线段树维护。 后面三部分都是比较套路...
2023-10-05
长剖与贪心+树上反悔贪心：1004T4
长剖与贪心+树上反悔贪心：1004T4 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133575747 长剖的本质是一种贪心。（启发式合并本质也是类似哈夫曼树的过程） 在此题中，首先肯定变直径，然后选端点为根。然后选叶子。而每个叶子为了不重复计算，可以只计算其长剖后所在链的贡献。（本题精髓，用长剖来贪心） 然后钦定某个点必选，就是一种反悔贪心。很显然的思路是删掉排名 2∗k−12*k-12∗k−1 的叶子，但考虑： 所以需要考虑离其最近被选的点 1234...