资料成果技术类初识acm

1、ACM程序设计程序设计杭州电子科技大学 刘春英2022-2-272第一讲第一讲ACMACM入门入门(Introduction (Introduction to ACM)to ACM)2022-2-273第一部分第一部分初始初始ACM2022-2-274ACM- ACM- (Association for Computing (Association for Computing Machinery)Machinery)成立于计算机诞生次年，是目前计算成立于计算机诞生次年，是目前计算机学界中历史最悠久、最具权威性的机学界中历史最悠久、最具权威性的组织组织What is ACM ?What is A

2、CM ?2022-2-275我们说的我们说的“ACM”“ACM”是什么？是什么？2022-2-276ACM/ICPCACM/ICPC： ACM主办的国际大学生程序设计竞赛主办的国际大学生程序设计竞赛 (International Collegiate Programming Contest)，简称，简称ACM / ICPC，自从，自从1977年年开始至今已经连续举办开始至今已经连续举办31届。其宗旨是提供届。其宗旨是提供一个让大学生向一个让大学生向IT界展示自己分析问题和解界展示自己分析问题和解决问题的能力的绝好机会，让下一代决问题的能力的绝好机会，让下一代IT天才天才可以接触到其今后工作中将

3、要用到的各种软可以接触到其今后工作中将要用到的各种软件。件。现在，现在，ACM / ICPC已成为世界各国大学生中已成为世界各国大学生中最具影响力的国际计算机赛事。（非官方）最具影响力的国际计算机赛事。（非官方）2022-2-277ACM/ICPC in ChinaACM/ICPC in China中国大陆高校从中国大陆高校从19961996年开始参加年开始参加ACM/ICPCACM/ICPC前六届中国赛区设在上海，由上海大学承办；前六届中国赛区设在上海，由上海大学承办；20022002年由清华大学和西安交通大学承办；年由清华大学和西安交通大学承办；20032003年由清华大学和中山大学承办。

4、年由清华大学和中山大学承办。20042004年由北京大学和上海交通大学承办。年由北京大学和上海交通大学承办。20052005年由四川大学、北大和浙大承办。年由四川大学、北大和浙大承办。20062006年由上海大学、清华和西电承办。年由上海大学、清华和西电承办。20072007年：北航、南航、吉大、西华年：北航、南航、吉大、西华20082008年：哈工程、北交、合肥、杭电、西南民大年：哈工程、北交、合肥、杭电、西南民大2022-2-278ACM in HDUACM in HDUn20032003年年9 9月，第一次参加此类比赛（浙大邀请赛）月，第一次参加此类比赛（浙大邀请赛）n200420042

5、0082008，每年，每年5 5月月n 浙江省第浙江省第1 15 5届大学生程序设计竞赛届大学生程序设计竞赛n2004200420082008，每年，每年11121112月月n 第第29293333届届ACMACM国际大学生程序设计竞国际大学生程序设计竞赛亚洲区预选赛赛亚洲区预选赛2022-2-279预期赛事（今后每年）预期赛事（今后每年）n3434月，举行校内大赛（暨选拔赛）月，举行校内大赛（暨选拔赛）n5 5月，参加浙江省大学生程序设计大赛月，参加浙江省大学生程序设计大赛n1111月，参加月，参加ACM/ICPCACM/ICPC亚洲区比赛（至少亚洲区比赛（至少参加参加5 5个赛区的比赛）个

6、赛区的比赛）n另外，每学期至少有三次月赛以及适当另外，每学期至少有三次月赛以及适当的练习赛的练习赛2022-2-2710如何比赛如何比赛?2022-2-2711F 首先根据解题数目进行排名。F 如果多支队伍解题数量相同，则根据总用时加上惩罚时间进行排名。F 总用时和惩罚时间由每道解答正确的试题的用时加上惩罚时间而成。F 每道试题用时将从竞赛开始到试题解答被判定为正确为止，其间每一次错误的运行将被加罚20分钟时间，未正确解答的试题不记时。如何排名？如何排名？2022-2-2712比赛形式比赛形式n1支队伍1台机器（提供打印服务）n上机编程解决问题（可带纸质资料）n实时测试，动态排名n试题n8-1

7、0题n全英文（可以带字典）n时间：持续5个小时2022-2-2713ACM .vs. 校程序设计竞赛校程序设计竞赛nACM竞赛n团队合作精神n即时提交，通过所有数据才能得分n全英文题目，题目考察范围广n校程序设计竞赛n个人编程能力的比拼n中文或英文（以后全英文），考察编程基本功2022-2-2714ACM队队员的基本原则队队员的基本原则n基本要求n人品好n愿意花时间在这项赛事上n有团队合作精神n能力要求n程序设计n英语科技文献阅读n数学2022-2-2715关于信息工程学院关于信息工程学院ACMn参赛历史n2005 2人 2人银牌n2006 2队 1铜 n2007 2队 1银n2008 6队

8、2银1铜（省内排名？）n2009 ？ ？2022-2-271620082008省赛排名情况省赛排名情况n金奖银奖金奖银奖113041n浙江大学：浙江大学：4812n杭州电子：杭州电子：268（另：（另：4铜）铜）n浙江工大：浙江工大：246（另：（另：2铜）铜）n宁波理工：宁波理工：224（另：（另：2铜）铜）n宁波大学：宁波大学：112n浙江师大：浙江师大：044n杭电信息：杭电信息：022n温州大学：温州大学：011n浙江理工：浙江理工：011n工大之江：工大之江：0112022-2-271720082008亚洲赛战况亚洲赛战况n暑假集训队伍数：暑假集训队伍数：11支支n（含信息工程学院（

9、含信息工程学院1支）支）n参加了现场赛的队伍数：参加了现场赛的队伍数：11支支n获奖队伍数：获奖队伍数：8支队获得奖牌支队获得奖牌n（2银银11铜，其中信息铜，其中信息2铜）铜）2022-2-2718杭电参赛历程杭电参赛历程2022-2-27192022-2-27202022-2-27212022-2-27222022-2-27232022-2-27242006集训队全家福集训队全家福2022-2-27252007集训队全家福集训队全家福20082008集训队全家福集训队全家福2022-2-2727开课目的开课目的n为杭电为杭电ACMACM代表队培养后备人才代表队培养后备人才n提高分析问题和应

10、用计算机编程解决提高分析问题和应用计算机编程解决问题的能力问题的能力n培养必要的自学能力培养必要的自学能力n培养学生的协调和沟通能力培养学生的协调和沟通能力n体会学习的快乐体会学习的快乐2022-2-2728如何入门呢如何入门呢? ?2022-2-2729ACMACM题目特点题目特点: :由于ACM竞赛题目的输入数据和输出数据一般有多组（不定），并且格式多种多样，所以，如何处理题目的输入输出是对大家的一项最基本的要求。这也是困扰初学者的一大问题。下面，分类介绍：2022-2-2730先看一个超级简单的题目：先看一个超级简单的题目：n nSample input:n1 5n10 20nSampl

11、e output:n6n302022-2-2731初学者很常见的一种写法：初学者很常见的一种写法：n#includenvoid main()nn int a,b;n scanf(“%d %d”,&a,&b);n Printf(“%d”,a+b);n2022-2-2732有什么问题呢？有什么问题呢？这就是下面需要解决的问题这就是下面需要解决的问题2022-2-2733第二部分第二部分基本输入输出基本输入输出2022-2-2734输入输入_第一类：第一类：n输入不说明有多少个Input Block,以EOF为结束标志。 参见：HDOJ_1089n 2022-2-2735Hdoj_1089源代码：源

12、代码：#include int main() int a,b; while(scanf(%d %d,&a, &b) != EOF) printf(%dn,a+b); 2022-2-2736本类输入解决方案：本类输入解决方案：nC语法：nwhile(scanf(%d %d,&a, &b) != EOF) n . nC+语法：nwhile( cin a b ) . 2022-2-2737说明（说明（1）：）：1.Scanf函数返回值就是读出的变量个数，如：scanf( “%d %d”, &a, &b ); 如果只有一个整数输入，返回值是1，如果有两个整数输入，返回值是2，如果一个都没有，则返回值是

13、-1。2.EOF是一个预定义的常量，等于-1。2022-2-2738输入输入_第二类：第二类：n输入一开始就会说有N个Input Block,下面接着是N个Input Block。 参见：HDOJ_1090 n p?pid=10902022-2-2739Hdoj_1090Hdoj_1090源代码：源代码：#include int main() int n,i,a,b; scanf(%d,&n);for(i=0;in;i+) scanf(%d %d,&a, &b); printf(%dn,a+b); 2022-2-2740本类输入解决方案：本类输入解决方案：nC语法：nscanf(%d,&n)

14、; nfor( i=0 ; i n; for( i=0 ; in ; i+ ) . 2022-2-2741输入输入_第三类：第三类：n输入不说明有多少个Input Block,但以某个特殊输入为结束标志。n参见：HDOJ_1091 n p?pid=10912022-2-2742Hdoj_1091Hdoj_1091源代码：源代码：#include int main() int a,b;while(scanf(%d %d,&a, &b) &(a!=0 & b!=0) printf(%dn,a+b); 上面的程序有什么问题？上面的程序有什么问题？2022-2-2743本类输入解决方案：本类输入解决方

15、案：nC语法：nwhile(scanf(%d,&n) & n!=0 ) n . nC+语法：nwhile( cin n & n != 0 ) . 2022-2-2744输入输入_第四类：第四类：n以上几种情况的组合 n p?pid=1092n p?pid=1093n p?pid=10942022-2-2745输入输入_第五类：第五类：n输入是一整行的字符串的参见：HDOJ_1048 n p?pid=10482022-2-2746本类输入解决方案：本类输入解决方案：nC语法：n char buf20; gets(buf); nC+语法：n如果用string buf;来保存：n getline(

16、cin , buf ); n如果用char buf 255 ; 来保存： cin.getline( buf, 255 );2022-2-2747说明（说明（5_1）：）：nscanf(“ %s%s”,str1,str2)，在多个字符串之间用一个或多个空格分隔；n若使用gets函数，应为gets(str1); gets(str2); 字符串之间用回车符作分隔。n通常情况下，接受短字符用scanf函数，接受长字符用gets函数。n而getchar函数每次只接受一个字符，经常c=getchar()这样来使用。2022-2-2748说明说明(5_2)(5_2)：cin.getlinecin.getli

17、ne的用法：的用法：ngetline 是一个函数，它可以接受用户的输入的字符，直到已达指定个数，或者用户输入了特定的字符。它的函数声明形式（函数原型）如下：nistream& getline(char line, int size, char endchar = n);n不用管它的返回类型，来关心它的三个参数：nchar line： 就是一个字符数组，用户输入的内容将存入在该数组内。nint size : 最多接受几个字符？用户超过size的输入都将不被接受。nchar endchar :当用户输入endchar指定的字符时，自动结束。默认是回车符。2022-2-2749说明说明(5_2)(5

18、_2)续续n结合后两个参数，getline可以方便地实现： 用户最多输入指定个数的字符，如果超过，则仅指定个数的前面字符有效，如果没有超过，则用户可以通过回车来结束输入。nchar name4;ncin.getline(name,4,n);n由于 endchar 默认已经是 n，所以后面那行也可以写成：ncin.getline(name,4);2022-2-2750思考：思考：n以下题目属于哪一类输入？以下题目属于哪一类输入？n p?pid=1018n p?pid=10132022-2-2751输出输出_第一类：第一类：n一个Input Block对应一个Output Block，Output

19、 Block之间没有空行。 参见：HDOJ_1089n .php?pid=10892022-2-2752解决方案：解决方案：nC语法：n . printf(%dn,ans); n nC+语法：n . cout ans endl; 2022-2-2753输出输出_第二类：第二类：n一个Input Block对应一个Output Block，每个Output Block之后都有空行。参见：HDOJ_1095 n p?pid=10952022-2-275410951095源代码源代码#include int main() int a,b; while(scanf(%d %d,&a, &b) != E

20、OF) printf(%dnn,a+b); 2022-2-2755解决办法：解决办法：nC语法：n . printf(%dnn,ans); n nC+语法：n . cout ans endl endl; 2022-2-2756输出输出_第三类：第三类：n一个Input Block对应一个Output Block，Output Block之间有空行。 参见：HDOJ_1096 n p?pid=10962022-2-27571096源代码源代码n#include n int main()n n int icase,n,i,j,a,sum;n scanf(%d,&icase);n for(i=0;i

21、icase;i+)n nsum=0;n scanf(%d,&n);nfor(j=0;jn;j+)nn scanf(%d,&a);n sum+=a;nnif(iicase-1)n printf(%dnn,sum);n elsen printf(%dn,sum);n n 2022-2-2758解决办法：解决办法：nC语法：nfor (k=0;kcount;k+) while () printf( %dn,result); if (k!=count-1) printf(n); nC+语法：n类似，输出语句换一下即可。2022-2-2759思考：思考：n以下题目属于哪一类输出？以下题目属于哪一类输出？

22、n p?pid=1016n p?pid=10172022-2-2760附附:初学者常见问题初学者常见问题2022-2-2761一、编译错误一、编译错误nMain函数必须返回int类型(正式比赛)n不要在for语句中定义类型n_int64不支持，可以用long long代替n使用了汉语的标点符号nitoa不是ansi函数n 能将整数转换为字符串而且与ANSI标准兼容的方法是使用sprintf()函数n int num = 100; char str25; sprintf(str, %d , num);n另外，拷贝程序容易产生错误2022-2-2762下面的下面的hdoj1089hdoj1089为什么为什么 CE? CE?#include int main() int a,b; while(scanf(%d %d,&a, &b) != EOF) printf(%dn,a+b); 2022-2-2763二、小技巧二、小技巧n数据的拷贝（特别是输出的提