题意给一个 $n(\le 5\times 10^5)$ 点 $m(\le 5\times 10^5)$ 边的有向无环图，求一个拓扑序满足拓扑序的前缀最大值最少/最多。题解最大的情况比较容易想到，从当前能走的点中选编号最小的点即可，用堆维护。至于最小的情况，直接选最大的点拓展会喜提46分。很容易想到这种方法的问题所在，如果很小的一个点连着一个很大的点，把这两个都选了有可能最优。考虑对贪心进行优...
题意有一棵 $n(\le 100004)$ 个点的树，从根节点出发。节点 $x$ 能放梅花，仅当其所有子节点 $y$ 上都放了 $w_y$ 朵梅花。对于 $\forall i\in [1,n]$ ，如果要在 $i$ 上放 $w_i$ 朵梅花，则至少需要在过程中准备多少梅花？题解可以发现对于节点 $x$ ，一定是按某种顺序遍历所有子节点 $y$ 放上梅花，而且不同的顺序得到的答案也不相同。考虑...
题意一棵 $n(\le 50000)$ 个点的树，有 $m(\le 50000)$ 支军队驻守在一些节点。要求根节点到每个叶子节点之间的路径上都有军队驻守，军队可以同时移动，每小时移动 $1$ 单位长度。问至少要多久才能满足条件，无解输出 -1（没有）。题解答案显然满足单调性，所以可以二分答案 $mid$ 。接下来只需要判断在 $mid$ 时间内能否满足条件。(1)如果军队 $i$ 在根节点...
题意环上有 $m(\le 10^9)$ 个点，有 $n(\le 2\times 10^5)$ 个人可以从 $l_i\rightarrow r_i$ 。对于所有的 $i\in [1,n]$ ，询问如果第 $i$ 个人必须选且为起点，至少要选多少人才能绕完一圈。题解首先断环成链。容易想到贪心，每次选 $l_i\le $ 当前的 $r$ ，$r_i$ 最大的 $i$ 作为下一步。一步一步跳是 $O...
题意自己去看吧太长了我懒得总结了题解可以发现，对一段路使用了加速器，那么在区间终点下车的乘客旅行时间都会 $-1$ 。所以可以预处理出每个点下车的人数 $q[i]$ 。预处理出最开始每个点的到达时间 $arr[i]$ 和 每个点最后到达的旅客时间 $last[i]$ 。如果使用加速器后能让下一段路的起点 $i$ 提前开车，即满足 $arr[i]-1<last[i]$ ，那么在下一段路的...
题意有 $n(\le 150000)$ 个建筑需要修复，每个建筑有修复耗时 $t1$ 以及修复完成的截止时间 $t2$ ，问最多能修复多少个建筑。题解贪心。先把所有建筑按照截止时间排序，然后依次处理各个建筑。如果当前建筑还能修就修，否则就从之前修过的建筑里找到耗时最多的，如果比当前建筑的耗时多就替换掉。需要用堆维护。#include<bits/stdc++.h>
using n...
题意在长度为 $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)$ 把全部扫一遍，就想到用优先队列来优化。不过问题也是显然的，每次合并我们都会删除当前点并改变父节点的值，但之前父节点肯定也已经放进了队列，而优先队列显然不能满足直接修改的条件。但仔细一想，每...
徐妈让我们做一本通的题，说是巩固基础。但说实话这里面的题又烂又水，就连第一章11道题就有双倍经验我也是无语的。这一章完成时间：两天（其实就是一个晚自习1h+两个中午40min），而且还包括颓废时间10000.活动安排贪心区间覆盖经典模型。按照右端点排序，然后依次判断能不能放即可。struct Edge{
int s,f;
} edge[1005];
int n,ans;
inlin...