ACM程序設計,杭州電子科技大學劉春英acm,2019/11/18,2,今天，,你了嗎？,AC,2019/11/18,3,每周一星（1）：,Nia,2019/11/18,4,第二講,基礎數學題,2019/11/18,5,1008:Elevator,2019/11/18,6,這是2004省賽最簡單的一題，當時訓練水平相對較高的學校基本上10分鐘之內解決該題，這是一個沒有算法的簡單模擬題目。入門訓練的好選擇,題目評述：,2019/11/18,7,HDOJ_1108最小公倍數,給定兩個正整數，計算這兩個數的最小公倍數。101470,2019/11/18,8,歐幾里德算法,intgcd(intda,intxiao)inttemp;while(xiao!=0)temp=da%xiao;da=xiao;xiao=temp;return(da);,思考：遞歸的形式如何寫？,2019/11/18,9,HDOJ_1061RightmostDigit,GivenapositiveintegerN,youshouldoutputthemostrightdigitofNN(1=N=1,000,000,000).3476,2019/11/18,10,HDOJ_1061RightmostDigit,數據規模很大暴力方法該打基本思路規律,2019/11/18,11,HDOJ_2035人見人愛AB,求AB的最后三位數表示的整數（1=A,B=10000）231268984,2019/11/18,12,HDOJ_2035人見人愛AB,最暴力的暴力？改進的暴力？二分加速？,2019/11/18,13,HDOJ_1425sort,給你n個整數，請按從大到小的順序輸出其中前m大的數。每組測試數據有兩行，第一行有兩個數n,m(0n,m1000000)，第二行包含n個各不相同，且都處于區間-500000,500000的整數。533-3592213-644213923,2019/11/18,14,HDOJ_1425sort,常規的思想是？常規的結果是？數據的特點是？加速的方法是？思考：1.如果數據可以重復呢?2.初始化需要注意什么?,2019/11/18,15,1021FibonacciAgain,2019/11/18,16,題目分析：,能被3整除的整數的特點？,還要看程序嗎？,如果兩個數的和能被3整除，這兩個數有什么特點？,關于“和”能否被3整除，這兩個數一共有多少種組合？,會不會出現某連續兩項和后面連續兩項相等的情況？如果出現，能得到什么信息？,2019/11/18,17,Hdoj_1021程序清單：,#includeintmain()longn;while(scanf(%ld,2019/11/18,18,ProblemB:NumberSequence,2019/11/18,19,題目特點：,這個題目是一個比較典型的ACM競賽題，盡管在真正的大賽中這個題目可能算比較簡單的，但在本次比賽中，本題難度屬于中等，可以說，能做出本題的隊伍基本都有銀獎以上。但如果不認真分析，有可能會掉入陷阱。,2019/11/18,20,Question:,暴力（Brute-Force）能解決問題嗎？,2019/11/18,21,題目分析：,對于這種題目，千萬不能蠻干！實際上，有經驗的同學看到本題目的數據規模，很快就能知道：這類題目有規律可循。,2019/11/18,22,現在對這題有什么想法,?,2019/11/18,23,附：非典型數學題,HDOJ_1205吃糖果Gardon吃糖果時有個特殊的癖好，就是不喜歡將一樣的糖果放在一起吃，喜歡先吃一種，下一次吃另一種；可是Gardon不知道是否存在一種吃糖果的順序使得他能把所有糖果都吃完？請你寫個程序幫忙計算一下對于每組數據，輸出一行，包含一個Yes或者No。,2019/11/18,24,請自己仔細分析.,哪位同學做個陳述？,2019/11/18,25,非典型之二：HDOJ_1071TheArea,2019/11/18,26,拋物線公式：y=ax2+bx+c,已知三點-a、b、c系數,公式已知-如何求面積？,會簡單積分嗎？,分析過程：,2019/11/18,27,課后任務：,完成在線練習：2