标签 堆 下的文章
- 首页
- 堆
SPOJ QTREE 系列简要题解
QTREE1把 $(fa_i,i)$ 的边权作为 $i$ 的点权，然后就是个树剖板子了...但是注意查询时 LCA 是不能查的，需要判一下。而且这题竟然不能交 C++ ，然后我改了半个小时才把 C++ 改成 C QAQQTREE2DIST 操作只需要维护树上前缀和即可求出答案。KTH 操作大力...
洛谷2056 [ZJOI2007]捉迷藏
Luogu分析首先吐槽一句...当初写《幻想乡战略游戏》的时候抄了个错的 ST 表求 LCA 的板子，那题竟然还过了...然后我蒯过来出现各种问题，害我调了好久 QAQ看到这个毒瘤的时限以及修改操作可以想到动态点分治。对于每个节点 $u$ 维护两个堆：一个堆维护点分子树中所有关灯的点到 $u$...
Codeforces Global Round 2 题解
orz GM Itst比赛地址Ilya and a Colorful Walk显然最优解要么是从 $1$ 走到某个地方，要么是从 $n$ 走到某个地方。直接 $O(n)$ 扫一遍即可。代码Alyona and a Narrow Fridge枚举答案 $x$ ，然后判断。判断的话，把前 $x$ ...
洛谷5283 [十二省联考2019]异或粽子
LuoguBZOJLOJ分析我们先来看一道比这题难的题目：NOI2010 超级钢琴。如果不会做这题，下面是题解链接：然后发现这题跟超级钢琴相比，就只是限定 $L=1,R=n$ ，然后把和换成了异或和。那么相应的把主席树换成可持久化 Trie 树就行了，其它地方不怎么需要改。具体实现及细节见代码...
洛谷2048 [NOI2010]超级钢琴
LuoguBZOJ分析堆+主席树。考虑对于每个左端点 $l$ ，先找到一个 $r$ 使得 $\sum\limits_{i=l}^ra[i]$ 最大。设 $s[i]=\sum\limits_{j=1}^i a[i]$ ，也就是说要找到一个 $r$ 使得 $sum[r]-sum[l-1]$ 最大。...
洛谷4404 [JSOI2010]缓存交换
LuoguBZOJ分析贪心。如果 $\mathrm{cache}$ 没有满，那么直接丢进去即可。如果满了的话，考虑丢掉哪个。显然丢到下一次出现最靠后的那个是最优的。用一个堆来维护目前所有 $\mathrm{cache}$ 中的数据上一个出现位置。因为需要删除，所以可以在 $\mathrm{pr...
洛谷5290 [十二省联考2019]春节十二响
LuoguBZOJ分析先考虑一条链的情况怎么做。显然 $1$ 最多会有两条支链，那么两条支链排序后对应相加即可。正确性显然。考虑把这个东西扩展到树上。每个节点维护一个堆，然后向上启发式合并即可。时间复杂度为 $O(n\log n)$ 。代码// ========================...
洛谷4064 [JXOI2017]加法
LuoguBZOJ分析第一眼想到二分答案。 然后我就不会了首先以 $l$ 为第一关键字、$r$ 为第二关键字将所有区间排序。假设现在二分出了一个答案 $mid$ 。贪心地想，我们只会在不得不给一个区间加上 $a$ 时给它加上 $a$ 。于是从左到右扫，如果一个点没有达到 $mid$ 的话，那么...
洛谷4437 [HNOI2018]排列
LuoguBZOJ分析首先，如果 $a[j]=k$ ，那么 $k$ 一定在 $j$ 的前面。考虑从 $a[j]$ 向 $j$ 连边，构成一个图。显然，如果有环的话是无解的，那么现在就是，如果要选子节点，必须要先选父节点。$i$ 节点第 $T$ 个选出来的话，贡献是 $Tw[i]$ 。考虑贪心。...
洛谷3243 [HNOI2015]菜肴制作
LuoguBZOJ分析$25\mathrm{min}$切了此题qwq一开始我觉得，显然可以用拓扑排序来做，只要求字典序最小的拓扑序列就行了。然后$\color{red}{\mathrm{WA\ on\ \#Example\ 3}}$于是冷静分析一波，发现要求的其实是字典序最大的倒序的拓扑序列。...