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

1、ACM程序设计程序设计2021/8/142每周一星（每周一星（4）：）：axie2021/8/143第第五五讲讲筛选法及预处理筛选法及预处理（附（附- -菜鸟的菜鸟的2222个经典错误）个经典错误）2021/8/144例例1-素数判断素数判断n题目描述：给定一个N（1N100000），请判断N是否是素数，如果是素数，则请输出YES，否则输出NO。nSample Input：45nSample Output:NOYES2021/8/145常见朴素算法常见朴素算法n#includenint main()nnint i,n;nwhile(scanf(%d,&n)=1)nfor(i=2;in;

2、i+)n if(n%i=0) break; nif(i=n) printf(YESn);nelse printf(NOn);nn2021/8/146朴素算法优化版本朴素算法优化版本n#includen#includenint main()nint i,n,x;nwhile(scanf(%d,&n)=1)nx=(int)sqrt(n);nfor(i=2;ix) printf(YESn);nelse printf(NOn);nn2021/8/147例例2-求所有素数求所有素数n题目描述：给定一个N（1N100000），请按照递增次序输出所有小于等于N的素数。nSample Input：10

3、nSample Output:2 3 5 72021/8/148题目分析题目分析n题目特点：不是求一个素数，而是求一段素数（一种常见的情况就是求指定范围的所有的素数）n如果还用常规求素数方法，可能的问题是？2021/8/149筛选法求素数筛选法求素数n基本思想基本思想：素数的倍数一定不是素数n实现方法实现方法：用一个长度为N+1的数组保存信息（0表示素数，1表示非素数），先假设所有的数都是素数（初始化为0），从第一个素数2开始，把2的倍数都标记为非素数（置为1），一直到大于N；然后进行下一趟，找到2后面的下一个素数3，进行同样的处理，直到最后，数组中依然为0的数即为素数。n说明：整数1特殊处理

4、即可。2021/8/1410效果演示效果演示0 000000 000000 000000 01 15 54 43 32 26 67 7111110109 98 81212 131317171616151514142021/8/1411效果演示效果演示0 001000 000000 000000 01 15 54 43 32 26 67 7111110109 98 81212 131317171616151514142021/8/1412效果演示效果演示0 001001 000000 000000 01 15 54 43 32 26 67 7111110109 98 81212 13131717

5、1616151514142021/8/1413效果演示效果演示0 001001 000010 000000 01 15 54 43 32 26 67 7111110109 98 81212 131317171616151514142021/8/1414效果演示效果演示0 001001 001011 001010 01 15 54 43 32 26 67 7111110109 98 81212 131317171616151514142021/8/1415效果演示效果演示0 001001 001111 001110 01 15 54 43 32 26 67 7111110109 98 81212

6、 131317171616151514142021/8/1416效果演示效果演示0 001001 001111 001110 01 15 54 43 32 26 67 7111110109 98 81212 131317171616151514142021/8/1417效果演示效果演示0 001001 001111 001110 01 15 54 43 32 26 67 7111110109 98 81212 131317171616151514142021/8/1418效果演示效果演示0 001001 001111 001110 01 15 54 43 32 26 67 7111110109

7、 98 81212 131317171616151514142021/8/1419参考代码（筛选法）参考代码（筛选法）n#includen#includenint a100001;nint main()n int i,j,n;nwhile(scanf(%d,&n)=1)nfor(i=2;i=n;i+)nif(ai=0)nfor(j=i+i;j=n;j+=i)naj=1; nprintf(2);nfor(i=3;i=n;i+)nif(ai=0) printf( %d,i); nprintf(n); nreturn 0; 2021/8/1420思考思考-常规筛选法的改进？常规筛选法的改进？

8、n#includen#includenint a100001;nint main()n int i,j,n;nwhile(scanf(%d,&n)=1)nfor(i=2;i=n;i+)nif(ai=0)nfor(j=i+i;j=n;j+=i)naj=1; nprintf(2);nfor(i=3;i=n;i+)nif(ai=0) printf( %d,i); nprintf(n); nreturn 0; 2021/8/1421例例3-求素数个数求素数个数n题目描述：给定一个N（1N100000），请输出小于等于N的素数的个数。n测试数据有C组，（1C100000）.nSample Inp

9、ut：10nSample Output:42021/8/1422常规筛选法代码常规筛选法代码n#includen#includenint a100001;nint main()nint i,j,n,count;n while(scanf(%d,&n)=1)n count=0;nfor(i=2;i=n;i+)nif(ai=0)nfor(j=i+i;j=n;j+=i)naj=1; nfor(i=2;i=n;i+)nif(ai=0) ncount+;nprintf(%dn,count); nreturn 0; n2021/8/1423题目分析题目分析(1)n题目特点：数据量超大！n分析：前面

10、算法的瓶颈：每组数据都求素数.n如何改进以加快求解速度？n可否一次筛选，多次查找？n这就是预处理思想2021/8/1424预处理参考代码预处理参考代码n#includen#includenint a100001;nint main()nint i,j,n,count;nfor(i=2;i=100000;i+)nif(ai=0)nfor(j=i+i;j=100000;j+=i)naj=1; nwhile(scanf(%d,&n)=1)n count=0;nfor(i=2;i=n;i+)nif(ai=0) ncount+;nprintf(%dn,count); nreturn 0; n20

11、21/8/1425题目分析题目分析(2)n相对之前，算法有否改进；n但依然风险很大n哪个地方依然影响效率？n如何改进？n请自己完成n再思考再思考:若求某一段数中素数的个数呢若求某一段数中素数的个数呢?2021/8/1426筛选法思想的其他应用筛选法思想的其他应用n1215 七夕节n题目大意：求一个数的真因子之和nSample Input：n2n10n20Sample Output：n8n222021/8/1427题目分析题目分析n本题特点同前例题：数据量很大（可达50万），每个数据也不小，同样可达50万。n常见方法：预处理筛法n思考：这个筛法和求素数的筛法细节区别在哪里？n再思考：如果是求一个

12、数的因子的数量，哪里需要变化？2021/8/14281215参考代码参考代码n略 :)2021/8/1429菜鸟的菜鸟的2222个经典错误个经典错误.2021/8/1430以以1089 A1089 AB B为例为例nSample Inputn1 5n10 20nSample Outputn6n302021/8/1431菜鸟之伤（菜鸟之伤（1 1）n#includenvoid main()nnint a,b;nscanf(“%d%d”,&a,&b);nprintf(“%dn”,a+b);n2021/8/1432菜鸟之伤（菜鸟之伤（1 1）n总结：程序不能处理多组数据的问题是最常见

13、的入门问题，只要掌握几种常见的类型，就可以轻松掌握了，具体处理方法曾在第一次课件有详细描述，这里省略了2021/8/1433菜鸟之伤（菜鸟之伤（2 2）n#includenvoid main()nnint a,b;nwhile(scanf(“%d%d”,&a,&b)!=0)nprintf(“%dn”,a+b);n2021/8/1434菜鸟之伤（菜鸟之伤（2 2）n总结：文件结束符EOF的值是-1而不是0，所以while(scanf()!=0)常常会因为死循环而造成TLE，这个必须牢记。n说明：不仅仅菜鸟，很多老鸟也常常因为不注意这点而犯错误，而且还常常因为想不到会犯这种低级错误

14、而想不到原因。2021/8/1435菜鸟之伤（菜鸟之伤（3 3）n#includenvoid main()nnint a,b;nwhile(scanf(“%d%d”,&a,&b)!=EOF);nprintf(“%dn”,a+b);n2021/8/1436菜鸟之伤（菜鸟之伤（3 3）n总结：while 或者 for循环的条件外面误加了分号，编译不影响，但是结果循环体没有真正得到多次执行；n说明：菜鸟常犯的错误，往往因为编译能通过而不能迅速察觉，尤其比赛中n提醒：提醒：当你将scanf();语句加上while循环以处理多组数据问题的时候尤其注意因为之前有分号，很容易忘记去掉！202

15、1/8/1437菜鸟之伤（菜鸟之伤（4 4）n#includenvoid main()nnint a,b;nwhile(scanf(“%d%d”,&a,&b) =2)nprintf(“%dn”,a+b);n2021/8/1438菜鸟之伤（菜鸟之伤（4 4）n总结：C语言中，赋值符号和判断是否相等的逻辑符号具有完全不同的含义，往往因为我们的习惯问题，在编程中误将判断是否相等的逻辑符号写成赋值符号。同样的，这种失误也会因为不影响编译而影响查错的时间。n说明：菜鸟常犯的错误，但是有过几次教训就会牢记了，呵呵2021/8/1439以以1001 Sum Problem1001 Sum P

16、roblem为例为例nSample Inputn1n100nSample Outputn1n50502021/8/1440菜鸟之伤（菜鸟之伤（5 5）#includevoid main() int i,n,s; while(scanf(“%d”,&n) =1) for(i=1;i=n;i+) s+=i; printf(“%dnn”,s); 2021/8/1441菜鸟之伤（菜鸟之伤（5 5）n总结：忘记变量的初始化是典型的菜鸟问题，不必紧张，多经历几次就牢记了n说明：普通变量的初始化还比较容易查找，而用来保存计算结果的数组的初始化更是容易忘记！2021/8/1442菜鸟之伤（菜鸟之伤（6

17、 6）#includevoid main() int i,n,s=0; while(scanf(“%d”,&n) =1) for(i=1;i=n;i+) s+=i; printf(“%dnn”,s); 2021/8/1443菜鸟之伤（菜鸟之伤（6 6）n总结：变量初始化放在循环外，是一个典型的ACM初级错误，因为ACM赛题的多组测试特性，如果不能在循环内初始化，将只能确保第一组数据没问题，而很多入门者习惯只测试一组数据，很容易忽略这个问题。nn说明：菜鸟常犯的错误，关键是要理解为什么这样会有问题，真正理解后，修改也就不难了。2021/8/1444菜鸟之伤（菜鸟之伤（7 7）n#incl

18、udenvoid main()nint i,n,s;nwhile(scanf(“%d”,&n) =1)nns=n*(n+1)/2;nprintf(“%dnn”,s);nn2021/8/1445菜鸟之伤（菜鸟之伤（7 7）n总结：数组越界还能在提交后收到Runtime Error的信息反馈，而运算中的数据溢出则往往只能收到Wrong Answer的错误提示，所以这种错误往往容易被误导成算法问题；n说明：不仅菜鸟，就是大牛甚至大神，也常常犯这种错误，只是情况复杂些而已2021/8/1446菜鸟之伤（菜鸟之伤（8 8）n#includenvoid main()nint i,n,s;nwhil

19、e(scanf(“%d”,&n) =1)nns=n/2*(n+1);nprintf(“%dnn”,s);nn2021/8/1447菜鸟之伤（菜鸟之伤（8 8）n总结：当两个整数进行运算的时候，运算结果一定还是整数，所以不要因为常规数学惯性思维的影响而认为结果可能为浮点数；而不同数据类型一同运算的时候，运算结果的数据类型和相对复杂的类型一致（比如 整数+实数，结果类型是实数）2021/8/1448菜鸟之伤（菜鸟之伤（9 9）n#includenvoid main()nint i,n,s;n while(scanf(“%d”,&n) =1)n if(n%2=0)n s=n/2*(n

20、+1);n elsen s=(n+1)/2*n;n printf(“%dnn”,s);n2021/8/1449菜鸟之伤（菜鸟之伤（9 9）n总结：写for或者while等任何循环语句的时候，不管循环体内有几个语句，务必养成都加上一对大括号的好习惯。n常常碰到的情况是这样的本来循环体内只有一条语句，确实不用大括号，但是在修改程序的过程中，循环体内增加了其他语句，而这时却忘记了添加大括号！n所以说好习惯很重要！2021/8/1450菜鸟之伤（菜鸟之伤（1010）n#includenvoid main()nint i,n,s;n while(scanf(“%d”,&n) =1)n if(n%

21、2=0)n s=n/2*(n+1);n elsen s=(n+1)/2*n; n printf(“%dnn”,s);n2021/8/1451菜鸟之伤（菜鸟之伤（1010）n总结：这也是一个经典错误，虽然为循环体加了大括号，但是并没有包含全部的信息，造成的后果是只有一次输出尽管对于每组数据都处理了，但是只输出最后一组结果。n由于很多同学习惯每次只测试一组数据，就更容易忽略这个错误了.n再次证明再次证明好习惯很重要！好习惯很重要！2021/8/1452菜鸟之伤（菜鸟之伤（1111）n假设不会中间溢出，下面的程序是否有问题？n#includenvoid main()nint i,n,s;n whil

22、e(scanf(“%d”,&n) =1)n n s=n(n+1)/2;n printf(“%dnn”,s);n n2021/8/1453菜鸟之伤（菜鸟之伤（1111）n总结：这也是受数学习惯影响而可能出现的一个错误，当然，这个错误很好检查，因为编译不能通过的n总结出这个只是因为确实会出现这个情况，而对于极度没有编程经验的同学来说，有时候也会带来困扰2021/8/1454还是以还是以A AB B为例为例n题目描述：计算AB的值，输入数据每行包含2个正整数，如果输入数据是两个负数，则结束输入。nSample Inputn1 5n-1 -1nSample Outputn62021/8/145

23、5菜鸟之伤（菜鸟之伤（1212）n#includenvoid main()nnint a,b;nwhile(scanf(“%d%d”,&a,&b)=2)n if(a=-1 & b=-1) return;n printf(“%dn”,a+b);n2021/8/1456菜鸟之伤（菜鸟之伤（1212）n总结：正如判断相等要用“=”一样，C语言中进行逻辑与的运算也是需要两个字符“&”，类似的逻辑或运算也是两个字符“|”，如果是单个的字符，含义就完全不同了2021/8/1457菜鸟之伤（菜鸟之伤（1313）n上一个程序的改进版：上一个程序的改进版：n#includenvo

24、id main()nnint a,b;nwhile(scanf(“%d%d”,&a,&b)=2)n if(a=-1 & b=-1) return;n printf(“%dn”,a+b);n2021/8/1458菜鸟之伤（菜鸟之伤（1313）n总结：题目描述是负数结束输入，Sample Input最后给出的是-1，如果读题不仔细，很容易陷入思维定势，而会不加思索在程序中用-1判断，这样就真的会发生不幸的事件尽管我也认为这个陷阱有点阴，而且未必有很大意义，但是题目并没错，而你确实读题不仔细n说明：算是经典的小陷阱，现在很少出现了2021/8/1459继续以继续以A AB B

25、为例为例n题目描述：给定2个整数A和B，如果A+B0，请输出”OK!”，否则请输出”No”nSample Inputn1 5n1 -5nSample OutputnOK!nNo2021/8/1460菜鸟之伤（菜鸟之伤（1414）n#includenvoid main()nnint a,b;nwhile(scanf(“%d%d”,&a,&b)=2)n if(a+b0) printf(“OK!n”);n else printf(“NOn”); n2021/8/1461菜鸟之伤（菜鸟之伤（1414）n总结：字符串输出的大小写问题对于菜鸟需要特别注意，其实，不管是全大写、全小写，还是首

26、字母大写，你尽管复制即可（没有电子版，另当别论），当然还要注意是否有标点符号等情况。n说明：菜鸟常犯错误，稍有经验即可避免2021/8/1462以以11701170Balloon Comes!为例为例nSample Inputn4n+ 1 2n- 1 2n* 1 2n/ 1 2nSample Outputn3n-1n2n0.502021/8/1463菜鸟之伤（菜鸟之伤（1515）nint n,a,b,i;nchar p;nscanf(%d,&n);nfor (i=0;in;i+)nn scanf(%c%d%d,&p,&a,&b);n if( ) n2021/8/

27、1464菜鸟之伤（菜鸟之伤（1515）n刚才程序的改进版刚才程序的改进版: :nint n,a,b,i;nchar p;nscanf(%d,&n);ngetchar();nfor (i=0;in;i+)nn scanf(%c%d%d,&p,&a,&b);n if( .) nn是否还有问题？如何修改？是否还有问题？如何修改？2021/8/1465菜鸟之伤（菜鸟之伤（1515）n总结：字符和数字的混合输入带来的问题，也是一个常常困扰使用C语言编程的同学的经典问题，关键就是程序未能及时接收回车符，而误将回车当作下一组数据的首字母，你可以通过添加一句getchar();

28、 轻松解决该问题。n说明：菜鸟的经典错误，如果之前没有遇到过，很难一下子反应过来，当然，遇到一次以后就不成为问题了2021/8/14662007 2007 平方和与立方和平方和与立方和n给定一段连续的整数，求出他们中所有偶数的平方和以及所有奇数的立方和。nSample Inputn1 3n2 5nSample Outputn4 28n20 1522021/8/1467菜鸟之伤（菜鸟之伤（1616）#includevoid main() int m,n; while(scanf(“%d%d” ,&m,&n) =2) int i,x=0,y=0; for(i=m;i=n;i+) i

29、f(i%2=0) y=y+i*i; else x=x+i*i*i; printf(“%d %dn”,y,x); 2021/8/1468菜鸟之伤（菜鸟之伤（1616）n总结：题目并没有保证数据是递增的，但人往往有思维定势，而很多题目的设计就是针对这一点！不要埋怨，这种训练能很好的培养我们审慎的思维习惯。n说明：这种错误经历过以后还是比较容易牢记的，所以说有时候经验很重要。2021/8/1469菜鸟之伤（菜鸟之伤（1717）n以下的程序输出什么？n#includen#includenint main()nnint j=0;nfor(j=0;j5;j+)nncoutj=;nprintf(%dn,j)

30、;nnreturn 0;n2021/8/1470菜鸟之伤（菜鸟之伤（1717）n 期望输出：nj=0nj=1nj=2nj=3nj=4n 实际输出：n?2021/8/1471菜鸟之伤（菜鸟之伤（1717）n总结：在一个程序中同时使用C和C+的输出语句，很容易带来问题，原因就是输出机制不完全一样（一个不带缓冲，一个带缓冲），所以尽量避免C和C+输出语句混用。n说明：这是传说中的经典错误，据说曾困扰某牛人于现场赛 :-)2021/8/1472以以2004 2004 成绩转换成绩转换 为例为例n题目描述：题目描述：输入一个百分制的成绩t，将其转换成对应的等级，具体转换规则如下： 90100为A; 80

31、89为B; 7079为C; 6069为D; 059为E;n输出描述：输出描述：对于每组输入数据，输出一行。如果输入数据不在0100范围内，请输出一行：“Score is error!”。2021/8/1473菜鸟之伤（菜鸟之伤（1818）n#includenint main()n int t,a;n while(scanf(%d,&t)!=EOF)n if(t100|t0) printf(Score is error!n);n elsen a=(t-50)/10;n switch(a)n case 5:n case 4:printf(An); case 3:printf(Bn);n c

32、ase 2:printf(Cn); case 1:printf(Dn);n default:printf(En); n n return 0;n 2021/8/1474菜鸟之伤（菜鸟之伤（1818）n总结：C语言中的case语句要求在每个case的处理后面都要跟break；（特殊需求除外），而如果因为不了解或者不小心而缺少部分break;则执行的效果也许会不符合你最初的设计。n说明：C语言的基本功很重要2021/8/1475以以2046 2046 骨牌铺方格骨牌铺方格 为例为例n题目描述：题目描述：在2n的一个长方形方格中,用一个1 2的骨牌铺满方格,输入n ,输出铺放方案的总数.n输入描述：

33、输入描述：输入数据由多行组成，每行包含一个整数n,表示该测试实例的长方形方格的规格是2n (0n=50)。2021/8/1476菜鸟之伤（菜鸟之伤（1919）n#includenint main()nn int i;n _int64 a50=0,1,2;n for(i=3;i=50;i+)n ai=ai-1+ai-2;n while(scanf(%d,&i)!=EOF)n printf(%I64dn,ai); n n2021/8/1477菜鸟之伤（菜鸟之伤（1919）n总结：数组下标越界是最常见的Runtime Error，也是菜鸟常犯的错误，除了需要扎实的C语言基本功，编程中的注意力

34、集中也是需要的（很多时候不是不知道理论，而是不注意）n说明：一般情况，你可以通过将数组开的大点而尽量避免这个问题2021/8/1478以以1425 Sort1425 Sort为例为例n题目描述：题目描述：给你n个整数，请按从大到小的顺序输出其中前m大的数。n输入描述：输入描述：每组测试数据有两行，第一行有两个数n,m(0n,m1000000)，第二行包含n个各不相同，且都处于区间-500000,500000的整数。2021/8/1479菜鸟之伤（菜鸟之伤（2020）n#includenvoid main()nn int n,m,i,num1000000;n while(scanf(“%d%d”,&n,&m)=2)n . n2021/8/1480菜鸟之伤（菜鸟之伤（2020）n总结：ACM编程中，使用很大的数组是很常见的做法，但如果超大的数组被定义成局部变量，则很容易出现Runtime Error，解决办法也很简单：定义成全局变量即可。原因是局部变量分配在栈（较小），全局变量分配在堆（较大）；n说明：这里所说的超大也不能无限制的大，可以根据题目的内存限制进行估算2021/8/14