程序设计与竞赛介绍 .pptVIP

程序设计竞赛介绍 刘俊杰 07.10 ACM/ICPC简介 ACM国际大学生程序设计竞赛面向世界各高校，分区域预赛和国际决赛两个阶段进行 正规比赛以三人为一组比赛,学校的程序设计竞赛为个人赛,也是校队的选拔赛 正规赛题为英文题,学校比赛用中文题. 竞赛对知识和技能的要求 扎实的编程功底 数据结构:包括链表、栈、队列、树、图等的实现与应用。 基本算法:包括排序、查找、递归、深度广度优先有哪些信誉好的足球投注网站、动态规划，以及实现数据结构操作中的各种算法等。 其它：图论、数论组合数学、计算几何等 国内外大学ACM的online judge: acm.fzu.edu.cn/ 福州大学 acm.fjnu.edu.cn/ 福建师大 acm.pku.edu.cn/JudgeOnline北京大学 acm.tju.edu.cn/toj 天津大学 acm.uva.es 西班牙的 Universidad de Valladolid acm.timus.ru 俄罗斯乌拉尔大学 以上各大学的站点有着大量的竞赛题目，并可在线提交，是ACMer的主要操练场。 编程风格的差异 平时编写的代码注重代码的易读性和规范性，而竞赛编写的代码注重代码的高效性（运算高效，代码精简） while(scanf(%d %d,N,M),N M) {…} 在竞赛中是一段简洁的好代码，而在平时的编程中是不提倡的 数据的输入输出 ACM竞赛中数据的输入输出使用标准输入输出，但读入形式与读文件相类似。可以把数据的输入输出理解为从一个文件读入数据，从另一个文件输出数据，但用的语句是标准输入输出的语句。 竞赛中常用的输入输出语句是scanf, getline, printf,而非cin, cout（执行效率高） scanf scanf()也是有返回值的，它返回匹配的个数。当读到文件尾时返回-1。 有时程序要求读入多组数据直到文件尾，可用如下语句使代码精简： while(scanf(…)!=-1){…}或 while(scanf(…)!=EOF){…} 常用库函数 说明：只对一些常用库函数做简要说明或列举，详细的使用方法请查找其它资料。都是C中的库函数，但在C++中也基本可使用，似乎不用加include也可用^____^ 字符串转换 atoi/atol(const char *)，返回整数 atof(const char *)，返回double，不是float itoa(int, char *, int)其中第一个数为待转换数，第二个为buf，最后一个为基数，返回buf 常用库函数 long strtol(char * ps, char ** endp, int b) strtol()会将参数ps字符串根据参数b来转换成长整型数，b为基数。程序会扫描参数ps字符串，跳过前面的空格字符，直到遇上数字或正负符号才开始做转换，再遇到非数字或字符串结束时(‘’)结束转换，并将结果返回。若参数endp不为NULL，则会将遇到不合条件而终止的ps中的字符指针由endp返回。 strtoul是strtol的无符号版 strtod返回double，其没有第三个参数 常用库函数 strlen, strcpy, strcmp, strcat, 需要#includestring.h memset, memcpy, memmove 需要#includememory.h或者string.h 区别 注意，memset(dest, int, size_t) 赋初值一般只有0和-1可以用memset 例： int dest[100]; memset(dest,0,sizeof(int)); qsort qsort(array, n, elemsize, comp)用于排序的函数，用的算法是快排，时间复杂度为O(nlogn),在正常情况下基本够用。 参数说明：array待排数组，n数组元素个数，elemsize数组元素的大小，comp比较函数。基中比较函数声明为：int comp (const void *arg1,const void *arg2)当arg1排在arg2之前时返回-1,相等时返回0,之后返回1。 qsort就是把数组array中的前n个元素按comp函数的比较规则排序。 qsort 其它一些编程技巧 (1)逗号运算符的使用： C/C++中’,’表达式按从左到右顺序求值，表达式的值是最后一个分句的值,每个分句必须是表达式，不可以是语句。逗号表达式保证从左到右依次求值。 int a=1,b=2,c; c=a+1,b+1; printf(“%d”,c); 其它一些编程技巧 (2)freopen函数的使用： 有时在调式程序时，输入的样例数据很多，若每次都用手动输入速度太慢。可用freopen函数把