coder-River
coder-River
全部文章
题解
归纳(12)
归档
标签
去牛客网
登录
/
注册
River的博客
万物皆可Restart~
全部文章
/ 题解
(共82篇)
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
550
Uva 1152 进来学学中途相遇法
来自专栏
一、题意 给定4个n元素(1<=n<=4000)的集合A,B,C,D,要求分别从中选取一个元素a,b,c,d,使得a+b+c+d=0。问有多少种取法。 二、解析 直接4重循环暴力肯定超时。回想若只有两个集合时,我们会通过map来存储其中一个集合A的值,然后遍历另外一个集合B来从map中询...
2020-08-28
0
383
Uva 10020 让人头大的区间问题 之 区间覆盖问题
来自专栏
一、题意 输入M以及若干区间[xi, yi),要求你从中取出最少的区间,使得这些区间能覆盖[0, M)。输出最少的数量,以及选出的区间。 二、解析 经典的区间覆盖问题。用贪心的思想。将所有区间按照左端点从小到大排列。用cur表示当前的“截取点”,在截取点之前的长度是毫无意义的。比如,在初始状态时由于...
2020-08-28
0
677
首页
上一页
1
2
3
4
5
6
7
8
9
下一页
末页