哈夫曼树/合并果子中具有的单调性：牛客65157/F
哈夫曼树/合并果子中具有的单调性：牛客65157/F
本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132912243
正常哈夫曼树实现是用优先队列的
但是我们发现新建的节点大小满足单调性
那么我们就可以直接拿个队列来维护
但是一开始的节点和新的节点会混在一起
那就拿两个队列维护呗
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 zhangxixi的博客！
相关推荐
2023-10-06
打表找规律与分析判断：ARC144C
打表找规律与分析判断：ARC144C 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133607035 https://atcoder.jp/contests/arc144/tasks/arc144_c?lang=en 一开始我猜的结论是前后 kkk 个预处理，中间贪心。 通过打表： 可以发现是前面 2k2k2k 连续块直接暴配，最后一段再用我想的贪心。 究其原因，其实是我们本质上代表着只要大于 2k+12k+12k+1 就必然有解。所以这样构造必然是对的...
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 位置有向上的话，我们贪心希望它和 ...
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-12-02
贪心+计数：CF1612G
贪心+计数：CF1612G 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/134747631 https://www.luogu.com.cn/problem/CF1612G 贪心考虑如何放最优。 假设当前出现次数最多为 iii ，有 kkk 个这样的数，打表可得左边 kkk 个随便放，右边 kkk 个随便放，然后递归下去即可，当前层方案数为 (k!)2(k!)^2(k!)2 。 在这个过程中顺便维护最大值即可。 123456789101112 m=read...
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...