coder-River
coder-River
全部文章
分类
归纳(12)
题解(82)
归档
标签
去牛客网
登录
/
注册
River的博客
万物皆可Restart~
TA的专栏
98篇文章
0人订阅
Re:从零开始的刷题生活
85篇文章
858人学习
Re:从零开始的归纳时间
13篇文章
1066人学习
全部文章
(共94篇)
Uva 1617 有时候题目可能没有你想得那么复杂...
来自专栏
一、题意 给你n条线段(线段端点为整数,n<=100000),输入保证线段间没有包含关系,且保证有解。现在要求将每条线段截取长度为1的一小段,使得截取后的所有线段之间的空隙数目最少。输出空隙的最少数目。 二、解析 一开始用了一种比较复杂的方法:将所有线段按右端点排序后,每个线段尽量靠左边选取...
2020-09-01
0
446
Uva 1616 这道题要求输出分数解?我不管,先求个小数解出来
来自专栏
一、题意 输入n条线段,线段之间没有包含关系,要求你把每条线段截成原来的一条子线段,使得改变之后的所有线段长度相等且互不相交(端点可以重合)。求每条线段的最大长度,并用分数表示。 二、解析 刚看到要用分数表示时,我是很懵的,但后来仔细一想,其实这只是出题人的虚晃一枪,我们首先求出小数解,然后再转变为...
2020-09-01
0
502
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
436
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
416
Uva 1149 进来涨涨自信:贪心问题入门题
来自专栏
一、题意 给定n个物品的大小a[maxn],每个背包的容量M,并且每个背包最多只能装2个物品。输出装下所有物品至少需要的背包数目。 二、解析 一看就是典型的乘船问题(贪心问题中的一种)。 由于只能装2个物品,因此我们首先将物品按大小排序,然后通过双指针指向一头一尾。头指针指向的是当前最小的物品,我们...
2020-08-31
0
365
Uva 12265 复杂的单调栈 之 求最大矩形周长
来自专栏
一、题意 输入一个n*m的矩阵,'.'表示空地,'#'表示障碍物,要求你对于每一个空地,求出以它为右下角的空矩形的最大周长。然后统计每个周长出现了多少次。 二、解析 看到题意,应该就能回想到一些之前做过的题目:找最大空矩形面积。而这道题要找的是最大周长。其实是异曲同工的,也就是先将原图转化为n个直方...
2020-08-31
0
581
首页
上一页
1
2
3
4
5
6
7
8
9
10
下一页
末页