(HDUACM2012版_05)筛选法及预处理(附菜鸟的22个经典错误)

ACM程序设计 杭州电子科技大学刘春英acm 4 6 2020 2 每周一星 4 axie 4 6 2020 3 第五讲 筛选法及预处理 附 菜鸟的22个经典错误 4 6 2020 4 例1 素数判断 题目描述 给定一个N 1 N 100000 请判断N是否是素数 如果是素数 则请输出YES 否则输出NO SampleInput 45SampleOutput NOYES 4 6 2020 5 常见朴素算法 includeintmain inti n while scanf d 4 6 2020 6 朴素算法优化版本 include includeintmain inti n x while scanf d 4 6 2020 7 例2 求所有素数 题目描述 给定一个N 1 N 100000 请按照递增次序输出所有小于等于N的素数 SampleInput 10SampleOutput 2357 4 6 2020 8 题目分析 题目特点 不是求一个素数 而是求一段素数 一种常见的情况就是求指定范围的所有的素数 如果还用常规求素数方法 可能的问题是 4 6 2020 9 筛选法求素数 基本思想 素数的倍数一定不是素数实现方法 用一个长度为N 1的数组保存信息 0表示素数 1表示非素数 先假设所有的数都是素数 初始化为0 从第一个素数2开始 把2的倍数都标记为非素数 置为1 一直到大于N 然后进行下一趟 找到2后面的下一个素数3 进行同样的处理 直到最后 数组中依然为0的数即为素数 说明 整数1特殊处理即可 4 6 2020 10 效果演示 4 6 2020 11 效果演示 4 6 2020 12 效果演示 4 6 2020 13 效果演示 4 6 2020 14 效果演示 4 6 2020 15 效果演示 4 6 2020 16 效果演示 4 6 2020 17 效果演示 4 6 2020 18 效果演示 4 6 2020 19 参考代码 筛选法 include includeinta 100001 intmain inti j n while scanf d 4 6 2020 20 思考 常规筛选法的改进 include includeinta 100001 intmain inti j n while scanf d 4 6 2020 21 例3 求素数个数 题目描述 给定一个N 1 N 100000 请输出小于等于N的素数的个数 测试数据有C组 1 C 100000 SampleInput 10SampleOutput 4 4 6 2020 22 常规筛选法代码 include includeinta 100001 intmain inti j n count while scanf d 4 6 2020 23 题目分析 1 题目特点 数据量超大 分析 前面算法的瓶颈 每组数据都求素数 如何改进以加快求解速度 可否一次筛选 多次查找 这就是预处理思想 4 6 2020 24 预处理参考代码 include includeinta 100001 intmain inti j n count for i 2 i 100000 i if a i 0 for j i i j 100000 j i a j 1 while scanf d 4 6 2020 25 题目分析 2 相对之前 算法有否改进 但依然风险很大 哪个地方依然影响效率 如何改进 请自己完成 再思考 若求某一段数中素数的个数呢 4 6 2020 26 筛选法思想的其他应用 1215七夕节题目大意 求一个数的真因子之和SampleInput 21020SampleOutput 822 4 6 2020 27 题目分析 本题特点同前例题 数据量很大 可达50万 每个数据也不小 同样可达50万 常见方法 预处理筛法思考 这个筛法和求素数的筛法细节区别在哪里 再思考 如果是求一个数的因子的数量 哪里需要变化 4 6 2020 28 1215参考代码 略 4 6 2020 29 菜鸟的22个经典错误 4 6 2020 30 以1089A B为例 SampleInput151020SampleOutput630 4 6 2020 31 菜鸟之伤 1 includevoidmain inta b scanf d d 4 6 2020 32 菜鸟之伤 1 总结 程序不能处理多组数据的问题是最常见的入门问题 只要掌握几种常见的类型 就可以轻松掌握了 具体处理方法曾在第一次课件有详细描述 这里省略了 4 6 2020 33 菜鸟之伤 2 includevoidmain inta b while scanf d d 4 6 2020 34 菜鸟之伤 2 总结 文件结束符EOF的值是 1而不是0 所以while scanf 0 常常会因为死循环而造成TLE 这个必须牢记 说明 不仅仅菜鸟 很多老鸟也常常因为不注意这点而犯错误 而且还常常因为想不到会犯这种低级错误而想不到原因 4 6 2020 35 菜鸟之伤 3 includevoidmain inta b while scanf d d 4 6 2020 36 菜鸟之伤 3 总结 while或者for循环的条件外面误加了分号 编译不影响 但是结果循环体没有真正得到多次执行 说明 菜鸟常犯的错误 往往因为编译能通过而不能迅速察觉 尤其比赛中 提醒 当你将scanf 语句加上while循环以处理多组数据问题的时候尤其注意 因为之前有分号 很容易忘记去掉 4 6 2020 37 菜鸟之伤 4 includevoidmain inta b while scanf d d 4 6 2020 38 菜鸟之伤 4 总结 C语言中 赋值符号 和判断是否相等的逻辑符号 具有完全不同的含义 往往因为我们的习惯问题 在编程中误将判断是否相等的逻辑符号写成赋值符号 同样的 这种失误也会因为不影响编译而影响查错的时间 说明 菜鸟常犯的错误 但是有过几次教训就会牢记了 呵呵 4 6 2020 39 以1001SumProblem为例 SampleInput1100SampleOutput15050 4 6 2020 40 菜鸟之伤 5 includevoidmain inti n s while scanf d 4 6 2020 41 菜鸟之伤 5 总结 忘记变量的初始化是典型的菜鸟问题 不必紧张 多经历几次就牢记了 说明 普通变量的初始化还比较容易查找 而用来保存计算结果的数组的初始化更是容易忘记 4 6 2020 42 菜鸟之伤 6 includevoidmain inti n s 0 while scanf d 4 6 2020 43 菜鸟之伤 6 总结 变量初始化放在循环外 是一个典型的ACM初级错误 因为ACM赛题的多组测试特性 如果不能在循环内初始化 将只能确保第一组数据没问题 而很多入门者习惯只测试一组数据 很容易忽略这个问题 说明 菜鸟常犯的错误 关键是要理解为什么这样会有问题 真正理解后 修改也就不难了 4 6 2020 44 菜鸟之伤 7 includevoidmain inti n s while scanf d 4 6 2020 45 菜鸟之伤 7 总结 数组越界还能在提交后收到RuntimeError的信息反馈 而运算中的数据溢出则往往只能收到WrongAnswer的错误提示 所以这种错误往往容易被误导成算法问题 说明 不仅菜鸟 就是大牛甚至大神 也常常犯这种错误 只是情况复杂些而已 4 6 2020 46 菜鸟之伤 8 includevoidmain inti n s while scanf d 4 6 2020 47 菜鸟之伤 8 总结 当两个整数进行运算的时候 运算结果一定还是整数 所以不要因为常规数学惯性思维的影响而认为结果可能为浮点数 而不同数据类型一同运算的时候 运算结果的数据类型和相对复杂的类型一致 比如整数 实数 结果类型是实数 4 6 2020 48 菜鸟之伤 9 includevoidmain inti n s while scanf d 4 6 2020 49 菜鸟之伤 9 总结 写for或者while等任何循环语句的时候 不管循环体内有几个语句 务必养成都加上一对大括号的好习惯 常常碰到的情况是这样的 本来循环体内只有一条语句 确实不用大括号 但是在修改程序的过程中 循环体内增加了其他语句 而这时却忘记了添加大括号 所以说 好习惯很重要 4 6 2020 50 菜鸟之伤 10 includevoidmain inti n s while scanf d 4 6 2020 51 菜鸟之伤 10 总结 这也是一个经典错误 虽然为循环体加了大括号 但是并没有包含全部的信息 造成的后果是只有一次输出 尽管对于每组数据都处理了 但是只输出最后一组结果 由于很多同学习惯每次只测试一组数据 就更容易忽略这个错误了 再次证明 好习惯很重要 4 6 2020 52 菜鸟之伤 11 假设不会中间溢出 下面的程序是否有问题 includevoidmain inti n s while scanf d 4 6 2020 53 菜鸟之伤 11 总结 这也是受数学习惯影响而可能出现的一个错误 当然 这个错误很好检查 因为编译不能通过的 总结出这个只是因为确实会出现这个情况 而对于极度没有编程经验的同学来说 有时候也会带来困扰 4 6 2020 54 还是以A B为例 题目描述 计算A B的值 输入数据每行包含2个正整数 如果输入数据是两个负数 则结束输入 SampleInput15 1 1SampleOutput6 4 6 2020 55 菜鸟之伤 12 includevoidmain inta b while scanf d d 4 6 2020 56 菜鸟之伤 12 总结 正如判断相等要用 一样 C语言中进行逻辑与的运算也是需要两个字符 类似的逻辑或运算也是两个字符 如果是单个的字符 含义就完全不同了 4 6 2020 57 菜鸟之伤 13 上一个程序的改进版 includevoidmain inta b while scanf d d 4 6 2020 58 菜鸟之伤 13 总结 题目描述是负数结束输入 SampleInput最后给出的是 1 如果读题不仔细 很容易陷入思维定势 而会不加思索在程序中用 1判断 这样就真的会发生不幸的事件 尽管我也认为这个陷阱有点阴 而且未必有很大意义 但是题目并没错 而你确实读题不仔细 说明 算是经典的小陷阱 现在很少出现了 4 6 2020 59 继续以A B为例 题目描述 给定2个整数A和B 如果A B 0 请输出 OK 否则请输出 No SampleInput151 5SampleOutputOK No 4 6 2020 60 菜鸟之伤 14 includevoidmain inta b while scanf d d 4 6 2020 61 菜鸟之伤 14 总结 字符串输出的大小写问题对于菜鸟需要特别注意 其实 不管是 全大写 全小写 还是首字母大写 你尽管复制即可 没有电子版 另当别论 当然还要注意是否有标点符号等情况 说明 菜鸟常犯错误 稍有经验即可避免 4 6 2020 62 以1170BalloonComes 为例 SampleInput4 12 12 12 12 SampleOutput3 120 50 4 6 2020 63 菜鸟之伤 15 intn a b i charp scanf d if 4 6 2020 64 菜鸟之伤 15 刚才程序的改进版 intn a b i charp scanf d if 是否还有问题 如何修改 4 6 2020 65 菜鸟之伤 15 总结 字符和数字的混合输入带来的问题 也是一个常常困扰使用C语言编程的同学的经典问题 关键就是程序未能及时接收回车符 而误将回车当作下一组数据的首字母 你可以通过添加一句getchar 轻松解决该问题 说明 菜鸟的经典错误 如果之前没有遇到过 很难一下子反应过来 当然 遇到一次以后就不成为问题了 4 6 2020 66 2007平方和与立方和 给定一段连续的整数 求出他们中所有偶数的平方和以及所有奇数的立方和 SampleInput1325SampleOutput42820152 4 6 2020 67 菜鸟之伤 16 includevoidmain intm n while scanf d d 4 6 2020 68 菜鸟之伤 16 总结 题目并没有保证数据是递增的 但人往往有思维定势 而很多题目的设计就是针对这一点 不要埋怨 这种训练能很好的培养我们审慎的思维习惯 说明 这种错误经历过以后还是比较容易牢记的 所以说有时候经验很重要 4 6 2020 69 菜鸟之伤 17 以下的程序输出什么 include includeintmain intj 0 for j 0 j 5 j cout j printf d n j return0 4 6 2020 70 菜鸟之伤 17 期望输出 j 0j 1j 2j 3j 4 实际输出 4 6 2020 71 菜鸟之伤 17 总结 在一个程序中同时使用C和C 的输出语句 很容易带来问题 原因就是输出机制不完全一样 一个不带缓冲 一个带缓冲 所以尽量避免C和C 输出语句混用 说明 这是传说中的经典错误 据说曾困扰某牛人于现场赛 4 6 2020 72 以2004成绩转换为例 题目描述 输入一个百分制的成绩t 将其转换成对应的等级 具体转换规则如下 90 100为A 80 89为B 70 79为C 60 69为D 0 59为E 输出描述 对于每组输入数据 输出一行 如果输入数据不在0 100范围内 请输出一行 Scoreiserror 4 6 2020 73 菜鸟之伤 18 includeintmain intt a while scanf d 4 6 2020 74 菜鸟之伤 18 总结 C语言中的case语句要求在每个case的处理后面都要跟break 特殊需求除外 而如果因为不了解或者不小心而缺少部分break 则执行的效果也许会不符合你最初的设计 说明 C语言的基本功很重要 4 6 2020 75 以2046骨牌铺方格为例 题目描述 在2 n的一个长方形方格中 用一个1 2的骨牌铺满方格 输入n 输出铺放方案的总数 输入描述 输入数据由多行组成 每行包含一个整数n 表示该测试实例的长方形方格的规格是2 n 0 n 50 4 6 2020 76 菜鸟之伤 19 includeintmain inti int64a 50 0 1 2 for i 3 i 50 i a i a i 1 a i 2 while scanf d 4 6 2020 77 菜鸟之伤 19 总结 数组下标越界是最常见的RuntimeError 也是菜鸟常犯的错误 除了需要扎实的C语言基本功 编程中的注意力集中也是需要的 很多时候不是不知道理论 而是不注意 说明 一般情况 你可以通过将数组开的大点而尽量避免这个问题 4 6 2020 78 以1425Sort为例 题目描述 给你n个整数 请按从大到小的顺序输出其中前m大的数 输入描述 每组测试数据有两行 第一行有两个数n m 0 n m 1000000 第二行包含n个各不相同 且都处于区间 500000 500000 的整数 4 6 2020 79 菜鸟之伤 20 includevoidmain intn m i num 1000000 while scanf d d n m 2 4 6 2020 80 菜鸟之伤 20 总结 ACM编程中 使用很大的数组是很常见的做法 但如果超大的数组被定义成局部变量 则很容易出现RuntimeError 解决办法也很简单 定义成全局变量即可 原因是局部变量分配在栈 较小 全局变量分配在堆 较大 说明 这里所说的超大也不能无限制的大 可以根据题目的内存限制进行估算 4 6 2020 81 以2039三角形为例 题目描述 给定三条边 请你判断一下能不能组成一个三角形 输入描述 输入数据第一行包含一个数M 接下有M行 每行一个实例 包含三个正数A B C 其中A B C 1000 输出描述 对于每个测试实例 如果三条边长A B C能组成三角形的话 输出YES 否则NO SampleInput2123222Sam