杭电ACM课件2008版---2

1009算法分析：输入（J,F放入数组）对数组排序（按效益，降序）输出（按效益高低有序交易）第三类技巧
型先来看一个简单的题目铺垫一下:1021FibonacciAgain题目分析：能被3整除的整数
的特点？还要看程序吗？如果两个数的和能被3整除，这两个数有什么特点？关于能否被3整除，这两个数一共有多少种组合？H
doj_1021程序清单：#includeintmain(){longn;whil
e(scanf("%ld",&n)!=EOF) if(n%8==2||n%8==6) printf("
yes\n"); else printf("no\n"); return0;}回到正题Prob
lemB:NumberSequence题目特点： 这个题目是一个比较典型的ACM竞赛题，尽管在真正的大赛中这个
题目可能算比较简单的，但在本次比赛中，本题难度属于中等，可以说，能做出本题的队伍基本都有二等奖以上。 但如果不认真分析，有可能
会掉入陷阱。Question:暴力能解决问题吗？Why?题目分析： 对于这种题目，千万不能蛮干
！实际上，有经验的同学看到本题目的数据规模，很快就能知道：这类题目有规律可循。现在对这题有什么想法???第
四类纸老虎型HDOJ_1071TheArea第一眼：傻了…再一看?抛物线公式：y=ax^2
+bx+c已知三点-〉a、b、c系数公式已知-〉如何求面积？会简单积分吗？该你思考了…感觉怎么样？
思考题(1)：（UralCollegiateProgrammingContest1998）http://
acm.hdu.edu.cn/showproblem.php?pid=1030题目大意：InputInputconta
instwointegernumbersMandNintherangefrom1to1000000000
separatedwithspace(s).OutputOutputshouldcontaintheleng
thoftheshortestroute.SampleInput612SampleOutput3
思考：要输出的结果和哪些因素有关？ 请发表见解。思考题(2)：（3月4日HDOJ的练习赛题目）要点分析
：1、暴力的复杂度是多少？2、哪些陷阱？3、关键在哪？4、顺利应该多长时间？数学公式:1、这个大家都会：1+2
+3+4+…n=n(n+1)/22、这个有些同学忘记了：11+22+33+…+nn=n(n+1)(2n+1)/
63、合并后得到n(n+1)(n+2)/3Anyquestion?课后作业（简单数学题）H
DOJ作业：一、DIY在线作业(2):《ACMProgramming》Exercise（2）byLCY二、常规练习（
包含以上作业）1004、1005、1008、10091012～1014、1019～10211049、1060、1061、10
661071、1178、1108、10301205、1597下次课内容：递推求解课后一定要练习！
Seeyounextweek.Thankyou!ACM程序设计计算机学院刘春英
今天，你了吗？AC每周一星（1）：06050016wuxingling关于期末考核
的补充：平时成绩30％ -分数组成（2×（10～12）＋其它）期末考试70％（5个题目） -分数组成（25-15-15-
10-5）开胃羹（1）几个常用单词：1、vertex(vertices)顶点2、polygon多边形
3、convex凸的4、concave凹的5、segment(线)段（n）;分割（v）开胃羹（2）
再来几个：1、integer整数2、positive正的3、negative(adj)负的;(
n)负数4、factorial(n)阶乘;(adj)因子的，阶乘的5、digital(n)数字;
(adj)数字的第三讲老少皆宜之数学题ACM数学题特点分析:题意容易理解算法相对简单（有些很难的！！
）编程比较容易ACM/ICPC入门练习的好选择下面，分类介绍：从首届“舜宇”杯说起比赛背景 由于前一
年的邀请赛很多学校没有做出一道题，所以，这次的比赛特意准备了几道简单的题目，目的就是让大多数的学校都能拿个气球回去，也好有个交待，
于是有…第一类弱智型ProblemA:LettheBalloonRise题目评述：
1.一个让你看到后兴奋的题目…2.只要懂点C或者C++，就可解决该问题。1004题目分析：该题算法思想比较
简单，就是对输入的字符串进行比较和统计。值得注意的一点是：如果用C语言来写，要注意可能会把第一个数字后的“回车符”误认为是第一个
串，字符串的比较也要用函数和循环语句。而C++则在处理字符串方面较为方便。ProblemE:Elevator
实际上，这是本次比赛最简单的一题，浙大、浙工大等当时训练水平相对较高的学校基本上10分钟之内解决该题，这也是一个没有算法的题目。
这种题目大家不会错过的…题目评述：不要分析了吧…第二类基本型ProblemF:FatMouse''Trade题目特点： 这个题目比前面两个题目稍难，但是属于能一眼看出解决办法的题目。只要静下心，还是比较容易解决的。