标签:算法-贪心

题意一棵 $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 动态规划49 动态规划-区间DP9 动态规划-单调队列优化DP5 动态规划-图上DP1 动态规划-斜率优化DP5 动态规划-树形DP14 动态规划-状压DP16 动态规划-线性DP10 动态规划-背包DP2 图论4 图论-LCA3 图论-Tarjan9 图论-二分图1 图论-割点3 图论-基环树1 图论-差分约束3 图论-强连通分量1 图论-最小环1 图论-最小生成树6 图论-最短/最长路17 图论-树上差分2 图论-桥1 图论-缩点4 图论-负环3 字符串3 字符串-kmp2 思维题3 数学25 数学-bsgs2 数学-exgcd4 数学-gcd2 数学-中国剩余定理2 数学-卡特兰数1 数学-卢卡斯定理4 数学-快速幂4 数学-扩展中国剩余定理1 数学-扩展卢卡斯定理3 数学-矩阵5 数学-约数1 数学-组合数3 数学-质数1 数据结构-动态开点线段树1 数据结构-单调栈1 数据结构-单调队列2 数据结构-可持久化字典树2 数据结构-堆4 数据结构-字典树2 数据结构-栈1 数据结构-树状数组3 数据结构-树链剖分10 数据结构-线段树3 数据结构-队列1 比赛-Codeforces17 比赛-JX Round1 比赛-NOIp/CSP4 算法-二分/三分11 算法-位运算1 算法-倍增4 算法-分块2 算法-分治3 算法-哈希1 算法-多叉树转二叉树2 算法-差分3 算法-悬线法1 算法-拓扑排序1 算法-排序3 算法-搜索20 算法-模拟5 算法-状态压缩4 算法-贪心8 算法-高精度3 问题-逆序对2 题目-一本通5 题目-网络流24题2