标签:数据结构-堆

题意在长度为 $N$ 的数列中选择不超过 $M$ 段连续的数,求这些数总和的最大值。$N,M\le 10000$ 。题解可以先将连续的相同符号的数合并起来,并忽略 $0$ 。因为取正数时一定会把一整段取完,取负数也肯定会把自己这段和两边的正数段取完。这样得到的新序列是正负交替的,下面处理新数列。先贪心的把所有正数取完,并记正数的个数为 $cnt$ 。如果 $cnt\le m$ ,那么此时就已...
题解 算法-贪心 数据结构-堆
题意要求维护一个序列,可以动态插入和查询第 $k$ 大。命令总数 $\le 30000$ 。题解用两个堆维护,大根堆大小为 $k-1$ ,其余放入小根堆。插入操作时,先插入大根堆,然后取堆顶放入小根堆。查询操作时,答案就是小根堆顶,并将答案放入大根堆。#include<bits/stdc++.h> using namespace std; inline int read() ...
题解 数据结构-堆
提高+/省选-
题意用 $K$ 进制串 $S_i$ 表示 $N$ 个不同的单词。每个单词出现了 $W_i$ 次,不存在某个进制串是另一个的字串。求处理后全文的最短长度,以及此情况下最长 $S_i$ 的最短长度。题解编码方式显然是一棵 $K$ 叉哈夫曼树,先补 $0$ 直到 $(N-1)\equiv 0\pmod {(K-1)}$ ,然后每次选 $K$ 个点合并成一个点直到只剩 $1$ 个点即可。要求最长的 ...
题解 数据结构-堆
提高+/省选-
四倍经验(1蓝2紫1黑):P3620,SP1553,P1484,P1792题意将 $N$ 个办公楼两两配成 $K$ 对,要求这 $K\times 2$ 栋楼相异。所有办公楼在一条直线上,配对的两栋楼之间需要连接电缆,求电缆长度的最小值。$N\le 100000$ 。题解显然,配对相邻的两栋楼是最优的。将边看成点来考虑,题目即转化成:在 $N$ 个点中选 $K$ 个不相邻的点,使得点权最小。每...
题解 数据结构-堆
省选/NOI-