ACM入门教程-数学问题.ppt

ACM程序设计竞赛入门 浙江工业大学田贤忠txz 2020 2 21 1 2020 2 21 2 第二讲 数学问题 2020 2 21 3 引例 本校OJ1207 Inmanyapplicationsverylargeintegersnumbersarerequired Someoftheseapplicationsareusingkeysforsecuretransmissionofdata encryption etc Inthisproblemyouaregivenanumber youhavetodeterminethenumberofdigitsinthefactorialofthenumber 2020 2 21 4 InputInputconsistsofseverallinesofintegernumbers Thefirstlinecontainsanintegern whichisthenumberofcasestobetested followedbynlines oneinteger1 m 107oneachlineOutputTheoutputcontainsthenumberofdigitsinthefactorialoftheintegersappearingintheinput SampleInput21020 SampleOutput719 2020 2 21 5 如何求位数 算出阶乘 循环求位数 阶乘怎么存储 一定要算出阶乘吗 n 的位数 int log10 n 1 int log10 1 log10 2 log10 3 log10 n 1 2020 2 21 6 代码怎么写 超时问题怎么解决 能不能降低计算量 有没有更简便的公式 2020 2 21 7 如果不知道高效的计算公式 int log10 1 log10 2 log10 3 log10 n 对于每个输入的数都要按上述公式计算如何避免重复计算 先算小数的位数 在此基础上再算大数 1 每次找最小值 需要存储数据和位数的计算 2 先把算出的log10存储 2020 2 21 8 计算机程序设计艺术 中给出了另一个公式n sqrt 2 n n e n 1 1 12 n 1 288 n n O 1 n 3 acos 1 e exp 1 两边对10取对数忽略log10 1 1 12 n 1 288 n n O 1 n 3 log10 1 0得到公式log10 n log10 sqrt 2 pi n n log10 n e 2020 2 21 9 数学问题的特点 题意容易理解 数学关联性一般比较大 语言的关联性相对较小 但有时需要相关策略来规避过高的复杂度 要注意复杂度问题 适合ACM ICPC入门练习 每次竞赛一般会有1 2个数学问题 2020 2 21 10 常用单词 1 integer整数 不一定就是32位的 2 positive正的3 negative adj 负的 n 负数4 factorial n 阶乘 adj 因子的 阶乘的5 digital n 数字 adj 数字的6 multiple倍数7 multiplication乘法运算 2020 2 21 11 常用单词 图形相关 1 vertex vertices 顶点2 polygon多边形3 convex凸的4 concave凹的5 segment 线 段 n 分割 v 2020 2 21 12 数学问题 分类分析 2020 2 21 13 第一类 简单问题 HDOJ1004 LettheBalloonRise HDOJ1004 LettheBalloonRise 题目描述 输入 第一行输入气球的个数n 以下n行输入n个气球的颜色 n为0时结束 输出 哪种颜色的气球数目最多 2020 2 21 15 HDOJ1004 LettheBalloonRise SampleInput5greenredblueredred3pinkorangepink0 Sampleoutputredpink 2020 2 21 16 2020 2 21 17 题目评述 1 一个让你看到后兴奋的题目 2 只要懂点C或者C 就可解决该问题 2020 2 21 18 1004题目分析 该题算法思想比较简单 就是对输入的字符串进行比较和统计 值得注意的一点是 如果用C语言来写 要注意可能会把第一个数字后的 回车符 误认为是第一个串 字符串的比较也要用函数和循环语句 而C 则在处理字符串方面较为方便 2020 2 21 19 Elevator ProblemDescriptionThehighestbuildinginourcityhasonlyoneelevator ArequestlistismadeupwithNpositivenumbers Thenumbersdenoteatwhichfloorstheelevatorwillstop inspecifiedorder Itcosts6secondstomovetheelevatoruponefloor and4secondstomovedownonefloor Theelevatorwillstayfor5secondsateachstop Foragivenrequestlist youaretocomputethetotaltimespenttofulfilltherequestsonthelist Theelevatorisonthe0thflooratthebeginninganddoesnothavetoreturntothegroundfloorwhentherequestsarefulfilled 2020 2 21 20 InputTherearemultipletestcases EachcasecontainsapositiveintegerN followedbyNpositivenumbers Allthenumbersintheinputarelessthan100 AtestcasewithN 0denotestheendofinput Thistestcaseisnottobeprocessed OutputPrintthetotaltimeonasinglelineforeachtestcase SampleInput1232310SampleOutput1741 constintUP 6 constintDOWN 4 constintSTOP 5 intnCase floor while cin nCase 2020 2 21 21 2020 2 21 22 第二类大数问题 2020 2 21 23 一 大数加法HDU1002 A BProblemII InputThefirstlineoftheinputcontainsanintegerT 1 T 20 whichmeansthenumberoftestcases ThenTlinesfollow eachlineconsistsoftwopositiveintegers AandB Noticethattheintegersareverylarge thatmeansyoushouldnotprocessthembyusing32 bitinteger Youmayassumethelengthofeachintegerwillnotexceed1000 2020 2 21 24 分析 准确的说 此问题不算是数学问题 由于数据特别大 用一般的整数类型不能存储 怎么办 字符串存储 怎么处理 按位加 进位 2020 2 21 25 字符如何相加 从最低位开始相加 不等长怎么办 发生进位怎么办 本校OJ1217大数乘 时空限定5S 32M基本描述给定一些大数 请计算其积 输入描述输入数据中含有一些整数对 对数 1000 若某对整数 整数位数 200 的值为00 则表示输入结束 输出描述每对整数对应一个乘法计算结果 输出该结果 每个结果输出完后应回车 样本输入23123400样本输出6276 A大数乘 分析 存放 string考虑正负性 位数 可能会超过200位很多 正负性可以通过判断两个数的正负性来解决 做乘法的数字运算时 应先将负号去掉 注意 倒序 stringmulti conststring A大数乘 调用 for stringa b cin a b 2020 2 21 30 第三类注重分析的问题 2020 2 21 31 先看一个简单的题目 2020 2 21 32 1331 取石子问题 Description 小明是个游戏迷 这不 今天他又和小刚一起玩 拿石子 的游戏 游戏规则是2个人轮流拿石子 一次可以拿1颗或3颗 规定谁取到最后一颗石子就是谁赢 小明和小刚商量后决定每次都是小明先取 小明与小刚都是游戏高手 该赢的局绝不会输 在知道石子总数的情况下 小明想快速知道每次的输赢情况 2020 2 21 33 分析 各取一次共有三种情况 共取走2颗石子 共取走4颗石子 共取走6颗石子设有石子S 方案 取了N1次 方案 取了N2次 方案 取了N3次后 还剩下K个石子 S 2 N1 4 N2 6 N3 KK的取值有三种情况 0 1 3 K 1 3则先取方胜 反之 另一方胜 当S为偶数时 后取方胜 反之 先取方胜 2020 2 21 34 杭电OJ 1021FibonacciAgain ProblemDescriptionThereareanotherkindofFibonaccinumbers F 0 7 F 1 11 F n F n 1 F n 2 n 2 Input Inputconsistsofasequenceoflines eachcontaininganintegern n 1 000 000 Output Printtheword yes if3divideevenlyintoF n Printtheword no ifnot SampleInput012345 SampleOutputnonoyesnonono 2020 2 21 35 题目分析 判断某一项是否能被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项整除 2020 2 21 36 Hdoj 1021程序清单 includeintmain longn while scanf ld 2020 2 21 37 这个问题主要在于找出规律 程序编写很简单 考查的是分析问题的能力 2020 2 21 38 第四类公式型 HDOJ 1071TheArea 2020 2 21 40 抛物线公式 y ax 2 bx c 已知三点 a b c系数 公式已知 如何求面积 积分问题 2020 2 21 41 递推求解 还记得Fibonacci问题吧 F 0 F 1 1 F n F n 1 F n 2 2020 2 21 42 1182 母牛问题 Description 假设单性繁殖成立 若一头母牛 从出生起第四个年头开始 每年生一头母牛 而生出的小母牛在之后的第四年也将具有生殖能力 按此规律 第n年时有多少头母牛 Input 输入数据中不多于50个整数 1 n 40 Output 对于每个n 输出其第n年的母牛数 每个结果对应一行输出 2020 2 21 43 如何得出递推公式 列出前面几个数据 1112346假设规模小于N的情况已经得到解决重点分析 当规模扩大到N时 如何枚举出所有的情况 并且要确保对于每一种子情况都能用已经得到的数据解决 f n f n 1 f n 3 n 3年存在的牛在n年均可以生出一头小牛 2020 2 21 44 再来看难一点的问题 2020 2 21 45 2050 折线分割平面 2020 2 21 46 这个问题 其实属于递推问题 你们比我更擅长 呵呵 2020 2 21 47 先看直线分割平面问题 经典结论 平面内有n条直线 任何两条不平行 任何三条不过同一点 这n条直线可以把平面分成n n 1 2 1个部分 可用数学归纳法证明 2020 2 21 48 公式的推导 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 1 2020 2 21 49 回到折线问题 一个折线可以看成两条直线相交 并去掉角的一边 可推出公式 f n f n 1 2n 1 2n 2 2020 2 21 50 f n f n 1 2n 1 2n 2f 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 n 2 n 1注意 两直线直接带入公式 n n 1 2 1 2020 2 21 51 Ok 内容已经不少了 来几个思考题 2020 2 21 52 思考 1 HDOJ1465 不容易系列之一 递推求解 某人写了n封信和n个信封 如果所有的信都装错了信封 求所有的信都装错信封 共有多少种不同情况 分析 总和就是 n 1 f n 1 f n 2 2020 2 21 53 includeintmain intn int64i a 21 0 a 2 1 a 3 2 for i 4 i 20 i a i i 1 a i 1 a i 2 while scanf d 2020 2 21 54 2020 2 21 55 思考 2 HDOJ1030 Delta wave ThetravellerneedstogofromthecellwithnumberMtothecellwithnumberN Thetravellerisabletoenterthecellthroughcelledgesonly hecannottravelfromcelltocellthroughvertices Thenumberofedgesthetravellerpassesmakesthelengthofthetraveller sroute WritetheprogramtodeterminethelengthoftheshortestrouteconnectingcellswithnumbersNandM 题目大意 InputInputcontainstwointegernumbersMandNintherangefrom1to1000000000separatedwithspace s OutputOutputshouldcontainthelengthoftheshortestroute SampleInput612SampleOutput3 分析 2020 2 21 57 分析 1 每一行数的数目为2n 1 一定为奇数 n 1 2 3 2 每一行的数的范围 n 1 2 1 n 2 3 奇数行中以奇数开头 奇数结尾偶数行中以偶数开头 偶数结尾4 第n行中与下一行的连接数为n 第一个有 第二个没有 最后一个有5 在奇数行中 数字为奇数则可到达下一行 为偶数则不行 2020 2 21 58 分析 M N分两种情况 先保证M N1 M和N在同一行 则直接Steps N M2 M和N不再同一行 则想办法让M往下走使得其变成第一种情况 循环下列情况 1 M能往下走 则往下走一步 2 不能往下走 则看二者偏离该行中心的大小 M偏离小于N偏离 如4偏离小于3 15偏离13 则能往右往右走 不能则往左走 M偏离小于N偏离能往左走则往左 不能则往右 M偏离等于N偏离则能往右走则往右走 不能则往左走 2020 2 21 59 部分程序 inlineintRow intnum 根据数字求行数 returnstatic cast sqrt static cast num 1 1 inlineintMid introw 第row行的中心的数 return row 1 row 1 1 row row 2 inlineboolCanLeft intnum introw 能不能往左 returnnum row 1 row 1 1 inlineboolCanRight intnum introw 能不能往右 returnnum row row inlineboolCanDown intnum introw 能不能往下 return num 2 row 2 intOffSet intnum introw num偏离row行中心的大小 returnnum Mid row 2020 2 21 60 2020 2 21 61 推荐练习 本校OJ 1177117811821207121112131288133113471358 HDOJ 1002 1008 1012 1014 1018 1021 1030 1071 10761204 1465 2013 2050 争取AC10题 2020 2 21 62 Seeyounextweek Thankyou