1、2020/7/28,1,ACM 程序設(shè)計(jì),計(jì)算機(jī)學(xué)院 劉春英,2020/7/28,2,第一講,ACM入門,2020/7/28,3,第一部分,初識(shí)ACM,2020/7/28,4,ACM (Association for Computing Machinery) 成立于計(jì)算機(jī)誕生次年，是目前計(jì)算機(jī)學(xué)界中歷史最悠久、最具權(quán)威性的組織，是推進(jìn)信息技術(shù)專業(yè)人員和學(xué)生提高技巧的主要力量。ACM通過(guò)提供前沿技術(shù)信息和從理論到實(shí)踐的轉(zhuǎn)化，為其全球7.5萬(wàn)名成員服務(wù)，并已經(jīng)成為信息科技領(lǐng)域的一個(gè)基本信息來(lái)源。,What is ACM ?,2020/7/28,5,我們說(shuō)的“ACM”是什么？,2020/7/28,6

2、,ACM/ICPC：,ACM主辦的國(guó)際大學(xué)生程序設(shè)計(jì)競(jìng)賽 (International Collegiate Programming Contest)，簡(jiǎn)稱ACM / ICPC，自從1977年開(kāi)始至今已經(jīng)連續(xù)舉辦30屆。其宗旨是提供一個(gè)讓大學(xué)生向IT界展示自己分析問(wèn)題和解決問(wèn)題的能力的絕好機(jī)會(huì)，并成為一個(gè)有效的途徑，讓下一代IT天才可以接觸到其日后工作中將要用到的各種軟件。 現(xiàn)在，ACM / ICPC已成為世界各國(guó)大學(xué)生中最具影響力的國(guó)際計(jì)算機(jī)賽事。,2020/7/28,7,ACM/ICPC in China,中國(guó)大陸高校從1996年開(kāi)始參加ACM國(guó)際大學(xué)生程序設(shè)計(jì)競(jìng)賽亞洲預(yù)賽。 前五屆中國(guó)賽

3、區(qū)設(shè)在上海，由上海大學(xué)承辦； 2002年由清華大學(xué)和西安交通大學(xué)承辦； 2003年由清華大學(xué)和中山大學(xué)承辦。 2004年由北京大學(xué)和上海交通大學(xué)承辦。 2005年由四川大學(xué)、北大和浙大承辦。 2006年由上海大學(xué)、清華和西電承辦。,2020/7/28,8,ACM in HDU,2003年9月，第一次參加省賽（邀請(qǐng)賽） 2004年5月，參加了浙江省“舜宇”杯首屆大學(xué)生程序設(shè)計(jì)大賽 2004年1112月，參加了第29屆ACM/ICPC亞洲區(qū)北京賽區(qū)和上海賽區(qū)比賽 2005年5月參加了浙江省第二屆“舜宇”杯大學(xué)生程序設(shè)計(jì)大賽 2005年11月參加了在大陸舉行的三站亞洲區(qū)比賽 2006年5月參加了浙江

4、省第二屆“舜宇”杯大學(xué)生程序設(shè)計(jì)大賽 今年,2020/7/28,9,預(yù)期賽事（今后每年）,34月，舉行校內(nèi)大賽（暨選拔賽） 5月，參加浙江省大學(xué)生程序設(shè)計(jì)大賽 11月，參加ACM/ICPC亞洲區(qū)比賽（至少參加兩個(gè)賽區(qū)的比賽） 另外，每學(xué)期至少有三次月賽以及適當(dāng)?shù)木毩?xí)賽,2020/7/28,10,如何比賽？, 3人組隊(duì), 可以攜帶諸如書、手冊(cè)、 程序清單等參考資料；不能攜帶任何可用計(jì)算機(jī)處理的軟件或數(shù)據(jù)、不能攜帶任何類型的通訊工具；,可能收到的反饋信息包括： Compile Error - 程序不能通過(guò)編譯。Run Time Error - 程序運(yùn)行過(guò)程中出現(xiàn)非正常中斷。 Time Limit

5、Exceeded - 運(yùn)行超過(guò)時(shí)限還沒(méi)有得到輸出結(jié)果。 Wrong Answer - 答案錯(cuò)誤。 Presentation Error - 輸出格式不對(duì)，可檢查空格、回車等等細(xì)節(jié)。 Accepted - 恭喜恭喜！,2020/7/28,11,首先根據(jù)解題數(shù)目進(jìn)行排名。 如果多支隊(duì)伍解題數(shù)量相同，則根據(jù)總用時(shí)加上懲罰時(shí)間進(jìn)行排名。 總用時(shí)和懲罰時(shí)間由每道解答正確的試題的用時(shí)加上懲罰時(shí)間而成。 每道試題用時(shí)將從競(jìng)賽開(kāi)始到試題解答被判定為正確為止，其間每一次錯(cuò)誤的運(yùn)行將被加罰20分鐘時(shí)間，未正確解答的試題不記時(shí)。,如何排名？,2020/7/28,12,比賽形式 1支隊(duì)伍1臺(tái)機(jī)器（提供打印服務(wù)） 上機(jī)

6、編程解決問(wèn)題（可帶紙質(zhì)資料） 實(shí)時(shí)測(cè)試，動(dòng)態(tài)排名 試題 6-10題 全英文（可以帶字典） 時(shí)間：持續(xù)5個(gè)小時(shí),2020/7/28,13,ACM .vs. 校程序設(shè)計(jì)競(jìng)賽,ACM競(jìng)賽 團(tuán)隊(duì)合作精神 即時(shí)提交，通過(guò)所有數(shù)據(jù)才能得分 全英文題目，題目考察范圍廣 校程序設(shè)計(jì)競(jìng)賽 個(gè)人編程能力的比拼 中文或者英文題目，考察編程基本功,2020/7/28,14,ACM隊(duì)隊(duì)員的基本原則,基本要求 人品好 愿意花時(shí)間在這項(xiàng)賽事上 有團(tuán)隊(duì)合作精神 能力要求 程序設(shè)計(jì) 英語(yǔ)科技文獻(xiàn)閱讀 數(shù)學(xué),2020/7/28,15,杭電參賽歷程,2020/7/28,16,2020/7/28,17,2020/7/28,18,20

7、20/7/28,19,2006 集訓(xùn)隊(duì),2020/7/28,20,全家福,2020/7/28,21,放松完畢 回到正題,2020/7/28,22,開(kāi)課目的,為杭電ACM代表隊(duì)培養(yǎng)后備人才 提高分析問(wèn)題和應(yīng)用計(jì)算機(jī)編程解決問(wèn)題的能力 培養(yǎng)必要的自學(xué)能力 培養(yǎng)學(xué)生的協(xié)調(diào)和溝通能力 體會(huì)學(xué)習(xí)的快樂(lè),2020/7/28,23,如何入門呢?,2020/7/28,24,ACM題目特點(diǎn):,由于ACM競(jìng)賽題目的輸入數(shù)據(jù)和輸出數(shù)據(jù)一般有多組（不定），并且格式多種多樣，所以，如何處理題目的輸入輸出是對(duì)大家的一項(xiàng)最基本的要求。這也是困擾初學(xué)者的一大問(wèn)題。 下面，分類介紹：,2020/7/28,25,先看一個(gè)超級(jí)簡(jiǎn)單

8、的題目：, Sample input: 1 5 10 20 Sample output: 6 30,2020/7/28,26,初學(xué)者很常見(jiàn)的一種寫法：,#include void main() int a,b; scanf(“%d %d”, ,2020/7/28,27,有什么問(wèn)題呢？,這就是下面需要解決的問(wèn)題,2020/7/28,28,第二部分,基本輸入輸出,2020/7/28,29,輸入_第一類：,輸入不說(shuō)明有多少個(gè)Input Block,以EOF為結(jié)束標(biāo)志。 參見(jiàn)：HDOJ_1089 ,2020/7/28,30,Hdoj_1089源代碼：,#include int main() int a

9、,b; while(scanf(%d %d, ,2020/7/28,31,本類輸入解決方案：,C語(yǔ)法： while(scanf(%d %d, scanf(%d, ,2020/7/28,35,本類輸入解決方案：,C語(yǔ)法： scanf(%d, i+ ) . ,2020/7/28,36,輸入_第三類：,輸入不說(shuō)明有多少個(gè)Input Block,但以某個(gè)特殊輸入為結(jié)束標(biāo)志。 參見(jiàn)：HDOJ_1091 ,2020/7/28,37,Hdoj_1091源代碼：,#include int main() int a,b; while(scanf(%d %d, ,上面的程序有什么問(wèn)題？,2020/7/28,38,

10、本類輸入解決方案：,C語(yǔ)法： while(scanf(%d, gets(buf); C+語(yǔ)法： 如果用string buf;來(lái)保存： getline( cin , buf ); 如果用char buf 255 ; 來(lái)保存： cin.getline( buf, 255 );,2020/7/28,42,說(shuō)明（5_1）：,scanf(“ %s%s”,str1,str2)，在多個(gè)字符串之間用一個(gè)或多個(gè)空格分隔； 若使用gets函數(shù)，應(yīng)為gets(str1); gets(str2); 字符串之間用回車符作分隔。 通常情況下，接受短字符用scanf函數(shù)，接受長(zhǎng)字符用gets函數(shù)。 而getchar函數(shù)每次

11、只接受一個(gè)字符，經(jīng)常c=getchar()這樣來(lái)使用。,2020/7/28,43,說(shuō)明（5_2）：cin.getline的用法：,getline 是一個(gè)函數(shù)，它可以接受用戶的輸入的字符，直到已達(dá)指定個(gè)數(shù)，或者用戶輸入了特定的字符。它的函數(shù)聲明形式（函數(shù)原型）如下： istream 不用管它的返回類型，來(lái)關(guān)心它的三個(gè)參數(shù)： char line： 就是一個(gè)字符數(shù)組，用戶輸入的內(nèi)容將存入在該數(shù)組內(nèi)。 int size : 最多接受幾個(gè)字符？用戶超過(guò)size的輸入都將不被接受。 char endchar :當(dāng)用戶輸入endchar指定的字符時(shí)，自動(dòng)結(jié)束。默認(rèn)是回車符。,2020/7/28,44,說(shuō)明（

12、5_2）續(xù),結(jié)合后兩個(gè)參數(shù)，getline可以方便地實(shí)現(xiàn)： 用戶最多輸入指定個(gè)數(shù)的字符，如果超過(guò)，則僅指定個(gè)數(shù)的前面字符有效，如果沒(méi)有超過(guò)，則用戶可以通過(guò)回車來(lái)結(jié)束輸入。 char name4; cin.getline(name,4,n); 由于 endchar 默認(rèn)已經(jīng)是 n，所以后面那行也可以寫成： cin.getline(name,4);,2020/7/28,45,思考：以下題目屬于哪一類輸入？, ,2020/7/28,46,思考：,hdoj_1018（Big Number ）如果用最簡(jiǎn)單的算法，則有一個(gè)很顯然的問(wèn)題：如何保存計(jì)算后的階乘？ 如果用大數(shù)類，則顯然小題大做！ 思考：如何解決

13、呢？,2020/7/28,47,再思考：,hdoj_1013（Digital Roots ）貌似簡(jiǎn)單，但是有陷阱在里面。 提示：輸入數(shù)據(jù)可能很長(zhǎng)，能按照整形進(jìn)行處理嗎？,2020/7/28,48,輸出_第一類：,一個(gè)Input Block對(duì)應(yīng)一個(gè)Output Block，Output Block之間沒(méi)有空行。 參見(jiàn)：HDOJ_1089 ,2020/7/28,49,解決方案：,C語(yǔ)法： . printf(%dn,ans); C+語(yǔ)法： . cout ans endl; ,2020/7/28,50,輸出_第二類：,一個(gè)Input Block對(duì)應(yīng)一個(gè)Output Block，每個(gè)Output Blo

14、ck之后都有空行。參見(jiàn)：HDOJ_1095 ,2020/7/28,51,1095源代碼,#include int main() int a,b; while(scanf(%d %d, ,2020/7/28,52,解決辦法：,C語(yǔ)法： . printf(%dnn,ans); C+語(yǔ)法： . cout ans endl endl; ,2020/7/28,53,輸出_第三類：,一個(gè)Input Block對(duì)應(yīng)一個(gè)Output Block，Output Block之間有空行。 參見(jiàn)：HDOJ_1096 ,2020/7/28,54,1096源代碼,#include int main() int icase

15、,n,i,j,a,sum; scanf(%d, ,2020/7/28,55,解決辦法：,C語(yǔ)法： for (k=0;kcount;k+) while () printf( %dn,result); if (k!=count-1) printf(n); C+語(yǔ)法： 類似，輸出語(yǔ)句換一下即可。,2020/7/28,56,思考：以下題目屬于哪一類輸出？, ,2020/7/28,57,附: 初學(xué)者常見(jiàn)問(wèn)題,2020/7/28,58,一、編譯錯(cuò)誤,Main函數(shù)必須返回int類型(正式比賽) 不要在for語(yǔ)句中定義類型 _int64不支持，可以用long long代替 使用了漢語(yǔ)的標(biāo)點(diǎn)符號(hào) itoa不是a

16、nsi函數(shù) 能將整數(shù)轉(zhuǎn)換為字符串而且與ANSI標(biāo)準(zhǔn)兼容的方法是使用sprintf()函數(shù) int num = 100; char str25; sprintf(str, %d , num); 另外，拷貝程序容易產(chǎn)生錯(cuò)誤,2020/7/28,59,下面的hdoj1089為什么 CE?,#include int main() int a,b; while(scanf(%d %d, ,2020/7/28,60,二、小技巧,數(shù)據(jù)的拷貝（特別是輸出的提示信息） 調(diào)試的sample input的拷貝,2020/7/28,61,三、C語(yǔ)言處理“混合數(shù)據(jù)”的問(wèn)題,例題（Hdoj_1170） ,2020/7/2

17、8,62,常見(jiàn)的代碼：, scanf(%dn, ,2020/7/28,63,有什么問(wèn)題？,2020/7/28,64,四、Printf和cout混用的問(wèn)題,以下的程序輸出什么？ #include #include int main() int j=0; for(j=0;j5;j+) coutj=; printf(%dn,j); return 0; ,2020/7/28,65,為什么？,一個(gè)帶緩沖輸出（cout） 一個(gè)不帶緩沖輸出(printf),2020/7/28,66,思考題（天津大學(xué)9月份月賽題）,目的：初步體會(huì)一下ACM的魅力 ,2020/7/28,67,授課方式與成績(jī)?cè)u(píng)定,介紹常用算法 舉例分析 上機(jī)練習(xí)（自己在線練習(xí)） 成績(jī)?cè)u(píng)定：機(jī)試 ( 5 6 題 ),2020/7/28,68,相關(guān)資料,數(shù)學(xué)知識(shí) 離散、組合 數(shù)論、圖論 計(jì)算幾何 算法&數(shù)據(jù)結(jié)構(gòu) 基本數(shù)據(jù)結(jié)構(gòu) 搜索、分治 動(dòng)態(tài)規(guī)劃 貪心,2020/