初識ACM.ppt

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

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

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

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

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

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

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

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

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

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

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

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

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

14、ck之后都有空行。參見：HDOJ_1095 ,2020/7/28,51,1095源代碼,#include int main() int a,b; while(scanf(%d %d, ,2020/7/28,52,解決辦法：,C語法： . printf(%dnn,ans); C+語法： . cout ans endl endl; ,2020/7/28,53,輸出_第三類：,一個Input Block對應一個Output Block，Output Block之間有空行。 參見：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語法： for (k=0;kcount;k+) while () printf( %dn,result); if (k!=count-1) printf(n); C+語法： 類似，輸出語句換一下即可。,2020/7/28,56,思考：以下題目屬于哪一類輸出？, ,2020/7/28,57,附: 初學者常見問題,2020/7/28,58,一、編譯錯誤,Main函數(shù)必須返回int類型(正式比賽) 不要在for語句中定義類型 _int64不支持，可以用long long代替 使用了漢語的標點符號 itoa不是a

16、nsi函數(shù) 能將整數(shù)轉(zhuǎn)換為字符串而且與ANSI標準兼容的方法是使用sprintf()函數(shù) int num = 100; char str25; sprintf(str, %d , num); 另外，拷貝程序容易產(chǎn)生錯誤,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語言處理“混合數(shù)據(jù)”的問題,例題（Hdoj_1170） ,2020/7/2

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