标签:算法-贪心

题意给一个 $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$ 放上梅花,而且不同的顺序得到的答案也不相同。考虑...
题解 动态规划 动态规划-树形DP 算法-贪心
提高+/省选-
题意一棵 $n(\le 50000)$ 个点的树,有 $m(\le 50000)$ 支军队驻守在一些节点。要求根节点到每个叶子节点之间的路径上都有军队驻守,军队可以同时移动,每小时移动 $1$ 单位长度。问至少要多久才能满足条件,无解输出 -1(没有)。题解答案显然满足单调性,所以可以二分答案 $mid$ 。接下来只需要判断在 $mid$ 时间内能否满足条件。(1)如果军队 $i$ 在根节点...
题解 算法-二分/三分 算法-贪心 算法-倍增
省选/NOI-
题意环上有 $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...
题解 算法-贪心 算法-倍增
省选/NOI-
题意自己去看吧太长了我懒得总结了题解可以发现,对一段路使用了加速器,那么在区间终点下车的乘客旅行时间都会 $-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)$ 把全部扫一遍,就想到用优先队列来优化。不过问题也是显然的,每次合并我们都会删除当前点并改变父节点的值,但之前父节点肯定也已经放进了队列,而优先队列显然不能满足直接修改的条件。但仔细一想,每...
题解 算法-贪心
省选/NOI-
徐妈让我们做一本通的题,说是巩固基础。但说实话这里面的题又烂又水,就连第一章11道题就有双倍经验我也是无语的。这一章完成时间:两天(其实就是一个晚自习1h+两个中午40min),而且还包括颓废时间10000.活动安排贪心区间覆盖经典模型。按照右端点排序,然后依次判断能不能放即可。struct Edge{ int s,f; } edge[1005]; int n,ans; inlin...
题解 算法-贪心 题目-一本通
标签
其它-Firefox1 其它-pbds1 其它-pjax1 其它-Ubuntu1 其它-VSCode1 其它-网易云音乐1 动态规划52 动态规划-区间DP9 动态规划-单调队列优化DP5 动态规划-图上DP1 动态规划-斜率优化DP5 动态规划-树形DP16 动态规划-状压DP16 动态规划-线性DP10 动态规划-背包DP3 图论4 图论-LCA4 图论-Tarjan11 图论-二分图1 图论-割点3 图论-基环树1 图论-差分约束4 图论-强连通分量2 图论-最小环1 图论-最小生成树6 图论-最短/最长路19 图论-树上差分2 图论-树的直径4 图论-桥1 图论-缩点5 图论-负环4 字符串3 字符串-kmp2 思维题3 数学26 数学-bsgs2 数学-exgcd4 数学-gcd2 数学-中国剩余定理2 数学-卡特兰数1 数学-卢卡斯定理4 数学-快速幂4 数学-扩展中国剩余定理1 数学-扩展卢卡斯定理3 数学-矩阵5 数学-约数1 数学-组合数3 数学-质数1 数据结构-动态开点线段树1 数据结构-单调栈1 数据结构-单调队列2 数据结构-可持久化字典树2 数据结构-堆4 数据结构-字典树2 数据结构-并查集2 数据结构-栈1 数据结构-树状数组6 数据结构-树链剖分10 数据结构-线段树5 数据结构-队列1 比赛-Codeforces21 比赛-JX Round1 比赛-NOIp/CSP5 算法-KM算法1 算法-二分/三分12 算法-位运算1 算法-倍增4 算法-分块2 算法-分治3 算法-哈希2 算法-多叉树转二叉树2 算法-差分4 算法-悬线法1 算法-拓扑排序2 算法-排序3 算法-搜索21 算法-模拟5 算法-状态压缩4 算法-贪心10 算法-高精度3 问题-逆序对2 题目-一本通5 题目-网络流24题2