coder-River
coder-River
全部文章
分类
归纳(12)
题解(82)
归档
标签
去牛客网
登录
/
注册
River的博客
万物皆可Restart~
TA的专栏
98篇文章
0人订阅
Re:从零开始的刷题生活
85篇文章
858人学习
Re:从零开始的归纳时间
13篇文章
1066人学习
全部文章
(共94篇)
HDU 1506 超经典!! 通过单调栈在直方图中找最大矩形
来自专栏
一、题意 每组数据中输入一个宽度为n的平面直方图。要求你输出直方图中面积最大的矩形的面积。 二、解析 超经典的直方图中求最大矩形问题。从0开始从左向右遍历直方图,并维护一个单调栈。单调栈里存放到当前位置为止的一个单调递增的直方图高度,栈里实际存放的是下标。这样就可以在O(1)时间获取离当前位置最近的...
2020-08-30
0
399
Uva 1442 超经典!水位问题,山洞里能装多少水?
来自专栏
一、题意 一个山洞的宽度由n个片段构成,每个片段有个地面高度floor[maxn]和天花板高度ceil[maxn]。现在往里面装水,要求各个地方的水位不能淹没天花板,求最多能装多少水。(山洞两侧为无限高的墙壁) 二、解析 这是一道超经典的水位问题。以前在leetcode上做过一道简化版:即没有天花板...
2020-08-30
0
442
Uva 1608 这是一道很不无聊的题目,也就用了分治法+中途相遇法
来自专栏
一、题意 如果一个序列的任意连续子序列中至少有一个只出现一次的元素,则称这个序列是non-boring的。输入一个长度为n的正整数序列(n<=200000),判断它是否是boring的。 二、解析 首先一起来学学语文:“任意连续子序列中至少有一个只出现一次的元素”.这句话的反命题为:存在一个连...
2020-08-29
0
643
Uva 12174 一个稍微复杂的滑动窗口问题
来自专栏
一、题意 每组数据输入一个s和一个n,s表示歌曲的数目,n表示歌曲乱序循环播放列表的长度,然后输入一个数组a[maxn]表示该播放列表。要求统计乱序播放列表的的开头位置有多少种可能性。 二、解析 一个位置如果是乱序循环播放列表的开头,那么从它开始的后s首歌曲一定互不相同,再后s首也是互不相同.......
2020-08-29
0
502
Uva 11093 关于在加油站加油就是为了能跑到下一个加油站加油的这件事
来自专栏
一、题意 环形跑道上有n个加油站(n<=100000),编号1-n,第i个加油站可以加油p[i]加仑,从它开到下一个加油站需要q[i]加仑,要求你选择一个加油站作为起点,然后跑一圈回到起点,要求作为起点的加油站编号尽可能小。无解则输出 Not Possible。有解则输出起点的加油站编号。 二...
2020-08-29
0
352
Uva 714 二分答案乱杀最大最小值与最小最大值问题
来自专栏
一、题意 输入包含若干组数据。每组数据输入一个n, k。然后输入一个长度为n的序列。要求你把这个序列划分为k段,记每一段的数字和为S(i),要求使得S(i)的最大值尽可能地小。输出划分结果。若有多解,则使前面的段尽可能地短。 二、解析 看到“最大值尽可能小”这种字眼,第一下就应该反应出可能要使用二分...
2020-08-29
0
579
Uva 1619 巧妙的单调栈
来自专栏
一、题意 给出一个长度为n(n<=100000)的正整数序列ai,求出一段连续子序列a[l..r]使得 (al+...+ar)*min{al,...,ar}尽量大。输出最大值和对应的区间。当区间相同时,输出最短的区间,长度相同时输出左端点最小的区间。 二、解析 区间和是很容易得到的,通过预先算...
2020-08-28
0
429
Uva 11572 进来学习滑动窗口法,听起来就很厉害呢
来自专栏
一、题意 输入一个长度为n的序列A(n<=1000000),找到一个尽量长的连续子序列,使得序列中没有相同的元素。 二、解析 使用双指针法。或者叫滑动窗口法。维护一个没有重复元素的窗口,即用i,j分别指向序列中当前窗口的头和尾,为了防止混乱,规定为A[i,j)。然后还需要一个vis数组表示元素...
2020-08-28
0
451
Uva 11054 今天我和村长说,我拿着-x千克的酒卖到了邻村
来自专栏
一、题意 直线上有n个等距的村庄(n<=100000),每个村庄要么买酒,要么卖酒。设第i个村庄的需求为ai,ai>0表示买酒,ai<0表示卖酒,sum(ai)=0。若把x数量的就从一个村庄运到隔壁村庄需要x人力,求总共需要多少人力完成所有买卖。 二、解析 这是一道很有意思的题目。...
2020-08-28
0
379
Uva 11134 让人头大的区间问题 之 区间限制问题
来自专栏
一、题意 要求在n*n的棋盘上放n个车(n<=5000),使得任意两个车不相互攻击,且第i个车在一个给定的矩形里。输入n,然后是n个车对应的矩形范围(xl, yl),(xr,yr),分别表示矩形的左上角和右下角。若无解输出IMPOSSIBLE,有解则依次输出每个车的坐标。多解时输出任意解即可。...
2020-08-28
0
551
首页
上一页
1
2
3
4
5
6
7
8
9
10
下一页
末页