coder-River
coder-River
全部文章
题解
归纳(12)
归档
标签
去牛客网
登录
/
注册
River的博客
万物皆可Restart~
全部文章
/ 题解
(共82篇)
Uva 10570 原数组与pos数组的双交换
来自专栏
一、题意 输入1 ~ n 的一个排列(n<=500),每次可以交换两个整数,输出至少要用多少次交换,就可以把排列变成一个1 ~ n 的环状排列。 二、解析 由于n比较小,因此暴力模拟法即可。首先枚举目标排列,总共 2 * n 种(以每一个下标作为开头1、顺时针和逆时针),然后对于每一个目标排列...
2020-08-31
0
379
Uva 1153 任务安排问题上如何同时考虑ddl优先和短任务优先?
来自专栏
一、题意 有n个工作(n<=800000),只能串行进行,已知每个工作的用时need[i]和截止期限ddl[i],问最多能完成多少个工作? 二、解析 这个是超典型的工作安排贪心问题。 一个比较简单的版本是给出工作的确切开始时间和结束时间,这种问题就是典型的区间限制问题,我们按照ddl排序,然后...
2020-08-31
0
599
Uva 1613 染色问题 之 通过dfs进行结点的染色
来自专栏
一、题意 给出一个n个点m条边的连通图,每个点的度数不超过k(k为一个奇数),要求给每个点进行1...k的染色,使得相邻点颜色不同。 二、解析 首先按照题目的意思求出k,并且题目已经告诉我们k染色一定有解,因此接下来就是放心的dfs染色即可。需要维护一个col[maxn]数组,0表示没有染色。这个c...
2020-08-31
0
457
Uva 11419 遇黑则白,反向思考
来自专栏
一、题意 输入n、d(d<n<100000)。然后输入一个n位的数字,要求你从中删去d个,使得剩下的数字最大。 二、解析 先给出我一开始想的一种错误的思路:即每次都删去最小的、位置靠前的数字。这个乍看一下很有道理,但实际上是错误的,因为这个没有从全局考虑。比如一个231这个3位数字,只能...
2020-08-31
0
433
Uva 12545 能从0变成1却不能轻易地从1变回0
来自专栏
一、题意 输入两个等长的字符串S、T,你的任务是用最少的操作步数把S变成T。S由0、1、?构成,T由0、1构成。可用的操作有: 把一个0变成1 把一个?变成0或1 交换两个字符的位置输出最少步数。若没有办法则输出-1. 二、解析 这里的操作最关键的就是1如何变成0。我们用 x->y 表示x...
2020-08-31
0
464
Uva1610 利用暴力法避开细节处理
来自专栏
一、题意 给n个字符串(n<=1000,n为偶数),要你找一个最短的字符串S,使得恰好有一半的串小于等于S,另一半大于S。如有多解,输出字典序最小的解。 二、解析 第一步操作是显然的:排序这n个字符串,然后取出最中间的两个,假设为a,b。下面就是要少一个字符串res使得res>=a,re...
2020-08-31
0
415
Uva 1149 进来涨涨自信:贪心问题入门题
来自专栏
一、题意 给定n个物品的大小a[maxn],每个背包的容量M,并且每个背包最多只能装2个物品。输出装下所有物品至少需要的背包数目。 二、解析 一看就是典型的乘船问题(贪心问题中的一种)。 由于只能装2个物品,因此我们首先将物品按大小排序,然后通过双指针指向一头一尾。头指针指向的是当前最小的物品,我们...
2020-08-31
0
365
Uva 12265 复杂的单调栈 之 求最大矩形周长
来自专栏
一、题意 输入一个n*m的矩阵,'.'表示空地,'#'表示障碍物,要求你对于每一个空地,求出以它为右下角的空矩形的最大周长。然后统计每个周长出现了多少次。 二、解析 看到题意,应该就能回想到一些之前做过的题目:找最大空矩形面积。而这道题要找的是最大周长。其实是异曲同工的,也就是先将原图转化为n个直方...
2020-08-31
0
580
HDU 1506 超经典!! 通过单调栈在直方图中找最大矩形
来自专栏
一、题意 每组数据中输入一个宽度为n的平面直方图。要求你输出直方图中面积最大的矩形的面积。 二、解析 超经典的直方图中求最大矩形问题。从0开始从左向右遍历直方图,并维护一个单调栈。单调栈里存放到当前位置为止的一个单调递增的直方图高度,栈里实际存放的是下标。这样就可以在O(1)时间获取离当前位置最近的...
2020-08-30
0
398
Uva 1442 超经典!水位问题,山洞里能装多少水?
来自专栏
一、题意 一个山洞的宽度由n个片段构成,每个片段有个地面高度floor[maxn]和天花板高度ceil[maxn]。现在往里面装水,要求各个地方的水位不能淹没天花板,求最多能装多少水。(山洞两侧为无限高的墙壁) 二、解析 这是一道超经典的水位问题。以前在leetcode上做过一道简化版:即没有天花板...
2020-08-30
0
442
首页
上一页
1
2
3
4
5
6
7
8
9
下一页
末页