题目摘记.txt

HDOJ acm.hdu.edu.cn 第10卷的一些题目

1======
题目：Loan Scheduling
来源：HDOJ 1910
难度：简单
题型：贪心
小记：排序后扫描一遍
2======
题目：Highway
来源：HDOJ 1912
难度：简单
题型：最小圆形覆盖
小记：排序后，从左到右扫描，求出第一个点的x最大圆心，再和后面点的x最小圆心进行比较
3======
题目：Hardware
来源：HDOJ 1916
难度：简单
题型：字符串处理+死做
小记：
4======
题目：Frogger
来源：HDOJ 1918
难度：简单
题型：bfs
小记：状态hash[time%m][x][y]
5======
题目：Gallup
来源：HDOJ 1919
难度：中等
题型：穷举+精度测试
小记：精度卡的很死，穷举的时候按要求重新输出一遍，再和输入的比较
6======
题目：Jackpot
来源：HDOJ 1920
难度：简单
题型：最小公倍数
小记：
7======
题目：Exploding CPU
来源：HDOJ 1923
难度：中等
题型：不错的题
小记：筛法求素数，用A，B代入展开，确定A，B的上下限，枚举保存预处理，再扫描确定位置
8======
题目：Subway planning
来源：HDOJ 1922
难度：中等(ref)
题型：最小直线覆盖
小记：枚举从零点到各圆的最小角度和最大角度，标记哪些圆位于夹角范围内
9======
题目：Pie
来源：HDOJ 1969
难度：简单
题型：二分测试，浮点精度
小记：注意的就是上限应该是最大的一块pie的V，因为有些太小的pie可以被丢弃
10=====
题目：Printer Queue
来源：HDOJ 1972
难度：简单
题型：模拟
小记：
11=====
题目：Prime Path
来源：HDOJ 1973
难度：简单
题型：bfs
小记：
12=====
题目：The Bookcase
来源：HDOJ 1971
难度：难
题型：dp
小记：分出三段，要求书柜的面积最小。
	  排序后，Hmax是肯定会出现的，所以可以放置在第一层。
	  两层确定后，第三层可以被推算出来。
	  如果让三个书柜平分宽度，所得的贪心值，可以用来剪枝，也可以用这结论减少内存。
	  枚举每本书所放的位置，保存状态为[第一层W][第二层W].h1 = 第二层高度,[第一层W][第二层W].h2 = 第三层高度
	  时间复杂度为O(NW^2)，空间复杂度为O(W^2)