ACM讲义
- 格式：doc
- 大小：1015.00 KB
- 文档页数：50
ACM程序设计培训讲义陈蕴谷2011年7月前言ACM/ICPC（ACM世界大学生程序设计竞赛）经过40年的发展，目前已经成为世界顶尖级的比赛。
独具一格的竞赛模式风格和著名的IBM公司赞助，吸引了众多大学生的参与。
近几年来，ACM ICPC在中国得到了空前的发展、Regional 赛区由2个增加到5个、赛事包括校赛、Regional、省赛、地区赛等多种层次、几乎每个学生都会有机会参与此项赛事活动。
相信你的参与肯定会为ACM ICPC 增添新的色彩。
工作一年有余，作为教师和辅导员的我经常会被问到同一个问题：“学习知识有用吗？学习C语言将来会有什么作用呢？课堂上枯燥的知识在现实世界中能用的上吗？”，参加过这个比赛你将会得到一个明确的答案：有用。
如果你在google上搜索一个人名的时候，当你不确定人名的时候，google是不是也能帮你找出来这个人名，你是否感觉计算机也是有思维的，而你是否想过计算机的思维是谁给的？是我们给的。
当你可以赋予一个计算机有人一样的思维的时候，你是不是感觉很amazing。
而当你使用智能化的sogou词库同步、暴风影音的自动播放下一个关联电影、千千静听的自动下载歌词的时候，你是不是感觉很方便。
不过你不要感觉很神秘，只要你是个用心的人，这些功能你都能实现，而且我相信你会比这些做的更好。
当你的思想的火花和计算机世界接轨的时候，一个有意义的程序就会诞生了。
当你用合理的数据结构和优秀的算法编写的每一句代码，小到能解决一个实际问题，大到能为国家的经济发展贡献一份力量。
ACM ICPC就给我们提供了这么一个平台，用你的思想解决现实世界中的种种问题。
当你把现实世界中物体的特征抽象到一堆数据时，用合理的数据结构存储到计算机里，用理想化的算法处理后传达到世界各个地方。
你会感觉到C语言书本的作用、课堂的意义、人生的意义。
众所周知，程序=算法+数据结构。
如果给你一种思想后，写出伪代码后，让你编写一个程序是很容易的。
所以现在的程序员是很多的，用普通的话说就是“搬砖”的总是会有的，而会指挥的人总是少的。
只有你学会少数人尝试的、一些尖端的知识后，你才会有可能走到社会的上层，而用心学习某些算法就是一个捷径。
当程序的数据达到亿万数量级的时候，有的人用1秒就有可能处理完所有的数据并得到合理的结果，有的人却要1天后能得到结果，这时候算法的作用就显现的尤为重要。
算法是一个程序的灵魂，是一个程序健壮性的标准，是一个程序生存周期长短的见证。
参加ACM ICPC没有想象的那么枯燥、那么难。
年轻的我们没有失败，只要亮出我们的风采，命运全在拼击，奋斗就是希望。
Join us,Happy everyday!陈蕴谷2011年7月于安庆目录ACM程序设计培训讲义 (1)前言 (1)一C语言难点讲解 (1)1.1 函数的传值和传址 (1)1.2 指针 (1)1.3 链表 (1)二递归 (2)2.1 递归的思想 (2)2.2 递归的应用 (2)2.3 递归的优缺点 (2)三分治 (3)3.1 分治的思想 (3)3.2 分治的应用 (3)四贪心算法 (4)4.1 贪心的思想 (4)4.2 贪心的应用 (4)五动态规划 (11)5.1 动态规划入门 (11)5.2 动态规划的基本思路 (14)5.3 动态规划的应用 (15)例1：最长上升子序列 (15)例2：Help Jimmy (17)例3：最长公共子序列 (20)5.4 贪心和动态规划的区别 (22)六大数问题 (24)6.1 大数的应用背景 (24)6.2 大数的加减乘除 (24)6.2.1大整数加法 (24)6.2.2 例题：大整数乘法 (26)6.2.3 例题：大整数除法 (29)6.3 大数的应用 (32)麦森数 (32)七数据结构 (36)7.1 栈和队列 (36)7.2 字符串匹配 (36)7.3 树 (36)7.4 图 (36)7.5 查找 (36)7.6 排序 (36)7.7 网络流 (36)八计算几何 (37)8.1 矢量 ..................................................................................... 错误！未定义书签。
8.1.1 矢量的概念 ................................................................. 错误！未定义书签。
8.1.2 矢量加减法 ................................................................. 错误！未定义书签。
8.1.3 矢量叉积..................................................................... 错误！未定义书签。
8.1.4 矢量叉积的应用 .......................................................... 错误！未定义书签。
8.2 包含关系 .............................................................................. 错误！未定义书签。
8.2.1 判断图形是否在矩形中................................................ 错误！未定义书签。
8.2.2 判断图形是否在多边形中 ............................................ 错误！未定义书签。
8.2.3 判断图形是否在圆中 ................................................... 错误！未定义书签。
8.3 凸包 ..................................................................................... 错误！未定义书签。
8.3.1 凸包的概念 ................................................................. 错误！未定义书签。
8.3.2 凸包的求法 ................................................................. 错误！未定义书签。
8.4 实例分析 .............................................................................. 错误！未定义书签。
例1 ..................................................................................... 错误！未定义书签。
例2 ..................................................................................... 错误！未定义书签。
例3 ..................................................................................... 错误！未定义书签。
例4 ..................................................................................... 错误！未定义书签。
九组合数学 . (39)9.1 鸽笼原理 (39)9.2 容斥原理 (39)9.3 递推关系 (39)9.4 发生函数 (39)9.5 Polya定理 (39)9.6 实例分析 (39)例1 (39)例2 (39)例3 (39)例4 (39)十POJ题目分类 (40)一C语言难点讲解1.1 函数的传值和传址1.2 指针1.3 链表二递归2.1 递归的思想2.2 递归的应用2.3 递归的优缺点三分治3.1 分治的思想3.2 分治的应用四贪心算法4.1 贪心的思想贪心算法总是作出在当前看来最好的选择。
也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。
当然，希望贪心算法得到的最终结果也是整体最优的。
虽然贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解。
如单源最短路径问题，最小生成树问题等。
在一些情况下，即使贪心算法不能得到整体最优解，其最终结果却是最优解的很好近似。
在对问题求解时，总是作出在当前看来是最好的选择。
也就是说，如果不从整体上加以考虑，它所作出的仅仅是在某种意义上的局部最优解（是否是全局最优，需要证明）。
若要用贪心算法求解某问题的整体最优解，必须首先证明贪心思想在该问题的应用结果就是最优解！！很多贪心类型的题目都象本题一样，不是最朴素的贪心，而是需要做一些变化，关键是找到贪心的本质！4.2 贪心的应用先看一个入门的例子：硕鼠的交易(HDOJ1009)FatMouse' TradeTime Limit: 2000/1000 MS (Jav a/Others) Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 6718 Accepted Submission(s): 1935Problem DescriptionFatMouse prepared M pounds of cat food, ready to trade with the cats guarding the warehouse containing his favorite food, JavaBean.The warehouse has N rooms. The i-th room contains J[i] pounds of JavaBeans and requires F[i] pounds of cat food. FatMouse does not have to trade for all the JavaBeans in the room, instead, he may get J[i]* a% pounds of JavaBeans if he pays F[i]* a% pounds of cat food. Here a is a real number. Now he is assigning this homework to you: tell him the maximum amount of JavaBeans he can obtain.InputThe input consists of multiple test cases. Each test case begins with a line containing two non-negative integers M and N. Then N lines follow, each contains two non-negative integers J[i] and F[i] respectively. The last test case is followed by two -1's. All integers are not greater than 1000.OutputFor each test case, print in a single line a real number accurate up to 3 decimal places, which is the maximum amount of JavaBeans that FatMouse can obtain.Sample Input5 3//M=5,N=3,M磅猫食，N间房间7 2//第一间房间7磅JavaBeans且需2磅猫食来换4 35 220 325 1824 1515 10-1 -1Sample Output13.33331.500代码：#include<stdio.h>#include<stdlib.h>double J[1005],F[1005];struct node{double s;int k;}S[1000];int cmp(const void* p1,const void* p2){return ((node *)p2)->s > ((node *)p1)->s ? 1 : -1; }int main(){double m;int n;while(scanf("%lf%d",&m,&n)!=EOF){if(m==-1&&n==-1) break;for(int i=0;i<n;i++){ scanf("%lf%lf",&J[i],&F[i]);S[i].s=J[i]/F[i];S[i].k=i;}qsort(S,n,sizeof(S[0]),cmp);double f=0;int j=0;for(int j=0;j<n;j++){if(F[S[j].k]<=m){f=f+J[S[j].k];m=m-F[S[j].k];}else{double k1=m/F[S[j].k];f=f+J[S[j].k]*k1;break;}}printf("%.3lf\n",f);}return 0;}再看一个例子：活动安排问题活动安排问题就是要在所给的活动集合中选出最大的相容活动子集合，是可以用贪心算法有效求解的很好例子。
