ACM 程序设计 计算机学院 刘春英 2018/11/30.

Presentation on theme: "ACM 程序设计 计算机学院 刘春英 2018/11/30."— Presentation transcript:

1 ACM 程序设计 计算机学院 刘春英 2018/11/30

2 第一讲 ACM入门 2018/11/30

3 第一部分 初识ACM 2018/11/30

4 What is ACM ? ACM (Association for Computing Machinery)
成立于计算机诞生次年，是目前计算机学界中历史最悠久、最具权威性的组织… 2018/11/30

5 我们说的“ACM” 是什么？ 2018/11/30

6 ACM/ICPC： ACM主办的国际大学生程序设计竞赛 (International Collegiate Programming Contest)，简称ACM / ICPC，自从1977年开始至今已经连续举办31届。其宗旨是提供一个让大学生向IT界展示自己分析问题和解决问题的能力的绝好机会，让下一代IT天才可以接触到其今后工作中将要用到的各种软件。 现在，ACM / ICPC已成为世界各国大学生中最具影响力的国际计算机赛事。（非官方） 2018/11/30

7 ACM/ICPC in China 中国大陆高校从1996年开始参加ACM国际大学生程序设计竞赛亚洲预赛。
前六届中国赛区设在上海，由上海大学承办； 2002年由清华大学和西安交通大学承办； 2003年由清华大学和中山大学承办。 2004年由北京大学和上海交通大学承办。 2005年由四川大学、北大和浙大承办。 2006年由上海大学、清华和西电承办。 2007年：北航、南航、吉大、西华 2018/11/30

8 2018/11/30

9 ACM in HDU 2003年9月，第一次参加省赛（邀请赛） 2004年5月，浙江省“舜宇”杯首届大学生程序设计大赛
2005年5月,浙江省第二届“舜宇”杯大学生程序设计大赛 2005年11月,参加中国大陆的三站亚洲区比赛 2006年5月,浙江省第二届“舜宇”杯大学生程序设计大赛 2006年11~12月，第31届ACM首尔、北京、上海和西安赛区比赛 今年… 2018/11/30

10 预期赛事（今后每年） 3~4月，举行校内大赛（暨选拔赛） 5月，参加浙江省大学生程序设计大赛
11月，参加ACM/ICPC亚洲区比赛（至少参加4～5个赛区的比赛） 另外，每学期至少有三次月赛以及适当的练习赛 2018/11/30

11 如何比赛？  3人组队  可以携带诸如书、手册、 程序清单等参考资料；不能携带任何可用计算机处理的软件或数据、不能携带任何类型的通讯工具； 可能收到的反馈信息包括： Compile Error -- 程序不能通过编译。 Run Time Error -- 程序运行过程中出现非正常中断。 Time Limit Exceeded -- 运行超过时限还没有得到输出结果。 Wrong Answer -- 答案错误。 Presentation Error -- 输出格式不对，可检查空格、回车等等细节。 Accepted -- 恭喜恭喜！ 2018/11/30

12 如何排名？ 首先根据解题数目进行排名。 如果多支队伍解题数量相同，则根据总用时加上惩罚时间进行排名。
总用时和惩罚时间由每道解答正确的试题的用时加上惩罚时间而成。 每道试题用时将从竞赛开始到试题解答被判定为正确为止，其间每一次错误的运行将被加罚20分钟时间，未正确解答的试题不记时。 2018/11/30

13 比赛形式 试题 时间：持续5个小时 1支队伍1台机器（提供打印服务） 上机编程解决问题（可带纸质资料） 实时测试，动态排名 6-10题
全英文（可以带字典） 时间：持续5个小时 2018/11/30

14 ACM .vs. 校程序设计竞赛 ACM竞赛 校程序设计竞赛 团队合作精神 即时提交，通过所有数据才能得分 全英文题目，题目考察范围广
个人编程能力的比拼 中文或者英文题目，考察编程基本功 2018/11/30

15 ACM队队员的基本原则 基本要求 能力要求 数学 人品好 愿意花时间在这项赛事上 有团队合作精神 程序设计 英语科技文献阅读
2018/11/30

16 杭电参赛历程 2018/11/30

17 HDU-ACM * 集训队* 2018/11/30

18 放松完毕 回到正题 2018/11/30

19 开课目的 为杭电ACM代表队培养后备人才 提高分析问题和应用计算机编程解决问题的能力 培养必要的自学能力 培养学生的协调和沟通能力
体会学习的快乐 2018/11/30

20 如何入门呢? 2018/11/30

21 ACM题目特点: 由于ACM竞赛题目的输入数据和输出数据一般有多组（不定），并且格式多种多样，所以，如何处理题目的输入输出是对大家的一项最基本的要求。这也是困扰初学者的一大问题。 下面，分类介绍： 2018/11/30

22 先看一个超级简单的题目： http://acm.hziee.edu.cn/showproblem.php?pid=1089
Sample input: 1 5 10 20 Sample output: 6 30 2018/11/30

23 初学者很常见的一种写法： #include<stdio.h> void main() { int a,b;
scanf(“%d %d”,&a,&b); Printf(“%d”,a+b); } 2018/11/30

24 有什么问题呢？ 这就是下面需要解决的问题 2018/11/30

25 第二部分 基本输入输出 2018/11/30

26 输入_第一类： 输入不说明有多少个Input Block,以EOF为结束标志。 参见：HDOJ_1089
2018/11/30

27 Hdoj_1089源代码： int a,b; #include <stdio.h> int main() {
while(scanf("%d %d",&a, &b) != EOF) printf("%d\n",a+b); return 0; } 2018/11/30

28 本类输入解决方案： C语法： while(scanf("%d %d",&a, &b) != EOF) { .... } C++语法：
{     } C++语法： while( cin >> a >> b ) {     } 2018/11/30

29 说明（1）： Scanf函数返回值就是读出的变量个数，如：scanf( “%d %d”, &a, &b ); 如果只有一个整数输入，返回值是1，如果有两个整数输入，返回值是2，如果一个都没有，则返回值是-1。 EOF是一个预定义的常量，等于-1。 2018/11/30

30 输入_第二类： 输入一开始就会说有N个Input Block,下面接着是N个Input Block。 参见：HDOJ_1090
2018/11/30

31 Hdoj_1090源代码： #include <stdio.h> int main() { int n,i,a,b;
scanf("%d",&n); for(i=0;i<n;i++) scanf("%d %d",&a, &b); printf("%d\n",a+b); } return 0; 2018/11/30

32 本类输入解决方案： C语法： scanf("%d",&n) ; for( i=0 ; i<n ; i++ ) { .... }
cin >> n; for( i=0 ; i<n ; i++ ) {     } 2018/11/30

33 输入_第三类： 输入不说明有多少个Input Block,但以某个特殊输入为结束标志。 参见：HDOJ_1091
2018/11/30

34 Hdoj_1091源代码： 上面的程序有什么问题？
#include <stdio.h> int main() { int a,b; while(scanf("%d %d",&a, &b) &&(a!=0 && b!=0)) printf("%d\n",a+b); } 上面的程序有什么问题？ 2018/11/30

35 本类输入解决方案： C语法： while(scanf("%d",&n) && n!=0 ) { .... } C++语法：
{     } C++语法： while( cin >> n && n != 0 ) {     } 2018/11/30

36 输入_第四类： 以上几种情况的组合 http://acm.hdu.edu.cn/showproblem.php?pid=1092
2018/11/30

37 输入_第五类： 输入是一整行的字符串的 参见：HDOJ_1048
2018/11/30

38 本类输入解决方案： C语法： char buf[20]; gets(buf); C++语法： 如果用string buf;来保存：
getline( cin , buf ); 如果用char buf[ 255 ]; 来保存： cin.getline( buf, 255 ); 2018/11/30

39 说明（5_1）： scanf(“ %s%s”,str1,str2)，在多个字符串之间用一个或多个空格分隔；
若使用gets函数，应为gets(str1); gets(str2); 字符串之间用回车符作分隔。 通常情况下，接受短字符用scanf函数，接受长字符用gets函数。 而getchar函数每次只接受一个字符，经常c=getchar()这样来使用。 2018/11/30

40 说明（5_2）：cin.getline的用法：
istream& getline(char line[], int size, char endchar = '\n'); 不用管它的返回类型，来关心它的三个参数： char line[]： 就是一个字符数组，用户输入的内容将存入在该数组内。 int size : 最多接受几个字符？用户超过size的输入都将不被接受。 char endchar :当用户输入endchar指定的字符时，自动结束。默认是回车符。 2018/11/30

41 说明（5_2）续 结合后两个参数，getline可以方便地实现： 用户最多输入指定个数的字符，如果超过，则仅指定个数的前面字符有效，如果没有超过，则用户可以通过回车来结束输入。 char name[4]; cin.getline(name,4,'\n'); 由于 endchar 默认已经是 '\n'，所以后面那行也可以写成： cin.getline(name,4); 2018/11/30

42 思考： 以下题目属于哪一类输入？ http://acm.hdu.edu.cn/showproblem.php?pid=1018
2018/11/30

43 输出_第一类： 一个Input Block对应一个Output Block，Output Block之间没有空行。 参见：HDOJ_1089
2018/11/30

44 解决方案： C语法： { .... printf("%d\n",ans); } C++语法：
{     ...     cout << ans << endl; } 2018/11/30

45 输出_第二类： 一个Input Block对应一个Output Block，每个Output Block之后都有空行。 参见：HDOJ_1095 2018/11/30

46 1095源代码 #include <stdio.h> int main() { int a,b;
while(scanf("%d %d",&a, &b) != EOF) printf("%d\n\n",a+b); } 2018/11/30

47 解决办法： C语法： { .... printf("%d\n\n",ans); } C++语法：
{     ...     cout << ans << endl << endl; } 2018/11/30

48 输出_第三类： 一个Input Block对应一个Output Block，Output Block之间有空行。 参见：HDOJ_1096
2018/11/30

49 1096源代码 #include <stdio.h> int main() { int icase,n,i,j,a,sum;
scanf("%d",&icase); for(i=0;i<icase;i++) sum=0; scanf("%d",&n); for(j=0;j<n;j++) scanf("%d",&a); sum+=a; } if(i<icase-1) printf("%d\n\n",sum); else printf("%d\n",sum); 2018/11/30

50 解决办法： C语法： for (k=0;k<count;k++) {       while (…)       {              printf(" %d\n",result);       }       if (k!=count-1) printf("\n"); } C++语法： 类似，输出语句换一下即可。 2018/11/30

51 思考： 以下题目属于哪一类输出？ http://acm.hdu.edu.cn/showproblem.php?pid=1016
2018/11/30

52 附: 初学者常见问题 2018/11/30

53 一、编译错误 Main函数必须返回int类型(正式比赛) 不要在for语句中定义类型 __int64不支持，可以用long long代替
使用了汉语的标点符号 itoa不是ansi函数 能将整数转换为字符串而且与ANSI标准兼容的方法是使用sprintf()函数 int num = 100;     char str[25];     sprintf(str, " %d" , num); 另外，拷贝程序容易产生错误 2018/11/30

54 下面的hdoj1089为什么 CE? int a,b; #include < stdio.h> int main() {
while(scanf("%d %d",&a, &b) != EOF) printf("%d\n",a+b); } 2018/11/30

55 二、小技巧 数据的拷贝（特别是输出的提示信息） 调试的sample input的拷贝 2018/11/30

56 例题（Hdoj_1170） 三、C语言处理“混合数据”的问题
2018/11/30

57 常见的代码： …… scanf("%d\n",&icase); for (i=0;i<icase;i++) {
scanf("%c%d%d",&opera,&num1,&num2); } 2018/11/30

58 有什么问题？ 2018/11/30

59 四、Printf和cout混用的问题 以下的程序输出什么？ #include<stdio.h>
#include<iostream.h> int main() { int j=0; for(j=0;j<5;j++) cout<<"j="; printf("%d\n",j); } return 0; 2018/11/30

60 为什么？ 一个带缓冲输出（cout） 一个不带缓冲输出(printf) 2018/11/30

61 五、输入输出原理 Input 1 5 2 6 10 20 Output 6 8 30 222 444 2018/11/30

62 思考题(目的：初步体会一下ACM的魅力)
Given two non-negative integers m and n, you will have to find the last digit of mn in decimal number system. Input The input file contains several lines. Each line contains two integers m and n (both less than ). Input is terminated by a line containing two zeroes. This line should not be processed. Output For each set of input you must produce one line of output which contains a single digit. This digit is the last digit of mn. Sample Input 3 2 3 5 0 0 Sample Output 9 3 2018/11/30

63 授课方式与成绩评定 介绍常用算法 举例分析 上机练习（自己在线练习） 成绩评定：机试 ( 5 ~ 6 题 ) 2018/11/30

64 相关资料 数学知识 离散、组合 数论、图论 计算几何 算法&数据结构 基本数据结构 搜索、分治 动态规划 贪心…… 2018/11/30

65 学习方式 练习->总结->练习->总结->…… http://acm.hdu.edu.cn 杭电ACM论坛
google、baidu 2018/11/30

66 去哪里练习？ 2018/11/30

67 常见问题： 1、需要什么基础？( C/C++ ) 2、英语不好怎么办？(问题不大) 3 、如何加入集训队? (200 && 申请 )
4 、可以退课吗? ( Of course! ) 2018/11/30

68 想对大家说的话… 2018/11/30

69 课后任务： 1、熟悉http://acm.hdu.edu.cn 2、完成在线练习： 《ACM Programming》Exercise（1）
3、学有余力，可以尝试下面题目: 、1013、1061 1170、 2018/11/30

70 See you next week! 2018/11/30