PDF《HDU 第11 版解题报告（农夫版）》

HDU 第11 版解题报告(农夫版) 农夫三拳(drizzlecrj@gmail.

com)

2000 ASCII码排序 题目大意:给定三个字母,按照 ASCII 码从小到大输出. 解题方法:三个字母排序,最简单的方法是进行三次比较,可以先判断 a 和b,再判断 a 和c,使得 a 是最小的数,然后比较 b 和c,将次小的放在 b 位置即可.当然使用任何一种你想使用的排序方法也 是可以的,包括直接插入排序,折半插入排序,链表插入排序,Shell 排序,冒泡排序,快速排序*, 直接选择排序,锦标赛排序,堆排序*,归并排序*,基数排序,桶排序,计数排序等.此外,还可以 选择使用 qsort 或者 std::sort.(*为需重点掌握算法) 联想:三个数使用基于比较的算法进行排序最少需要的比较次数是

3 次,那么

4 个数呢,5 个数呢,n 个数呢?4 个数的最少比较次数是

5 次,这个也许不难看出,但是

5 个数一般人只能想到

8 次(使用归 并的思想),实际上可以

7 次就完成.更多信息请参见《计算机程序设计艺术第三卷》5.3 节中的 极少 比较排序 一节. 经验谈:在输入数据范围很大(通常

105 或106 范围),且算法时间复杂度为 O(n)或者 O( nlogn )时,使用cin 往往会超时,这个时候记得要用 scanf,或者使用更快的 gets 和getchar 函数. 2001计算两点间的距离 题目大意:给出两个点的坐标,输出两点间的距离. 解题方法:对于两点(x1,y1),(x2,y2),距离公式为

2 2 )

2 1 ( )

2 1 ( y y x x ? + ? . 注意点:要注意题目中给的数是整数还是实数. 小知识:对于设置小数末尾的精度,有如下几种方法(以保留两位小数为例):C 当中我们使用 printf( %.2lf ,…) ;

C++当中我们可以使用 iostream 头文件中的 cout.setf( ios::fixed)以及 cout.precision(2) 来指定,还可以使用 iomanip 中setiosflags( ios::fixed)和setprecision(2)来指定. 2002计算球体积 题目大意:给定求的半径,求出求的体积. 解题方法:使用球的体积公式

3 3

4 R π . 注意点:平常 PI 我们都是取的 acos(-1.0),而这里题目中指定了 3.1415927,比赛的时候并没有指明, 003求绝对值 使得许多人 wa 了n次.

2 个实数的绝对值. . s 函数,需要注意的是浮点数中有-0 的存在,需要额外的判断为

0 题目大意:求一 解题方法:使用 cmath 中的 fabs 函数 注意点:可能有人会想到去自己实现 fab 的情况.浮点数的比较是一门很深的学问.可以参见Bruce Dawson的一篇文章Comparing floating point numbers.关于浮点数的一些更加具体的细节,请见我Blog上翻译的Representation of Integers and Reals Section I 和Section II. 2004成绩转换 一个成绩,按照题中的规则,输出对应的等级. 做判断. 题目大意:根据 解题方法:使用 if…else…if 或者 switch,可以先将成绩除以

10 再2005 第几天? 一个日期表示,输出它是该年的第几天. 400==0. 串,然后手动分解,使用 atoi ACM 竞赛试题了,问题是这样的,已只某年某月某日是星期几,要求计算 题目大意:给出 解题方法:使用闰年公式 year%4==0&

&

year%100!=0||year% 小知识:读取 1986/9/24 这样形式,有以下几种做法:1.读取整行字符 转换为整数;

2.直接用 cin 进行输入;

3.读入整行,使用 sscanf (buf, %d/%d/%d ,…);

4.使用 scanf( %d/%d/%d ,…). 补充 : 不记得是哪一年得 若干年后的某月某日是星期几,虽然最后求解出来了,但是比较麻烦.关于给定年月日求星期几,我 整理了一下,大约有下面一些公式: 一:常用公式 D Y Y Y Y W + ? + ? ? ? + ? = ]