ACM程序设计竞赛程序设计竞赛入门入门浙江工业大学浙江工业大学田贤忠田贤忠txzzjut.edu.cn2024/8/1312024/8/132第二讲第二讲数学问题2024/8/133引例：引例：本校OJ 1207http:/acm.zjut.edu.cn/ShowProblem.aspx?ShowID=1207 （相似题）杭电杭电1018，求求n！的位数！的位数 http:/acm.hdu.edu.cn/showproblem.php?pid=1018Inmanyapplicationsverylargeintegersnumbersarerequired.Someoftheseapplicationsareusingkeysforsecuretransmissionofdata,encryption,etc.Inthisproblemyouaregivenanumber,youhavetodeterminethenumberofdigitsinthefactorialofthenumber.2024/8/134InputInputconsistsofseverallinesofintegernumbers.Thefirstlinecontainsanintegern,whichisthenumberofcasestobetested,followedbynlines,oneinteger1m107oneachlineOutputTheoutputcontainsthenumberofdigitsinthefactorialoftheintegersappearingintheinput.Sample Input2 10 20Sample Output7 192024/8/135如何求位数？算出阶乘，循环求位数？ 阶乘怎么存储？ 一定要算出阶乘吗？ n!的位数： (int) log10(n!)+1(int)(log10(1)+log10(2)+log10(3)+log10(n)+12024/8/136代码怎么写？超时问题怎么解决？ 能不能降低计算量？有没有更简便的公式？2024/8/137如果不知道高效的计算公式？(int)(log10(1)+log10(2)+log10(3)+log10(n)对于每个输入的数都要按上述公式计算如何避免重复计算？ 先算小数的位数，在此基础上再算大数。 （1） 每次找最小值？需要存储数据和位数的计算 （2）先把算出的log10存储？2024/8/138计算机程序设计艺术计算机程序设计艺术中给出了另一个公式中给出了另一个公式 n! = sqrt(2*n) * (n/e)n) * (1 + 1/(12*n) + 1/(288*n*n) + O(1/n3) = acos(-1) e = exp(1)两边对两边对10取对数取对数 忽略忽略 log10(1 + 1/(12*n) + 1/(288*n*n) + O(1/n3) log10(1) = 0 得到公式得到公式 log10(n!) = log10(sqrt(2 * pi * n) + n * log10(n / e)2024/8/139数学问题的特点：题意容易理解；题意容易理解；数学关联性一般比较大；数学关联性一般比较大；语言的关联性相对较小；但有时需要相关语言的关联性相对较小；但有时需要相关策略来规避过高的复杂度。策略来规避过高的复杂度。要注意复杂度问题；要注意复杂度问题；适合适合ACM/ICPC入门练习。入门练习。每次竞赛一般会有每次竞赛一般会有1-2个数学问题个数学问题。2024/8/1310常用单词：1、integer 整数（不一定就是32位的）2、positive 正的3、negative (adj)负的; (n)负数4、factorial (n)阶乘; (adj)因子的，阶乘的5、digital (n)数字; (adj)数字的6、multiple 倍数7、multiplication 乘法运算2024/8/1311常用单词： （ 图形相关）1、vertex ( vertices ) 顶点2、polygon 多边形3、convex 凸的4、concave 凹的5、segment (线)段（n）;分割（v）2024/8/1312数学问题数学问题（分类分析）（分类分析）2024/8/1313第一类简单问题HDOJ1004:LettheBalloonRiseHDOJ1004:LettheBalloonRise题目描述：题目描述： 输入：输入：第一行输入气球的个数第一行输入气球的个数n，以下，以下n行输入行输入n个气球的颜色，个气球的颜色，n为为0时结束。时结束。 输出：输出：哪种颜色的气球数目最多哪种颜色的气球数目最多2024/8/1315HDOJ1004:LettheBalloonRiseSample Input5 green red blue red red 3 pink orange pink 0Sample output red pink2024/8/13162024/8/1317题目评述：1. 一个让你看到后兴奋的题目2.只要懂点C或者C+，就可解决该问题。2024/8/13181004题目分析：该题算法思想比较简单，就是对输入的字符串进行比较和统计。值得注意的一点是：如果用C语言来写，要注意可能会把第一个数字后的“回车符”误认为是第一个串，字符串的比较也要用函数和循环语句。而C+则在处理字符串方面较为方便。2024/8/1319Elevatorhttp:/acm.hdu.edu.cn/showproblem.php?pid=1008Problem DescriptionThehighestbuildinginourcityhasonlyoneelevator.ArequestlistismadeupwithNpositivenumbers.Thenumbersdenoteatwhichfloorstheelevatorwillstop,inspecifiedorder.Itcosts6secondstomovetheelevatoruponefloor,and4secondstomovedownonefloor.Theelevatorwillstayfor5secondsateachstop.Foragivenrequestlist,youaretocomputethetotaltimespenttofulfilltherequestsonthelist.Theelevatorisonthe0thflooratthebeginninganddoesnothavetoreturntothegroundfloorwhentherequestsarefulfilled.2024/8/1320InputTherearemultipletestcases.EachcasecontainsapositiveintegerN,followedbyNpositivenumbers.Allthenumbersintheinputarelessthan100.AtestcasewithN=0denotestheendofinput.Thistestcaseisnottobeprocessed.OutputPrintthetotaltimeonasinglelineforeachtestcase.Sample Input1 2 3 2 3 1 0Sample Output17 41const int UP = 6; const int DOWN = 4; const int STOP = 5; int nCase,floor; while(cin nCase & nCase) int sec = 0,tmp; cin floor; tmp = floor; sec = floor * UP + STOP; /由由0层出发到第一个目标层所有时间层出发到第一个目标层所有时间 for(int i = 1; i floor; if(floor tmp) /如果电梯往上如果电梯往上 sec += (floor - tmp) * UP + STOP; else /电梯往下电梯往下 sec += (tmp - floor) * DOWN + STOP; tmp = floor;/记录本次目标层，方便下一个目标层的计算记录本次目标层，方便下一个目标层的计算 cout sec endl; 2024/8/13212024/8/1322第二类 大数问题2024/8/1323一、大数加法 HDU1002： A + B Problem IIInput The first line of the input contains an integer T(1=T=20) which means the number of test cases. Then T lines follow, each line consists of two positive integers, A and B. Notice that the integers are very large, that means you should not process them by using 32-bit integer. You may assume the length of each integer will not exceed 1000.2024/8/1324分析：准确的说，此问题不算是数学问题；由于数据特别大，用一般的整数类型不能存储，怎么办？字符串存储？怎么处理？按位加，进位？2024/8/13251 2 3 5 6 7 8 02 35 6 7 8 0.3 5 6 0(1)字符如何相加？(从最低位开始相加）(2)不等长怎么办？(3)发生进位怎么办？本校本校OJ1217大数乘大数乘 时空限定时空限定 l5S，32M基本描述基本描述l给定一些大数，请计算其积。给定一些大数，请计算其积。输入描述输入描述l输入数据中含有一些整数对输入数据中含有一些整数对（对数（对数1000），若某对整），若某对整数（整数位数数（整数位数200）的值为）的值为0 0，则表示输入结束。，则表示输入结束。输出描述输出描述l每对整数对应一个乘法计算每对整数对应一个乘法计算结果，输出该结果，每个结结果，输出该结果，每个结果输出完后应回车。果输出完后应回车。样本输入样本输入l2 3l12 34l0 0样本输出样本输出l6l276A大数乘大数乘分析：分析：l存放：存放：lstringl考虑考虑l正负性，正负性，l位数（可能会超过位数（可能会超过200位很多）。位很多）。l正负性正负性l可以通过判断两个数的正负性来解决，可以通过判断两个数的正负性来解决，l做乘法的数字运算时，应先将负号去掉。做乘法的数字运算时，应先将负号去掉。l注意：注意：l倒序倒序string multi(const string& a, const string& b) if(a=0 | b=0) return 0; string aa(a0=-? a.substr(1) : a); string bb(b0=-? b.substr(1) : b); string sign = (a0=-)+(b0=-)=1 ? - : ); string s(aa.length() + bb.length(),0); reverse(aa.begin(), aa.end(); reverse(bb.begin(), bb.end(); for(int j=0; jbb.length(); +j) if(bbj=0) continue; int temp = 0; for(int i=0; iab & (a!=0 | b!=0); ) coutmulti(a, b)=2).Input ：Inputconsistsofasequenceoflines,eachcontaininganintegern.(n1,000,000).Output：Printthewordyesif3divideevenlyintoF(n).Printthewordnoifnot.Sample Input0 1 2 3 4 5Sample Outputno no yes no no no2024/8/1335题目分析：题目分析：判断某一项是否能被3 整除 是否需要把某一项的值求出来，进行整除判断？能被3整除的整数的特点？关于能否被3整除，这样的项在排列上是否有规律？（找出规律）第0项除以3余1，第1项除以3余2，第2项整除，第3项除以3余2，第4项除以3余2，第5项除以3余1，第6项整除，第7项除以3余1，第8项除以3余1，第9项除以3余2，第7项整除.2024/8/1336Hdoj_1021程序清单：程序清单：#includeint main() long n; while(scanf(%ld,&n) != EOF) if (n%8=2 | n%8=6) printf(yesn); else printf(non);return 0;2024/8/1337这个问题主要在于找出规律；程序编写很简单；考查的是分析问题的能力。2024/8/1338第四类 公式型HDOJ_1071TheArea 2024/8/1340抛物线公式：y=ax2+bx+c已知三点-a、b、c系数公式已知-如何求面积？积分问题2024/8/1341递推求解还记得还记得Fibonacci问题吧？问题吧？F(0)=F(1)=1;F(n)=F(n-1)+F(n-2);2024/8/13421182：母牛问题母牛问题http:/acm.zjut.edu.cn/ShowProblem.aspx?ShowID=1182Description: 假设单性繁殖成立，若一头母牛，从出生起第四个年头开始，每年生一头母牛，而生出的小母牛在之后的第四年也将具有生殖能力。按此规律，第n年时有多少头母牛？ Input: 输入数据中不多于50个整数（1n40）。 Output:对于每个n，输出其第n年的母牛数，每个结果对应一行输出。2024/8/1343如何得出递推公式？列出前面几个数据：1112346假设规模小于N的情况已经得到解决重点分析：当规模扩大到N时，如何枚举出所有的情况，并且要确保对于每一种子情况都能用已经得到的数据解决。f(n）=f(n-1)+f(n-3)(n-3年存在的牛在n年均可以生出一头小牛）2024/8/1344再来看难一点的问题2024/8/13452050：折线分割平面：折线分割平面http:/acm.hdu.edu.cn/showproblem.php?pid=20502024/8/1346这个问题其实属于递推问题，你们比我更擅长，呵呵2024/8/1347先看直线分割平面问题经典结论：平面内有n条直线，任何两条不平行，任何三条不过同一点；这n条直线可以把平面分成 n(n+1) /2 +1个部分。可用数学归纳法证明。2024/8/1348公式的推导F(1)=2; F(n) = F(n-1)+n;(第n条直线与n-1条相交，将增加n个区域）F(n)=n+n-1+n-2+.+2+f(1) =n(n+1)/2+12024/8/1349回到折线问题：一个折线可以看成两条直线相交，并去掉角的一个折线可以看成两条直线相交，并去掉角的一边一边 ；可推出公式：；可推出公式： f(n)=f(n-1)+(2n-1) +2n-22024/8/1350 f(n)=f(n-1)+(2n-1) +2n-2 f(1)=2F(n) = 2n+2n-1+2n-2+2n-3+. +4+3 -2*(n-1)+f(1) =2n-1+2n-2+.+4+3 +2+1 +1 =2n*(2n-1)/2 +1 = 2n(n-1)+1 =2*n2-n+1注意：两直线直接带入公式： n(n+1) /2 +12024/8/1351Ok, 内容已经不少了来几个思考题2024/8/1352思考（1） HDOJ 1465: 不容易系列之一不容易系列之一(递推求解)某人写了n封信和n个信封，如果所有的信都装错了信封。求所有的信都装错信封,共有多少种不同情况。分析分析总和就是 (n-1)*(f(n-1)+f(n-2)2024/8/1353#includeint main()int n;_int64 i,a21=0;a2=1;a3=2;for(i=4;i=20;i+)ai=(i-1)*(ai-1+ai-2);while(scanf(%d,&n)!=EOF)printf(%I64dn,an);return 0;2024/8/13542024/8/1355思考（2）HDOJ1030: Delta-wave http:/acm.hdu.edu.cn/showproblem.php?pid=1030ThetravellerneedstogofromthecellwithnumberMtothecellwithnumberN.Thetravellerisabletoenterthecellthroughcelledgesonly,hecannottravelfromcelltocellthroughvertices.Thenumberofedgesthetravellerpassesmakesthelengthofthetravellersroute.WritetheprogramtodeterminethelengthoftheshortestrouteconnectingcellswithnumbersNandM.题目大意：题目大意：InputInputcontainstwointegernumbersMandNintherangefrom1to1000000000separatedwithspace(s).OutputOutputshouldcontainthelengthoftheshortestroute.SampleInput612SampleOutput3分析：2024/8/1357分析：分析：1.每一行数的数目为每一行数的数目为 2n-1 (一定为奇数一定为奇数), n=1,2,3.2.每一行的数的范围每一行的数的范围(n-1)2+1 , n23.奇数行中以奇数开头，奇数结尾奇数行中以奇数开头，奇数结尾偶数行中以偶数开头，偶数结尾偶数行中以偶数开头，偶数结尾4.第第n行中与下一行的连接数为行中与下一行的连接数为n，第一个有，第，第一个有，第二个没有二个没有.最后一个有最后一个有5.在奇数行中，数字为奇数则可到达下一行，为在奇数行中，数字为奇数则可到达下一行，为偶数则不行偶数则不行2024/8/1358分析：分析：M，N分两种情况，先保证分两种情况，先保证MN1.M和N在同一行,则直接Steps = N-M2.M和N不再同一行,则想办法让M往下走使得其变成第一种情况，循环下列情况： (1).M能往下走，则往下走一步。 (2).不能往下走，则看二者偏离该行中心的大小，M偏离小于N偏离，如4偏离 小于 3，15偏离13 ，则能往右往右走，不能则往左走； M偏离小于N偏离能往左走则往左，不能则往右。 M偏离等于N偏离则能往右走则往右走，不能则往左走。2024/8/1359部分程序部分程序inline int Row(int num)/根据数字求行数return static_cast(sqrt(static_cast(num-1)+1;inline int Mid(int row)/第row行的中心的数return (row-1)*(row-1)+1+row*row)/2;inline bool CanLeft(int num,int row)/能不能往左return num(row-1)*(row-1)+1);inline bool CanRight(int num,int row)/能不能往右return num(row*row);inline bool CanDown(int num,int row)/能不能往下return (num%2=row%2);int OffSet(int num,int row) /num偏离row行中心的大小return num-Mid(row);2024/8/13602024/8/1361推荐练习推荐练习本校本校OJ：1177 1178 1182 1207 1211 1213 1288 1331 1347 1358HDOJ： 1002、1008、1012、1014、1018、1021、1030、1071、1076 1204、1465 、 2013、2050、争取争取AC10题！题！2024/8/1362See you next week.Thank you!