ACM课件lecture老少皆宜数学题.ppt

ACM程序设计,2020/6/11,2,第二讲,老少皆宜之数学题,2020/6/11,3,今天，,你了吗？,AC,2020/6/11,4,开胃羹（1）,几个常用单词：1、vertex(vertices)顶点2、polygon多边形3、convex凸的4、concave凹的5、segment(线)段（n）;分割（v）,2020/6/11,5,开胃羹（2）,再来几个：1、integer整数2、positive正的3、negative(adj)负的;(n)负数4、factorial(n)阶乘;(adj)因子的，阶乘的5、digital(n)数字;(adj)数字的,2020/6/11,6,ACM数学题特点分析:,题意容易理解算法相对简单（有些很难的！）编程比较容易ACM/ICPC入门练习的好选择下面，分类介绍：,2020/6/11,7,从首届“舜宇”杯说起,2020/6/11,8,比赛背景,由于前一年的邀请赛很多学校没有做出一道题，所以，这次的比赛特意准备了几道简单的题目，目的就是让大多数的学校都能拿个气球回去，也好有个交待，于是有,2020/6/11,9,第一类,傻瓜型,2020/6/11,10,1004:LettheBalloonRise,2020/6/11,11,ProblemDescription,Contesttimeagain!Howexciteditistoseeballoonsfloatingaround.Buttotellyouasecret,thejudgesfavoritetimeisguessingthemostpopularproblem.Whenthecontestisover,theywillcounttheballoonsofeachcolorandfindtheresult.Thisyear,theydecidetoleavethislovelyjobtoyou.,2020/6/11,12,Input,Inputcontainsmultipletestcases.EachtestcasestartswithanumberN(0N=2).,2020/6/11,36,InputInputconsistsofasequenceoflines,eachcontaininganintegern.(n1,000,000).OutputPrintthewordyesif3divideevenlyintoF(n).Printthewordnoifnot.,2020/6/11,37,SampleInput012345,SampleOutputnonoyesnonono,2020/6/11,38,题目分析：,能被3整除的整数的特点？,如果两个数的和能被3整除，这两个数有什么特点？,关于能否被3整除，这两个数一共有多少种组合？,2020/6/11,39,Hdoj_1021程序清单：,#includeintmain()longn;while(scanf(%ld,2020/6/11,40,回到正题大锤搞定,2020/6/11,41,1005:NumberSequence,2020/6/11,42,Anumbersequenceisdefinedasfollows:f(1)=1,f(2)=1,f(n)=(A*f(n-1)+B*f(n-2)mod7.GivenA,B,andn,youaretocalculatethevalueoff(n).,ProblemDescription,2020/6/11,43,InputTheinputconsistsofmultipletestcases.Eachtestcasecontains3integersA,Bandnonasingleline(1=A,B=1000,1=n=100,000,000).Threezerossignaltheendofinputandthistestcaseisnottobeprocessed.OutputForeachtestcase,printthevalueoff(n)onasingleline.,2020/6/11,44,SampleInput1131210000SampleOutput25,2020/6/11,45,题目特点：,这个题目是一个比较典型的ACM竞赛题，尽管在真正的大赛中这个题目可能算比较简单的，但在本次比赛中，本题难度属于中等，可以说，能做出本题的队伍基本都有二等奖以上。但如果不认真分析，有可能会掉入陷阱。,2020/6/11,46,Question:,暴力能解决问题吗？,2020/6/11,47,拒绝暴力,2020/6/11,48,题目分析：,对于这种题目，千万不能蛮干！实际上，有经验的同学看到本题目的数据规模，很快就能知道：这类题目有规律可循。,2020/6/11,49,现在对这题有什么想法,?,2020/6/11,50,第四类,纸老虎型,2020/6/11,51,HDOJ_1071TheArea,2020/6/11,52,SampleInput25.0000005.0000000.0000000.00000010.0000000.00000010.00000010.0000001.0000001.00000014.0000008.222222SampleOutput33.3340.69,2020/6/11,53,第一眼：傻了,2020/6/11,54,再一看,2020/6/11,55,抛物线公式：y=ax2+bx+c,已知三点-a、b、c系数,公式已知-如何求面积？,会简单积分吗？,分析过程：,该你思考了,感觉怎么样？,2020/6/11,57,思考题：,1178Heritagefromfather,2020/6/11,58,FamousHarryPotter,whoseemdtobeanormalandpoorboy,isactuallyawizard.Everythingchangedwhenhehadhisbirthdayoftenyearsold.AhugemancalledHagridfoundHarryandleadhimtoanewworldfullofmagicpower.Ifyouvereadthisstory,youprobablyknowthatHarrysparentshadlefthimalotofgoldcoins.HagridleadHarrytoGringotts(thebankholdupbyGoblins).Andtheysteppedintotheroomwhichstoredthefortunefromhisfather.Harrywasastonishing,coztherewerepilesofgoldcoins.ThewayofpackingthesecoinsbyGoblinswasreallyspecial.Onlyonecoinwasonthetop,andthreecoinsconsistedantrianglewereonthenextlowerlayer.Thethirdlayerhassixcoinswhichwerealsoconsistedantriangle,andsoon.Ontheithlayertherewasantrianglehaveicoinseachedge(totallyi*(i+1)/2).Thewholeheapseemedjustlikeapyramid.Goblinstillknewthetotalnumofthelayers,soitsupyoutohelpHarrytofigureoutthesumofallthecoins.,ProblemDescription,2020/6/11,59,InputTheinputwillconsistofsomecases,eachcasetakesalinewithonlyoneintegerN(0N231).Itendswithasingle0.Output对于每个输入的N,输出一行,采用科学记数法来计算金币的总数(保留三位有效数字),2020/6/11,60,SampleInput130SampleOutput1.00E01.00E1,2020/6/11,61,要点分析：,1、暴力的复杂度是多少？2、哪些陷阱？3、关键在哪？4、顺利应该多长时间？,2020/6/11,62,数学公式:,1、这个大家都会：1+2+3+4+n=n(n+1)/22、这个有些同学忘记了：1*1+2*2+3*3+n*n=n(n+1)(2n+1)/63、合并后得到n(n+1)(n+2)/3,2020/6/11,63,问题一：科学计数法的格式,不知道？eE,用%e:用%.2e,如何实现格式要求？,2020/6/11,64,解决方案,方法一：把输出先输出到字符串，再去掉e之后的0a=(1.0*n*n*n+3.0*n*n+2.0*n)/6.0;sprintf(str,%.2E,a);len=strlen(str);for(i=0;i=4;i+)printf(%c,stri);for(i=6;stri!=0;i+)if(i=len-1|stri!=0)printf(%c,stri);printf(n);,2020/6/11,65,方法二：尾数和指数分开控制格式a=(1.0*n*n*n+3.0*n*n+2.0*n)/6.0;b=log10(a);printf(%.2lf,a/pow(10,b);printf(E%dn,b);,2020/6/11,66,Anyquestion?,2020/6/11,67,课后任务：,1004、1005、1008、1009、106010121014、10191021、10611049、1178、1108、10301071、1597,2020/6/11,68,提示：关于PresentationError的错误,2016输出n个数，用空格隔开常见错误：for(i=1;i=n;i+)printf(“%d“,ai);printf(“n“);最后一个数之后也有空格造成PresentationError错误,2020/6/11,69,解决办法,1、方法一for(i=1;in;i+)printf(“%d“,ai)；printf(“%dn“,ai);,2、方法2for(i=1;i=n;i+)printf(“%d“,ai)；if(in)printf(“n”);printf(“%dn“,ai);,2020/6/11,70,2010水仙花#includeintmain()intm,n,t;inti,j;intflag;inta,b,c;flag=0;,不知道m到n有多少个水仙花数，怎么控制最后一个数后不空格？,2020/6/11,71,while(scanf(%d%d,2020/6/11,72,if(i=j)printf(%d,i);flag=1;,if(i=j)if(flag=1)printf();printf(%d,i);flag=1;,不知道m到n有多少个水仙花数，怎么控制最后一个数后不空格？,2020/6/11,73,if(flag=0)printf(no);printf(n);return0;,2020/6/11,74,下一讲：,递推求解,2020/6/11,75,ThankYou,