杭州电子科技大学ACM培训02---简单数学题.ppt

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,今天，,你 了吗？,AC,11/5/2025,1,每周一星（1）：,酷行天下,11/5/2025,2,第二讲,基础数学题,11/5/2025,3,HDOJ_1108,最小公倍数,给定两个正整数，计算这两个数的最小公倍数。,10 14,70,11/5/2025,6,欧几里德算法,int gcd(int da,int xiao),int temp;,while(xiao!=0),temp=da%xiao;,da=xiao;,xiao=temp;,return(da);,思考：,递归的形式如何写？,11/5/2025,7,HDOJ_1061,Rightmost Digit,Given a positive integer N,you should output the most right digit of NN,(1=N=1,000,000,000).,3,4,7,6,11/5/2025,8,HDOJ_1061,Rightmost Digit,数据规模,很大,暴力方法 该打,基本思路 规律,11/5/2025,9,HDOJ_2035,人见人爱,AB,求AB的最后三位数表示的整数（1=A,B=10000）,2 3,12 6,8,984,11/5/2025,10,HDOJ_2035,人见人爱,AB,最暴力的暴力？,改进的暴力？,二分加速？,11/5/2025,11,HDOJ_1425,sort,给你n个整数，请按从大到小的顺序输出其中前m大的数。,每组测试数据有两行，第一行有两个数n,m(0n,m1000000)，第二行包含n个各不相同，且都处于区间-500000,500000的整数。,5 3,3-35 92 213-644,213 92 3,11/5/2025,12,HDOJ_1425,sort,常规的思想是？,常规的结果是？,数据的特点是？,加速的方法是？,思考：,1.,如果数据可以重复呢,?,2.初始化需要注意什么?,11/5/2025,13,1021 Fibonacci Again,11/5/2025,14,题目分析：,能被3整除的整数的特点？,还要看程序吗？,如果两个数的和能被3整除，这两个数有什么特点？,关于“和”能否被3整除，这两个数一共有多少种组合？,会不会出现某连续两项和后面连续两项相等的情况？,如果,出现,，,能得到什么信息,？,11/5/2025,15,Hdoj_1021,程序清单：,#include,int main(),long n;,while(scanf(%ld,&n)!=EOF),if(n%8=2|n%8=6),printf(yesn);,else,printf(non);,return 0;,11/5/2025,16,Problem B:Number Sequence,11/5/2025,17,题目特点：,这个题目是一个比较典型的ACM竞赛题，尽管在真正的大赛中这个题目可能算比较简单的，但在本次比赛中，本题难度属于中等，可以说，能做出本题的队伍基本都有银奖以上。,但如果不认真分析，有可能会掉入陷阱。,11/5/2025,18,Question:,暴力（Brute-Force）能解决问题吗？,11/5/2025,19,题目分析：,对于这种题目，千万不能蛮干！实际上，有经验的同学看到本题目的数据规模，很快就能知道：这类题目有规律可循。,11/5/2025,20,现在对这题有什么想法,?,11/5/2025,21,附：非典型数学题,HDOJ_1205,吃糖果,Gardon吃糖果时有个特殊的癖好，就是不喜欢将一样的糖果放在一起吃，喜欢先吃一种，下一次吃另一种；可是Gardon不知道是否存在一种吃糖果的顺序使得他能把所有糖果都吃完？请你写个程序帮忙计算一下,对于每组数据，输出一行，包含一个Yes或者No。,11/5/2025,22,请自己仔细分析.,哪位同学做个陈述？,11/5/2025,23,非典型之二：,HDOJ_1071 The Area,11/5/2025,24,抛物线公式：y=ax2+bx+c,已知三点 -a、b、c 系数,公式已知 -如何求面积？,会简单积分吗？,分析过程：,11/5/2025,25,课后任务：,完成在线练习：,201009ACM程序设计作业2基础数学练习,特别提醒：,作业务必尽力完成,（第一次的作业尚未完成的，一定要补上）,11/5/2025,26,Welcome to HDOJ,Thank,You,11/5/2025,27,