标签:算法-贪心

题意在长度为 $N$ 的数列中选择不超过 $M$ 段连续的数,求这些数总和的最大值。$N,M\le 10000$ 。题解可以先将连续的相同符号的数合并起来,并忽略 $0$ 。因为取正数时一定会把一整段取完,取负数也肯定会把自己这段和两边的正数段取完。这样得到的新序列是正负交替的,下面处理新数列。先贪心的把所有正数取完,并记正数的个数为 $cnt$ 。如果 $cnt\le m$ ,那么此时就已...
题解 算法-贪心 数据结构-堆
题意在 $[0,m]$ 中选一个数,使得它经过给定的 $n$ 个 &、|、^ 操作后得到的数最大。$2\le m\le 10^{9} \ , \ 2\le n\le 10^{5}$ 。题解所有数都 $\le 2^{30}$ ,而且修改都只涉及二进制的修改,所以对每一位进行贪心。用 $s_0$ 代表最初全为 $0$ 的数在操作后每一位的值;用 $s_1$ 代表最初全为 $1$ 的数在操...
题解 算法-贪心
提高+/省选-
洛谷博客: https://www.luogu.org/blog/llf/solution-uva1205贪心策略和其他题解一样,选取最大的点和它的父节点合并。只是我看其它题解每次找最大都是 $O(n)$ 把全部扫一遍,就想到用优先队列来优化。不过问题也是显然的,每次合并我们都会删除当前点并改变父节点的值,但之前父节点肯定也已经放进了队列,而优先队列显然不能满足直接修改的条件。但仔细一想,每...
题解 算法-贪心
省选/NOI-
徐妈让我们做一本通的题,说是巩固基础。但说实话这里面的题又烂又水,就连第一章11道题就有双倍经验我也是无语的。这一章完成时间:两天(其实就是一个晚自习1h+两个中午40min),而且还包括颓废时间10000.活动安排贪心区间覆盖经典模型。按照右端点排序,然后依次判断能不能放即可。struct Edge{ int s,f; } edge[1005]; int n,ans; inlin...
题解 算法-贪心 题目-一本通