杭電ACM課件lecture01初識A

1、2020/7/28,1,ACM 程序設(shè)計(jì),計(jì)算機(jī)學(xué)院 劉春英,2020/7/28,2,第一講,ACM入門,2020/7/28,3,第一部分,初識ACM,2020/7/28,4,ACM (Association for Computing Machinery) 成立于計(jì)算機(jī)誕生次年，是目前計(jì)算機(jī)學(xué)界中歷史最悠久、最具權(quán)威性的組織,What is ACM ?,2020/7/28,5,我們說的“ACM”是什么？,2020/7/28,6,ACM/ICPC：,ACM主辦的國際大學(xué)生程序設(shè)計(jì)競賽 (International Collegiate Programming Contest)，簡稱ACM /

2、ICPC，自從1977年開始至今已經(jīng)連續(xù)舉辦31屆。其宗旨是提供一個讓大學(xué)生向IT界展示自己分析問題和解決問題的能力的絕好機(jī)會，讓下一代IT天才可以接觸到其今后工作中將要用到的各種軟件。 現(xiàn)在，ACM / ICPC已成為世界各國大學(xué)生中最具影響力的國際計(jì)算機(jī)賽事。（非官方）,2020/7/28,7,ACM/ICPC in China,中國大陸高校從1996年開始參加ACM國際大學(xué)生程序設(shè)計(jì)競賽亞洲預(yù)賽。 前六屆中國賽區(qū)設(shè)在上海，由上海大學(xué)承辦； 2002年由清華大學(xué)和西安交通大學(xué)承辦； 2003年由清華大學(xué)和中山大學(xué)承辦。 2004年由北京大學(xué)和上海交通大學(xué)承辦。 2005年由四川大學(xué)、北大和

3、浙大承辦。 2006年由上海大學(xué)、清華和西電承辦。 2007年：北航、南航、吉大、西華,2020/7/28,8,2020/7/28,9,ACM in HDU,2003年9月，第一次參加省賽（邀請賽） 2004年5月，浙江省“舜宇”杯首屆大學(xué)生程序設(shè)計(jì)大賽 2004年1112月，第29屆ACM亞洲區(qū)北京和上海賽區(qū)比賽 2005年5月,浙江省第二屆“舜宇”杯大學(xué)生程序設(shè)計(jì)大賽 2005年11月,參加中國大陸的三站亞洲區(qū)比賽 2006年5月,浙江省第二屆“舜宇”杯大學(xué)生程序設(shè)計(jì)大賽 2006年1112月，第31屆ACM首爾、北京、上海和西安賽區(qū)比賽 今年,2020/7/28,10,預(yù)期賽事（今后每年

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

5、 答案錯誤。 Presentation Error - 輸出格式不對，可檢查空格、回車等等細(xì)節(jié)。 Accepted - 恭喜恭喜！,2020/7/28,12,首先根據(jù)解題數(shù)目進(jìn)行排名。 如果多支隊(duì)伍解題數(shù)量相同，則根據(jù)總用時加上懲罰時間進(jìn)行排名。 總用時和懲罰時間由每道解答正確的試題的用時加上懲罰時間而成。 每道試題用時將從競賽開始到試題解答被判定為正確為止，其間每一次錯誤的運(yùn)行將被加罰20分鐘時間，未正確解答的試題不記時。,如何排名？,2020/7/28,13,比賽形式 1支隊(duì)伍1臺機(jī)器（提供打印服務(wù)） 上機(jī)編程解決問題（可帶紙質(zhì)資料） 實(shí)時測試，動態(tài)排名 試題 6-10題 全英文（可以帶字

6、典） 時間：持續(xù)5個小時,2020/7/28,14,ACM .vs. 校程序設(shè)計(jì)競賽,ACM競賽 團(tuán)隊(duì)合作精神 即時提交，通過所有數(shù)據(jù)才能得分 全英文題目，題目考察范圍廣 校程序設(shè)計(jì)競賽 個人編程能力的比拼 中文或者英文題目，考察編程基本功,2020/7/28,15,ACM隊(duì)隊(duì)員的基本原則,基本要求 人品好 愿意花時間在這項(xiàng)賽事上 有團(tuán)隊(duì)合作精神 能力要求 程序設(shè)計(jì) 英語科技文獻(xiàn)閱讀 數(shù)學(xué),2020/7/28,16,杭電參賽歷程,2020/7/28,17,HDU-ACM* 集訓(xùn)隊(duì)*,2020/7/28,18,放松完畢 回到正題,2020/7/28,19,開課目的,為杭電ACM代表隊(duì)培養(yǎng)后備人才

7、 提高分析問題和應(yīng)用計(jì)算機(jī)編程解決問題的能力 培養(yǎng)必要的自學(xué)能力 培養(yǎng)學(xué)生的協(xié)調(diào)和溝通能力 體會學(xué)習(xí)的快樂,2020/7/28,20,如何入門呢?,2020/7/28,21,ACM題目特點(diǎn):,由于ACM競賽題目的輸入數(shù)據(jù)和輸出數(shù)據(jù)一般有多組（不定），并且格式多種多樣，所以，如何處理題目的輸入輸出是對大家的一項(xiàng)最基本的要求。這也是困擾初學(xué)者的一大問題。 下面，分類介紹：,2020/7/28,22,先看一個超級簡單的題目：, Sample input: 1 5 10 20 Sample output: 6 30,2020/7/28,23,初學(xué)者很常見的一種寫法：,#include void mai

8、n() int a,b; scanf(“%d %d”, ,2020/7/28,24,有什么問題呢？,這就是下面需要解決的問題,2020/7/28,25,第二部分,基本輸入輸出,2020/7/28,26,輸入_第一類：,輸入不說明有多少個Input Block,以EOF為結(jié)束標(biāo)志。 參見：HDOJ_1089 ,2020/7/28,27,Hdoj_1089源代碼：,#include int main() int a,b; while(scanf(%d %d, ,2020/7/28,28,本類輸入解決方案：,C語法： while(scanf(%d %d, scanf(%d, ,2020/7/28,3

9、2,本類輸入解決方案：,C語法： scanf(%d, i+ ) . ,2020/7/28,33,輸入_第三類：,輸入不說明有多少個Input Block,但以某個特殊輸入為結(jié)束標(biāo)志。 參見：HDOJ_1091 ,2020/7/28,34,Hdoj_1091源代碼：,#include int main() int a,b; while(scanf(%d %d, ,上面的程序有什么問題？,2020/7/28,35,本類輸入解決方案：,C語法： while(scanf(%d, gets(buf); C+語法： 如果用string buf;來保存： getline( cin , buf ); 如果用c

10、har buf 255 ; 來保存： cin.getline( buf, 255 );,2020/7/28,39,說明（5_1）：,scanf(“ %s%s”,str1,str2)，在多個字符串之間用一個或多個空格分隔； 若使用gets函數(shù)，應(yīng)為gets(str1); gets(str2); 字符串之間用回車符作分隔。 通常情況下，接受短字符用scanf函數(shù)，接受長字符用gets函數(shù)。 而getchar函數(shù)每次只接受一個字符，經(jīng)常c=getchar()這樣來使用。,2020/7/28,40,說明（5_2）：cin.getline的用法：,getline 是一個函數(shù)，它可以接受用戶的輸入的字符，

11、直到已達(dá)指定個數(shù)，或者用戶輸入了特定的字符。它的函數(shù)聲明形式（函數(shù)原型）如下： istream 不用管它的返回類型，來關(guān)心它的三個參數(shù)： char line： 就是一個字符數(shù)組，用戶輸入的內(nèi)容將存入在該數(shù)組內(nèi)。 int size : 最多接受幾個字符？用戶超過size的輸入都將不被接受。 char endchar :當(dāng)用戶輸入endchar指定的字符時，自動結(jié)束。默認(rèn)是回車符。,2020/7/28,41,說明（5_2）續(xù),結(jié)合后兩個參數(shù)，getline可以方便地實(shí)現(xiàn)： 用戶最多輸入指定個數(shù)的字符，如果超過，則僅指定個數(shù)的前面字符有效，如果沒有超過，則用戶可以通過回車來結(jié)束輸入。 char na

12、me4; cin.getline(name,4,n); 由于 endchar 默認(rèn)已經(jīng)是 n，所以后面那行也可以寫成： cin.getline(name,4);,2020/7/28,42,思考：以下題目屬于哪一類輸入？, ,2020/7/28,43,輸出_第一類：,一個Input Block對應(yīng)一個Output Block，Output Block之間沒有空行。 參見：HDOJ_1089 ,2020/7/28,44,解決方案：,C語法： . printf(%dn,ans); C+語法： . cout ans endl; ,2020/7/28,45,輸出_第二類：,一個Input Block對應(yīng)

13、一個Output Block，每個Output Block之后都有空行。參見：HDOJ_1095 ,2020/7/28,46,1095源代碼,#include int main() int a,b; while(scanf(%d %d, ,2020/7/28,47,解決辦法：,C語法： . printf(%dnn,ans); C+語法： . cout ans endl endl; ,2020/7/28,48,輸出_第三類：,一個Input Block對應(yīng)一個Output Block，Output Block之間有空行。 參見：HDOJ_1096 ,2020/7/28,49,1096源代碼,#i

14、nclude int main() int icase,n,i,j,a,sum; scanf(%d, ,2020/7/28,50,解決辦法：,C語法： for (k=0;kcount;k+) while () printf( %dn,result); if (k!=count-1) printf(n); C+語法： 類似，輸出語句換一下即可。,2020/7/28,51,思考：以下題目屬于哪一類輸出？, ,2020/7/28,52,附: 初學(xué)者常見問題,2020/7/28,53,一、編譯錯誤,Main函數(shù)必須返回int類型(正式比賽) 不要在for語句中定義類型 _int64不支持，可以用lon

15、g long代替 使用了漢語的標(biāo)點(diǎn)符號 itoa不是ansi函數(shù) 能將整數(shù)轉(zhuǎn)換為字符串而且與ANSI標(biāo)準(zhǔn)兼容的方法是使用sprintf()函數(shù) int num = 100; char str25; sprintf(str, %d , num); 另外，拷貝程序容易產(chǎn)生錯誤,2020/7/28,54,下面的hdoj1089為什么 CE?,#include int main() int a,b; while(scanf(%d %d, ,2020/7/28,55,二、小技巧,數(shù)據(jù)的拷貝（特別是輸出的提示信息） 調(diào)試的sample input的拷貝,2020/7/28,56,三、C語言處理“混合數(shù)據(jù)”

16、的問題,例題（Hdoj_1170） ,2020/7/28,57,常見的代碼：, scanf(%dn, ,2020/7/28,58,有什么問題？,2020/7/28,59,四、Printf和cout混用的問題,以下的程序輸出什么？ #include #include int main() int j=0; for(j=0;j5;j+) coutj=; printf(%dn,j); return 0; ,2020/7/28,60,為什么？,一個帶緩沖輸出（cout） 一個不帶緩沖輸出(printf),2020/7/28,61,五、輸入輸出原理,Input 1 5 2 6 10 20 111 111

17、 321 123,Output 6 8 30 222 444,2020/7/28,62,思考題(目的：初步體會一下ACM的魅力),Given two non-negative integers m and n, you will have to find the last digit of mn in decimal number system. Input The input file contains several lines. Each line contains two integers m and n (both less than 101001). Input is termin

18、ated by a line containing two zeroes. This line should not be processed. Output For each set of input you must produce one line of output which contains a single digit. This digit is the last digit of mn. Sample Input 3 2 3 5 0 0 Sample Output 9 3,2020/7/28,63,授課方式與成績評定,介紹常用算法 舉例分析 上機(jī)練習(xí)（自己在線練習(xí)） 成績評定：機(jī)試 ( 5 6 題 ),2020/7/28,64,相關(guān)資料,數(shù)學(xué)知識 離散、組合 數(shù)論、圖論 計(jì)算幾何 算法&數(shù)據(jù)結(jié)構(gòu) 基本數(shù)據(jù)結(jié)構(gòu) 搜索、分治 動態(tài)規(guī)劃 貪心,2020/7/28,65,學(xué)習(xí)方式,練習(xí)-總結(jié)-練習(xí)-總結(jié)- 杭電ACM論壇 google、baid