coder-River
coder-River
全部文章
题解
归纳(12)
归档
标签
去牛客网
登录
/
注册
River的博客
万物皆可Restart~
全部文章
/ 题解
(共82篇)
Uva 1615 让人头大的区间问题之 区间选点问题
来自专栏
一、题意 给一个x轴的一段长度[0, L]代表一条公路,然后给出n个点的坐标(xi, yi),要你在公路上选出尽量少的点,使得对于给定的每个点,都有一个选出的点离它的欧几里得距离不超过D。 二、解析 以每个给定的点为圆心,D为半径可以画出n个⚪,这些⚪和公路会相交并得到对应的割线。这些割线就是本题中...
2020-08-27
0
505
UvaLive 6606 让人头大的区间问题之 区间不相交问题
来自专栏
一、题意 有一个会议室,同一时间只能用来开一次会。输入若干会议时间区间,输出这个会议室最多能安排多少场会议。 二、解析 经典的区间不相交问题。由贪心思想:我们希望选出一个区间后,能留下来更长一些的时间长度(这样才有可能选出更多的区间),因此我们按照时间区间的结束点进行从小到大排序,总是先选取最先完成...
2020-08-27
0
393
Uva 108 超经典!!最大连续子数列和与最大子矩形和
来自专栏
一、题意 输出n,然后输入一个n*n(n<=100)的数字矩形,要求你找出这个矩形中数字和最大的子矩形。输出这个子矩形的数字和。 二、解析 先来回顾一下一维的最大连续子数列和问题:在一个长度为n的数列a[1...n]中,找到数字和最大的子序列。在一维情形我们有4种方法: 方法一:暴力枚举,枚...
2020-08-27
0
766
Uva 12558 一套有用的组合技:迭代+深搜索
来自专栏
一、题意 埃及分数问题。给一个分数a/b。将它拆成式子:a/b=1/c1+1/c2+1/c3...其中c1,c2,c3,...严格递增,且尽可能使得项数最少,在此前提下最大的c值最小。输出式子。 二、解析 一般来说枚举题理论上可以用回溯法解决,但是在这题中,我们可以发现回溯法每一层的枚举数量为无限....
2020-08-27
0
616
Uva 10085 八数码的3种状态表示方法
来自专栏
一、题意 这是一个八数码问题的变种。输入九宫格的初始状态,九宫格的数字为0...8,其中0代表为空位,其余数字代表由相应数字的板块在那个位置上。然后对九宫格里的板块进行移动,直到变成一个最终状态。要求输出变成的最远的状态,即操作次数最多的状态。打印出这个最终状态,同时用“UDLR”输出空位的移动路径...
2020-08-26
0
638
Uva 10603 这是一道(倒)水题
来自专栏
一、题意 每组数据给出a,b,c,d四个值。a,b,c为三个杯子的容量,其中初始时前两个杯子为空,最后一个装满了水。d为目标水量。要求你在这三个杯子之间相互倒水,每次倒水要么源杯倒空,要么把目标杯倒满,不能把水倒掉。求最少的总倒水量,使得最终至少有一个杯子的水量最接近d。输出这个最少的总倒水量以及最...
2020-08-26
0
507
Uva 129 困难串好难啊
来自专栏
一、题意 如果一个字符串包含两个相邻的重复子串,则称它为容易的串。输入k和L, 要求输出由前L个字母组成的、字典序第k小的困难的串。 二、解析 通过回溯法按字典序枚举字符串,每次枚举都对应这当前字符串的最后一个字符。因此判断是否是困难的串时,就可以只判断当前字符串的后缀有没有出现相邻的重复子串即可。...
2020-08-26
0
452
Uva 524 回溯大法好
来自专栏
一、题意 每组数据给一个n。要求你输出所有1...n的从1开始的排列,每个排列满足相邻两个(包括首尾两个)之和为素数。输出顺序按字典序。 二、解析 看到这题第一反应是枚举全排列,事实证明那样会超时。紫薯告诉我们,回溯法总是比生成-测试法快得多。因此我们考虑用回溯的思想。需要一个递归深度值idx表示当...
2020-08-26
0
469
Uva 167 看到这个经典题,我的青春回来了...
来自专栏
一、题意 有若干组数据。每组数据给一个8*8棋盘,棋盘上每个位置上有一个数字,要求你找出一个八皇后摆法,使得八皇后位置上的数字之和最大。输出这个最大值。 二、解析 经典的八皇后问题,做了一些小修改。但其实还是八皇后问题。枚举出所有摆法然后维护出最大值即可。 三、代码 #include <ios...
2020-08-26
0
532
Uva 10976 暴力枚举来试试?
来自专栏
一、题意 输入正整数k,找到所有的正整数x>=y,使得 1/k = 1/x + 1/y。并打印出来。 二、解析 暴力枚举法。关键是缩小枚举范围。首先显然 k<x<=y,另一方面 y<=2k<=x。因此可以发现y的范围是(k, 2k],因此选择枚举y,时间复杂度仅为O(n...
2020-08-26
0
362
首页
上一页
1
2
3
4
5
6
7
8
9
下一页
末页