《lecture初识A》PPT课件.ppt

2020 3 20 1 ACM程序设计 计算机学院刘春英 2020 3 20 2 第一讲 ACM入门 2020 3 20 3 第一部分 初识ACM 2020 3 20 4 ACM AssociationforComputingMachinery 成立于计算机诞生次年 是目前计算机学界中历史最悠久 最具权威性的组织 WhatisACM 2020 3 20 5 我们说的 ACM 是什么 2020 3 20 6 ACM ICPC ACM主办的国际大学生程序设计竞赛 InternationalCollegiateProgrammingContest 简称ACM ICPC 自从1977年开始至今已经连续举办31届 其宗旨是提供一个让大学生向IT界展示自己分析问题和解决问题的能力的绝好机会 让下一代IT天才可以接触到其今后工作中将要用到的各种软件 现在 ACM ICPC已成为世界各国大学生中最具影响力的国际计算机赛事 非官方 2020 3 20 7 ACM ICPCinChina 中国大陆高校从1996年开始参加ACM国际大学生程序设计竞赛亚洲预赛 前六届中国赛区设在上海 由上海大学承办 2002年由清华大学和西安交通大学承办 2003年由清华大学和中山大学承办 2004年由北京大学和上海交通大学承办 2005年由四川大学 北大和浙大承办 2006年由上海大学 清华和西电承办 2007年 北航 南航 吉大 西华 2020 3 20 8 2020 3 20 9 ACMinHDU 2003年9月 第一次参加省赛 邀请赛 2004年5月 浙江省 舜宇 杯首届大学生程序设计大赛2004年11 12月 第29届ACM亚洲区北京和上海赛区比赛2005年5月 浙江省第二届 舜宇 杯大学生程序设计大赛2005年11月 参加中国大陆的三站亚洲区比赛2006年5月 浙江省第二届 舜宇 杯大学生程序设计大赛2006年11 12月 第31届ACM首尔 北京 上海和西安赛区比赛今年 2020 3 20 10 预期赛事 今后每年 3 4月 举行校内大赛 暨选拔赛 5月 参加浙江省大学生程序设计大赛11月 参加ACM ICPC亚洲区比赛 至少参加4 5个赛区的比赛 另外 每学期至少有三次月赛以及适当的练习赛 2020 3 20 11 如何比赛 3人组队 可以携带诸如书 手册 程序清单等参考资料 不能携带任何可用计算机处理的软件或数据 不能携带任何类型的通讯工具 可能收到的反馈信息包括 CompileError 程序不能通过编译 RunTimeError 程序运行过程中出现非正常中断 TimeLimitExceeded 运行超过时限还没有得到输出结果 WrongAnswer 答案错误 PresentationError 输出格式不对 可检查空格 回车等等细节 Accepted 恭喜恭喜 2020 3 20 12 首先根据解题数目进行排名 如果多支队伍解题数量相同 则根据总用时加上惩罚时间进行排名 总用时和惩罚时间由每道解答正确的试题的用时加上惩罚时间而成 每道试题用时将从竞赛开始到试题解答被判定为正确为止 其间每一次错误的运行将被加罚20分钟时间 未正确解答的试题不记时 如何排名 2020 3 20 13 比赛形式1支队伍1台机器 提供打印服务 上机编程解决问题 可带纸质资料 实时测试 动态排名试题6 10题全英文 可以带字典 时间 持续5个小时 2020 3 20 14 ACM vs 校程序设计竞赛 ACM竞赛团队合作精神即时提交 通过所有数据才能得分全英文题目 题目考察范围广校程序设计竞赛个人编程能力的比拼中文或者英文题目 考察编程基本功 2020 3 20 15 ACM队队员的基本原则 基本要求人品好愿意花时间在这项赛事上有团队合作精神能力要求程序设计英语科技文献阅读数学 2020 3 20 16 杭电参赛历程 2020 3 20 17 HDU ACM 集训队 2020 3 20 18 放松完毕回到正题 2020 3 20 19 开课目的 为杭电ACM代表队培养后备人才提高分析问题和应用计算机编程解决问题的能力培养必要的自学能力培养学生的协调和沟通能力体会学习的快乐 2020 3 20 20 如何入门呢 2020 3 20 21 ACM题目特点 由于ACM竞赛题目的输入数据和输出数据一般有多组 不定 并且格式多种多样 所以 如何处理题目的输入输出是对大家的一项最基本的要求 这也是困扰初学者的一大问题 下面 分类介绍 2020 3 20 22 先看一个超级简单的题目 2020 3 20 23 初学者很常见的一种写法 includevoidmain inta b scanf d d 2020 3 20 24 有什么问题呢 这就是下面需要解决的问题 2020 3 20 25 第二部分 基本输入输出 2020 3 20 26 输入 第一类 输入不说明有多少个InputBlock 以EOF为结束标志 参见 HDOJ 1089 2020 3 20 27 Hdoj 1089源代码 includeintmain inta b while scanf d d 2020 3 20 28 本类输入解决方案 C语法 while scanf d d a b EOF C 语法 while cin a b 2020 3 20 29 说明 1 Scanf函数返回值就是读出的变量个数 如 scanf d d 如果只有一个整数输入 返回值是1 如果有两个整数输入 返回值是2 如果一个都没有 则返回值是 1 EOF是一个预定义的常量 等于 1 2020 3 20 30 输入 第二类 输入一开始就会说有N个InputBlock 下面接着是N个InputBlock 参见 HDOJ 1090 2020 3 20 31 Hdoj 1090源代码 includeintmain intn i a b scanf d 2020 3 20 32 本类输入解决方案 C语法 scanf d i 2020 3 20 33 输入 第三类 输入不说明有多少个InputBlock 但以某个特殊输入为结束标志 参见 HDOJ 1091 2020 3 20 34 Hdoj 1091源代码 includeintmain inta b while scanf d d 上面的程序有什么问题 2020 3 20 35 本类输入解决方案 C语法 while scanf d n n 0 C 语法 while cin n n 0 2020 3 20 36 输入 第四类 以上几种情况的组合 2020 3 20 37 输入 第五类 输入是一整行的字符串的参见 HDOJ 1048 2020 3 20 38 本类输入解决方案 C语法 charbuf 20 gets buf C 语法 如果用stringbuf 来保存 getline cin buf 如果用charbuf 255 来保存 cin getline buf 255 2020 3 20 39 说明 5 1 scanf s s str1 str2 在多个字符串之间用一个或多个空格分隔 若使用gets函数 应为gets str1 gets str2 字符串之间用回车符作分隔 通常情况下 接受短字符用scanf函数 接受长字符用gets函数 而getchar函数每次只接受一个字符 经常c getchar 这样来使用 2020 3 20 40 说明 5 2 cin getline的用法 getline是一个函数 它可以接受用户的输入的字符 直到已达指定个数 或者用户输入了特定的字符 它的函数声明形式 函数原型 如下 istream不用管它的返回类型 来关心它的三个参数 charline 就是一个字符数组 用户输入的内容将存入在该数组内 intsize 最多接受几个字符 用户超过size的输入都将不被接受 charendchar 当用户输入endchar指定的字符时 自动结束 默认是回车符 2020 3 20 41 说明 5 2 续 结合后两个参数 getline可以方便地实现 用户最多输入指定个数的字符 如果超过 则仅指定个数的前面字符有效 如果没有超过 则用户可以通过回车来结束输入 charname 4 cin getline name 4 n 由于endchar默认已经是 n 所以后面那行也可以写成 cin getline name 4 2020 3 20 42 思考 以下题目属于哪一类输入 2020 3 20 43 输出 第一类 一个InputBlock对应一个OutputBlock OutputBlock之间没有空行 参见 HDOJ 1089 2020 3 20 44 解决方案 C语法 printf d n ans C 语法 cout ans endl 2020 3 20 45 输出 第二类 一个InputBlock对应一个OutputBlock 每个OutputBlock之后都有空行 参见 HDOJ 1095 2020 3 20 46 1095源代码 includeintmain inta b while scanf d d 2020 3 20 47 解决办法 C语法 printf d n n ans C 语法 cout ans endl endl 2020 3 20 48 输出 第三类 一个InputBlock对应一个OutputBlock OutputBlock之间有空行 参见 HDOJ 1096 2020 3 20 49 1096源代码 includeintmain inticase n i j a sum scanf d 2020 3 20 50 解决办法 C语法 for k 0 k count k while printf d n result if k count 1 printf n C 语法 类似 输出语句换一下即可 2020 3 20 51 思考 以下题目属于哪一类输出 2020 3 20 52 附 初学者常见问题 2020 3 20 53 一 编译错误 Main函数必须返回int类型 正式比赛 不要在for语句中定义类型 int64不支持 可以用longlong代替使用了汉语的标点符号itoa不是ansi函数能将整数转换为字符串而且与ANSI标准兼容的方法是使用sprintf 函数intnum 100 charstr 25 sprintf str d num 另外 拷贝程序容易产生错误 2020 3 20 54 下面的hdoj1089为什么CE includeintmain inta b while scanf d d 2020 3 20 55 二 小技巧 数据的拷贝 特别是输出的提示信息 调试的sampleinput的拷贝 2020 3 20 56 三 C语言处理 混合数据 的问题 例题 Hdoj 1170 2020 3 20 57 常见的代码 scanf d n 2020 3 20 58 有什么问题 2020 3 20 59 四 Printf和cout混用的问题 以下的程序输出什么 include includeintmain intj 0 for j 0 j 5 j cout j printf d n j return0 2020 3 20 60 为什么 一个带缓冲输出 cout 一个不带缓冲输出 printf 2020 3 20 61 五 输入输出原理 Input15261020111111321123 Output6830222444 2020 3 20 62 思考题 目的 初步体会一下ACM的魅力 Giventwonon negativeintegersmandn youwillhavetofindthelastdigitofmnindecimalnumbersystem InputTheinputfilecontainsseverallines Eachlinecontainstwointegersmandn bothlessthan101001 Inputisterminatedbyalinecontainingtwozeroes Thislineshouldnotbeprocessed OutputForeachsetofinputyoumustproduceonelineofoutputwhichcontainsasingledigit Thisdigitisthelastdigitofmn SampleInput323500SampleOutput93 2020 3 20 63 授课方式与成绩评定 介绍常用算法举例分析上机练习 自己在线练习 成绩评定 机试 5 6题 2020 3 20 64 相关资料 数学知识离散 组合数论 图论计算几何算法 数据结构基本数据结构搜索 分治动态规划贪心 2020 3 20 65 学习方式 练习 总结 练习 总结 杭电ACM论坛google baidu 2020 3 20 66 去哪里练习 2020 3 20 67 常见问题 1 需要什么基础 C C 4 可以退课吗 Ofcourse 3 如何加入集训队 200 申请 2 英语不好怎么办 问题不大 2020 3 20 68 想对大家说的话 2020 3 20 69 课后任务 1 熟悉2 完成在线练习 ACMProgramming Exercise 1 3 学有余力 可以尝试下面题目 1016 1018 1013 10611170 2000 2043 2020 3 20 70 Seeyounextweek