杭電acm初學(xué)者的課件

杭電acm初學(xué)者的課件2024/4/162第一講ACM入門2024/4/163第一部分初識ACM2024/4/164

ACM(AssociationforComputingMachinery)

成立于計(jì)算機(jī)誕生次年，是目前計(jì)算機(jī)學(xué)界中歷史最悠久、最具權(quán)威性的組織…WhatisACM?2024/4/165我們說的“ACM”

是什么？2024/4/166ACM/ICPC：

ACM主辦的國際大學(xué)生程序設(shè)計(jì)競賽(InternationalCollegiateProgrammingContest)，簡稱ACM/ICPC，自從1977年開始至今已經(jīng)連續(xù)舉辦31屆。其宗旨是提供一個讓大學(xué)生向IT界展示自己分析問題和解決問題的能力的絕好機(jī)會，讓下一代IT天才可以接觸到其今后工作中將要用到的各種軟件。

現(xiàn)在，ACM/ICPC已成為世界各國大學(xué)生中最具影響力的國際計(jì)算機(jī)賽事。（非官方）2024/4/167ACM/ICPCinChina

中國大陸高校從1996年開始參加ACM國際大學(xué)生程序設(shè)計(jì)競賽亞洲預(yù)賽。前六屆中國賽區(qū)設(shè)在上海，由上海大學(xué)承辦；2002年由清華大學(xué)和西安交通大學(xué)承辦；2003年由清華大學(xué)和中山大學(xué)承辦。2004年由北京大學(xué)和上海交通大學(xué)承辦。2005年由四川大學(xué)、北大和浙大承辦。2006年由上海大學(xué)、清華和西電承辦。2007年：北航、南航、吉大、西華2024/4/1682024/4/169ACMinHDU2003年9月，第一次參加省賽（邀請賽）2004年5月，浙江省“舜宇”杯首屆大學(xué)生程序設(shè)計(jì)大賽2004年11~12月，第29屆ACM亞洲區(qū)北京和上海賽區(qū)比賽2005年5月,浙江省第二屆“舜宇”杯大學(xué)生程序設(shè)計(jì)大賽2005年11月,參加中國大陸的三站亞洲區(qū)比賽2006年5月,浙江省第二屆“舜宇”杯大學(xué)生程序設(shè)計(jì)大賽2006年11~12月，第31屆ACM首爾、北京、上海和西安賽區(qū)比賽今年…2024/4/1610預(yù)期賽事（今后每年）3~4月，舉行校內(nèi)大賽（暨選拔賽）5月，參加浙江省大學(xué)生程序設(shè)計(jì)大賽11月，參加ACM/ICPC亞洲區(qū)比賽（至少參加4～5個賽區(qū)的比賽）另外，每學(xué)期至少有三次月賽以及適當(dāng)?shù)木毩?xí)賽2024/4/1611如何比賽？

3人組隊(duì)

可以攜帶諸如書、手冊、程序清單等參考資料；不能攜帶任何可用計(jì)算機(jī)處理的軟件或數(shù)據(jù)、不能攜帶任何類型的通訊工具；可能收到的反饋信息包括：

CompileError--程序不能通過編譯。

RunTimeError--程序運(yùn)行過程中出現(xiàn)非正常中斷。

TimeLimitExceeded

--運(yùn)行超過時限還沒有得到輸出結(jié)果。

WrongAnswer--答案錯誤。

PresentationError

--輸出格式不對，可檢查空格、回車等等細(xì)節(jié)。

Accepted--恭喜恭喜！

2024/4/1612首先根據(jù)解題數(shù)目進(jìn)行排名。如果多支隊(duì)伍解題數(shù)量相同，則根據(jù)總用時加上懲罰時間進(jìn)行排名?？傆脮r和懲罰時間由每道解答正確的試題的用時加上懲罰時間而成。每道試題用時將從競賽開始到試題解答被判定為正確為止，其間每一次錯誤的運(yùn)行將被加罰20分鐘時間，未正確解答的試題不記時。如何排名？2024/4/1613比賽形式1支隊(duì)伍1臺機(jī)器（提供打印服務(wù)）上機(jī)編程解決問題（可帶紙質(zhì)資料）實(shí)時測試，動態(tài)排名試題6-10題全英文（可以帶字典）時間：持續(xù)5個小時2024/4/1614ACM.vs.校程序設(shè)計(jì)競賽ACM競賽團(tuán)隊(duì)合作精神即時提交，通過所有數(shù)據(jù)才能得分全英文題目，題目考察范圍廣校程序設(shè)計(jì)競賽個人編程能力的比拼中文或者英文題目，考察編程基本功2024/4/1615ACM隊(duì)隊(duì)員的基本原則基本要求人品好愿意花時間在這項(xiàng)賽事上有團(tuán)隊(duì)合作精神能力要求程序設(shè)計(jì)英語科技文獻(xiàn)閱讀數(shù)學(xué)2024/4/1616杭電參賽歷程2024/4/1617HDU-ACM

*集訓(xùn)隊(duì)*2024/4/1618放松完畢

回到正題

2024/4/1619開課目的為杭電ACM代表隊(duì)培養(yǎng)后備人才提高分析問題和應(yīng)用計(jì)算機(jī)編程解決問題的能力培養(yǎng)必要的自學(xué)能力培養(yǎng)學(xué)生的協(xié)調(diào)和溝通能力體會學(xué)習(xí)的快樂2024/4/1620如何入門呢?2024/4/1621ACM題目特點(diǎn):

由于ACM競賽題目的輸入數(shù)據(jù)和輸出數(shù)據(jù)一般有多組（不定），并且格式多種多樣，所以，如何處理題目的輸入輸出是對大家的一項(xiàng)最基本的要求。這也是困擾初學(xué)者的一大問題。 下面，分類介紹：2024/4/1622先看一個超級簡單的題目：Sleinput:151020Sleoutput:6302024/4/1623初學(xué)者很常見的一種寫法：#include<stdio.h>voidmain(){inta,b;scanf(“%d%d”,&a,&b);Printf(“%d”,a+b);}2024/4/1624有什么問題呢？這就是下面需要解決的問題2024/4/1625第二部分基本輸入輸出2024/4/1626輸入_第一類：輸入不說明有多少個InputBlock,以EOF為結(jié)束標(biāo)志。

參見：HDOJ_10892024/4/1627Hdoj_1089源代碼：#include<stdio.h>intmain(){inta,b; while(scanf("%d%d",&a,&b)!=EOF) printf("%d\n",a+b);}

2024/4/1628本類輸入解決方案：C語法：

while(scanf("%d%d",&a,&b)!=EOF) {

....

}C++語法：

while(cin>>a>>b)

{

....

}2024/4/1629說明（1）：Scanf函數(shù)返回值就是讀出的變量個數(shù)，如：scanf(“%d%d”,&a,&b);

如果只有一個整數(shù)輸入，返回值是1，如果有兩個整數(shù)輸入，返回值是2，如果一個都沒有，則返回值是-1。EOF是一個預(yù)定義的常量，等于-1。2024/4/1630輸入_第二類：輸入一開始就會說有N個InputBlock,下面接著是N個InputBlock。

參見：HDOJ_10902024/4/1631Hdoj_1090源代碼：#include<stdio.h>intmain(){intn,i,a,b; scanf("%d",&n);for(i=0;i<n;i++){ scanf("%d%d",&a,&b); printf("%d\n",a+b);}}2024/4/1632本類輸入解決方案：C語法：

scanf("%d",&n); for(i=0;i<n;i++)

{

....

}C++語法：

cin>>n;

for(i=0;i<n;i++)

{

....

}2024/4/1633輸入_第三類：輸入不說明有多少個InputBlock,但以某個特殊輸入為結(jié)束標(biāo)志。 參見：HDOJ_10912024/4/1634Hdoj_1091源代碼：#include<stdio.h>intmain(){ inta,b;

while(scanf("%d%d",&a,&b)&&(a!=0&&b!=0)) printf("%d\n",a+b);}上面的程序有什么問題？2024/4/1635本類輸入解決方案：C語法：

while(scanf("%d",&n)&&n!=0) {

....

}C++語法：

while(cin>>n&&n!=0)

{

....

}2024/4/1636輸入_第四類：以上幾種情況的組合2024/4/1637輸入_第五類：輸入是一整行的字符串的

參見：HDOJ_10482024/4/1638本類輸入解決方案：C語法：

charbuf[20];

gets(buf);

C++語法： 如果用stringbuf;來保存：

getline(cin,buf);

如果用charbuf[255];來保存：

cin.getline(buf,255);2024/4/1639說明（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()這樣來使用。

2024/4/1640說明（5_2）：cin.getline的用法：getline是一個函數(shù)，它可以接受用戶的輸入的字符，直到已達(dá)指定個數(shù)，或者用戶輸入了特定的字符。它的函數(shù)聲明形式（函數(shù)原型）如下：

istream&getline(charline[],intsize,charendchar='\n');不用管它的返回類型，來關(guān)心它的三個參數(shù)：charline[]：就是一個字符數(shù)組，用戶輸入的內(nèi)容將存入在該數(shù)組內(nèi)。intsize:最多接受幾個字符？用戶超過size的輸入都將不被接受。charendchar:當(dāng)用戶輸入endchar指定的字符時，自動結(jié)束。默認(rèn)是回車符。2024/4/1641說明（5_2）續(xù)結(jié)合后兩個參數(shù)，getline可以方便地實(shí)現(xiàn)：用戶最多輸入指定個數(shù)的字符，如果超過，則僅指定個數(shù)的前面字符有效，如果沒有超過，則用戶可以通過回車來結(jié)束輸入。charname[4];cin.getline(name,4,'\n');由于endchar默認(rèn)已經(jīng)是'\n'，所以后面那行也可以寫成：cin.getline(name,4);2024/4/1642思考：

以下題目屬于哪一類輸入？2024/4/1643輸出_第一類：一個InputBlock對應(yīng)一個OutputBlock，OutputBlock之間沒有空行。

參見：HDOJ_10892024/4/1644解決方案：C語法：

{

....

printf("%d\n",ans); }C++語法：

{

...

cout<<ans<<endl;

}2024/4/1645輸出_第二類：一個InputBlock對應(yīng)一個OutputBlock，每個OutputBlock之后都有空行。

參見：HDOJ_1095

2024/4/16461095源代碼#include<stdio.h>intmain(){inta,b; while(scanf("%d%d",&a,&b)!=EOF) printf("%d\n\n",a+b);}2024/4/1647解決辦法：C語法：

{

....

printf("%d\n\n",ans); }C++語法：

{

...

cout<<ans<<endl<<endl;

}2024/4/1648輸出_第三類：一個InputBlock對應(yīng)一個OutputBlock，OutputBlock之間有空行。

參見：HDOJ_10962024/4/16491096源代碼#include<stdio.h>intmain(){inticase,n,i,j,a,sum;scanf("%d",&icase);for(i=0;i<icase;i++){ sum=0;scanf("%d",&n); for(j=0;j<n;j++) { scanf("%d",&a);sum+=a; } if(i<icase-1) printf("%d\n\n",sum);else printf("%d\n",sum);}}2024/4/1650解決辦法：C語法：

for(k=0;k<count;k++)

{

while(…)

{

printf("%d\n",result);

}

if(k!=count-1)printf("\n");

}

C++語法： 類似，輸出語句換一下即可。2024/4/1651思考：

以下題目屬于哪一類輸出？2024/4/1652附:初學(xué)者常見問題2024/4/1653一、編譯錯誤Main函數(shù)必須返回int類型(正式比賽)不要在for語句中定義類型__int64不支持，可以用longlong代替使用了漢語的標(biāo)點(diǎn)符號itoa不是ansi函數(shù)能將整數(shù)轉(zhuǎn)換為字符串而且與ANSI標(biāo)準(zhǔn)兼容的方法是使用sprintf()函數(shù)

intnum=100;

charstr[25];

sprintf(str,"%d",num);

另外，拷貝程序容易產(chǎn)生錯誤2024/4/1654下面的hdoj1089為什么CE?#include<stdio.h>intmain(){inta,b; while(scanf("%d%d",&a,&b)!=EOF) printf("%d\n",a+b);}

2024/4/1655二、小技巧數(shù)據(jù)的拷貝（特別是輸出的提示信息）調(diào)試的sleinput的拷貝2024/4/1656三、C語言處理“混合數(shù)據(jù)”的問題例題（Hdoj_1170）2024/4/1657常見的代碼： ……scanf("%d\n",&icase);for(i=0;i<icase;i++){scanf("%c%d%d",&opera,&num1,&num2);……}……2024/4/1658有什么問題？2024/4/1659四、Printf和cout混用的問題以下的程序輸出什么？#include<stdio.h>#include<iostream.h>intmain(){ intj=0; for(j=0;j<5;j++) { cout<<"j="; printf("%d\n",j); } return0;}2024/4/1660為什么？一個帶緩沖輸出（cout）一個不帶緩沖輸出(printf)2024/4/1661五、輸入輸出原理Input15261020111111321123Output68302224442024/4/1662思考題(目的：初步體會一下ACM的魅力) Giventwonon-negativeintegersmandn,youwillhavetofindthelastdigitofmnindecimalnumbersystem.InputTheinputfilecontainsseverallines.Eachlinecontainstwointegersmandn(bothlessthan101001