哈夫曼树/合并果子中具有的单调性：牛客65157/F
哈夫曼树/合并果子中具有的单调性：牛客65157/F
本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132912243
正常哈夫曼树实现是用优先队列的
但是我们发现新建的节点大小满足单调性
那么我们就可以直接拿个队列来维护
但是一开始的节点和新的节点会混在一起
那就拿两个队列维护呗
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 zhangxixi的博客！
相关推荐
2026-10-05
整除分块 + 哈夫曼树优化：CCPC2026网络赛L
整除分块 + 哈夫曼树优化：CCPC2026网络赛L Logging Compression - Problem - QOJ.ac 这题其实就是让你实现哈夫曼树。 我们首先考虑压缩信息。如果一段区间每个数出现是相同的，我们就可以合并来存储他们。那样子在优先队列里我们记两个值：当前值 sss + 有多少个数是这样的 nnn。 我们考虑我们在小根堆里取出来的第一个东西，其 n≥2n\ge 2n≥2，那样子其实本质上有 $\lfloor\dfrac n 2\rfloor $ 对自己和自己合并。那我们直接把 (2s,⌊n2⌋)(2s,\lfloor\dfrac n 2\rfloor )(2s,⌊...
2023-09-27
贪心+二分+DP+矩阵快速幂：CF461E
贪心+二分+DP+矩阵快速幂：CF461E 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133316261 https://codeforces.com/contest/461/problem/E 第一步：捕捉题目信息 四种字符 →\to→ 矩阵 n≤1018→n\le 10^{18}\ton≤1018→ 矩阵快速幂 →\to→ dp 最小值最大 →\to→ 二分 第二步：分析性质 sss 未知？那如果已知怎么做，肯定是每次暴力选最长的。 ...
2023-12-25
网络流+先跑一遍确保正确性：ARC156F
网络流+先跑一遍确保正确性：ARC156F 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135209595 https://www.luogu.com.cn/problem/AT_arc156_f 可以很显然建一个流： 然而它最大流是对的，但构造方案可能会假，因为存在最左边的边没流，相当于某个数没选。 一定有解是怎样？全选 aia_iai ，所以我们可以先全选 aia_iai 跑。然后我们再加入 bi,cib_i,c_ibi,ci 来跑，那样反悔...
2022-05-13
【一本通 1488：新的开始】题解
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/16267581.html 题目链接 题目 发展采矿业当然首先得有矿井，小 FF 花了上次探险获得的千分之一的财富请人在岛上挖了 nnn 口矿井，但他似乎忘记考虑的矿井供电问题…… 为了保证电力的供应，小 FF 想到了两种办法： 在这一口矿井上建立一个发电站，费用为 vvv（发电站的输出功率可以供给任意多个矿井）。 将这口矿井与另外的已经有电力供应的矿井之间建立电网，费用为 ppp。 小 FF 希望身为「NewBe_One」计划首席工程师的你帮他想...
2023-10-03
抓住普通情况变量猜结论：ARC136C
抓住普通情况变量猜结论：ARC136C 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133525236 假如不是环，我们求的就是上升的量。那么我们可以先大胆猜一波，环形结果就是上升的量。 然而我们在非环的情况是在前面补了0的，我们这里不能补0，我们就只能对最大值取max 1234n=read(); for(i=0; i<n; ++i) a[i]=read(), m=max(m, a[i]); for(i=0; i<n; ++i) k+=max(...
2021-12-04
【Loj #10008. 「一本通 1.1 练习 4」家庭作业】题解
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15643572.html 题目链接 题目 老师在开学第一天就把所有作业都布置了，每个作业如果在规定的时间内交上来的话才有学分。每个作业的截止日期和学分可能是不同的。例如如果一个作业学分为 101010，要求在 666 天内交，那么要想拿到这 101010 学分，就必须在第 666 天结束前交。 每个作业的完成时间都是只有一天。例如，假设有 7 次作业的学分和完成时间如下： 作业号 期限 学分 111 111 666 222 111 7...