ACM培訓(xùn)輸入輸出處理需要掌握的知識(shí)參考資料常用術(shù)語(yǔ)ICPC(InternationalCollegiateProgrammingContest) 國(guó)際大學(xué)生程序設(shè)計(jì)競(jìng)賽AC(Accepted)程序通過(guò)WA(WrongAnswer)錯(cuò)誤的答案 (讀做“哇”)PE(PresentationError)輸出格式錯(cuò)誤RE(RuntimeError)程序執(zhí)行錯(cuò)誤(常見(jiàn)于數(shù)組溢出、遞歸層數(shù)太多...)CE(CompileError)編譯錯(cuò)誤MLE(MemoryLimitExceeded)內(nèi)存超界(正式比賽沒(méi)有內(nèi)存限制，但如果用太多可能RE)TLE(TimeLimitExceed)程序超時(shí)錯(cuò)誤(死循環(huán)或算法有問(wèn)題)OLE(OutputLimitExceed)輸出超界(一般不太常見(jiàn)，除非你輸出了超過(guò)1024K...)

DP(DynamicProgramming)動(dòng)態(tài)編程，動(dòng)態(tài)規(guī)劃DFS(DepthFirstSearch)深度優(yōu)先搜索BFS(BreadthFirstSearch)寬度/廣度優(yōu)先搜索LCS(LongestCommonSubsequence)最長(zhǎng)公共子串輸入輸出C: scanf 速度快

printf 格式容易控制C++:cin 使用簡(jiǎn)單,自動(dòng)識(shí)別類(lèi)型cout 格式控制較麻煩 數(shù)據(jù)規(guī)模較大時(shí),推薦(必須)使用scanf以避免超時(shí)(TLE)

輸入輸出cout:帶緩沖輸出printf:不帶緩沖輸出C和C++的輸入輸出混合使用至于cout的緩存問(wèn)題，五種情況會(huì)刷緩沖:\n（我試下來(lái)是要刷的）endlflush緩沖區(qū)滿(mǎn)程序結(jié)束輸入輸出#include<stdio.h>#include<iostream.h>intmain(){ for(intj=0;j<5;j++) { cout<<"j="; printf("%d\n",j); } return0;}j=0j=1j=2j=3j=401234j=j=j=j=j=輸入輸出scanf輸入格式%d%lld%c%s%lf對(duì)每種格式搞清楚一個(gè)重要問(wèn)題是否自動(dòng)跳過(guò)前導(dǎo)空白？什么是空白：空格，TAB，回車(chē)輸入輸出%d%lld%lf自動(dòng)掃描前導(dǎo)空格比如：讀入5個(gè)整數(shù)到A[5]輸入文件中，數(shù)的排布是這個(gè)樣子352678

99206不管它，直接5次%dfor(inti=0;i<5;i++)scanf(“%d”,A+i);%lld用于輸入和輸出長(zhǎng)整數(shù)(longlong,64位)%lf用于輸入輸出double輸入輸出%s讀一個(gè)字符串，自動(dòng)掃描前導(dǎo)空白，讀到空白結(jié)束如：abcdefgh，將讀出”abcd”%c讀一個(gè)字符，但是不掃描前導(dǎo)空白如何讀一個(gè)非空白字符呢？比如，讀取某人的信息，其性別用M/F表示TopBoyMComputerScienceKittyFSoftware名字和專(zhuān)業(yè)用%s讀，性別怎么辦?自己過(guò)濾空格？麻煩！輸入輸出讀一個(gè)非空白字符，方法一:charstr[2];scanf(“%1s”,str);//%1s掃描前導(dǎo)空白，并且只讀一個(gè)字符charc=str[0];方法二:強(qiáng)制掃描空白在%前面加上一個(gè)空格表示“強(qiáng)制掃描前導(dǎo)空白”scanf(“%c”,&ch);前面那個(gè)讀人物信息的完整scanf語(yǔ)句：scanf(“%s%c%s”,name,&gender,ability);輸入輸出同理,我們也可以用其它字符來(lái)掃描其它類(lèi)型的無(wú)關(guān)輸入比如,輸入年月日的信息2007-08-03scanf(“%d-%d-%d”,&y,&m,&d);其它類(lèi)似浮點(diǎn)數(shù)的輸入問(wèn)題為什么說(shuō)while(in!=0.00)不合理呢?如果不合理應(yīng)該怎么判斷！！while(in!=0.00)是不太好，浮點(diǎn)數(shù)的判斷不能這樣比較，因?yàn)闋可娴骄鹊膯?wèn)題應(yīng)該用e=in-num，然后判斷e輸入輸出的技巧輸入輸出的問(wèn)題：輸入部分:1.輸入一開(kāi)始就會(huì)說(shuō)有N個(gè)InputBlock,下面接著是N個(gè)InputBlock

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

{

....

}

2.輸入不說(shuō)明有多少個(gè)InputBlock,但以某個(gè)特殊輸入為結(jié)束標(biāo)志

while(scanf("%d",&n)!=EOF&&n!=0)orwhilewhile(cin>>n&&n!=0)

{

....

}

3.輸入不說(shuō)明有多少個(gè)InputBlock,以EOF為結(jié)束標(biāo)志

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

{

....

}

while(cin>>a>>b)

{

....

4.輸入是一整行的字符串的

charbuf[255];

gets(buf);

charbuf[255];

cin.getline(buf,255);輸出部分：1.一個(gè)InputBlock對(duì)應(yīng)一個(gè)OutputBlock，OutputBlock之間沒(méi)有空行

...

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

...

...

cout<<ans<<endl;

...

2.一個(gè)InputBlock對(duì)應(yīng)一個(gè)OutputBlock，OutputBlock之間有空行。

intcasenum=0;

...

{

if(casenum++)putchar('\n');

...

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

}

intcasenum=0;

...

{

if(casenum++)cout<<endl;

...

cout<<ans<<endl;

}3.一個(gè)InputBlock對(duì)應(yīng)一個(gè)OutputBlock，每個(gè)OutputBlock之后都有空行。

...

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

...

...

cout<<ans<<endl<<endl;

...

其他說(shuō)明：1.EOF是一個(gè)標(biāo)志（常量），不是字符串"EOF"，用鍵盤(pán)的輸入方法是Ctrl+Z2.最好不要把C和C++的輸入輸出語(yǔ)句混著用，會(huì)造成一些莫名其妙的問(wèn)題3.我個(gè)人傾向于使用純C的輸入輸出，因?yàn)榉奖闱宜俣瓤臁?/p>

關(guān)于重定向操作當(dāng)程序要輸入的內(nèi)容很多時(shí)，從文件讀入的操作變得非常重要,特別是需要調(diào)試時(shí)，這樣可以避免你反復(fù)的從鍵盤(pán)敲入重復(fù)的內(nèi)容。使用標(biāo)準(zhǔn)輸入語(yǔ)句,可以使用重定向命令行輸入命令:Test.exe<in.dat>out.dat最好不要進(jìn)行函數(shù)聲明變量定義在使用之前避免 for(inti=0;i<n;i++)i的使用范圍僅僅在for{}內(nèi)部，容易導(dǎo)致CE遇到問(wèn)題首先自己查找資料，之后再提問(wèn)例子FactorialTimeLimit:1000MS

MemoryLimit:65536KDescriptionCaculaten!.InputTheinputshouldconsistofaseriesofcases.Ineverycasethereshouldbeaninteger,n(nislessthan21).Onelinepercase.OutputForeachcaseyoushouldoutputthethevalueofn!.SampleInput23SampleOutput26考慮輸入intmain(){ while(cin>>n){

} }例子intmain(){ intn,res; while(cin>>n){ res=1; for(inti=2;i<=n;i++)res*=i; cout<<res<<endl; } }WrongAnswerFactorialTimeLimit:1000MS

MemoryLimit:65536KDescriptionCaculaten!.InputTheinputshouldconsistofaseriesofcases.Ineverycasethereshouldbeaninteger,n(nislessthan21).Onelinepercase.OutputForeachcaseyoushouldoutputthethevalueofn!.SampleInput23SampleOutput2620!=

24329000Int32位取值范圍是-2147483648~214748364720!=

2432900020-2102132736類(lèi)似問(wèn)題:數(shù)據(jù)范圍:決定使用什么類(lèi)型數(shù)據(jù)規(guī)模:決定開(kāi)多大的數(shù)組#defineMAX10005宜大不宜小注意事項(xiàng)三個(gè)方向：Algorithm（算法）Math（數(shù)學(xué)）Realization（實(shí)現(xiàn)）三種能力：EnglishReadingSelf-learningTeamwork需要哪些知識(shí)不完全列表排序算法（平方排序算法的應(yīng)用，Shell排序，快速排序，歸并排序，時(shí)間復(fù)雜度下界，三種線性時(shí)間排序，外部排序）數(shù)論（整除，集合論，關(guān)系，素?cái)?shù)，進(jìn)位制，輾轉(zhuǎn)相除，擴(kuò)展的輾轉(zhuǎn)相除，同余運(yùn)算，解線性同余方程，中國(guó)剩余定理）指針（鏈表，搜索判重，鄰接表，開(kāi)散列，二叉樹(shù)的表示，多叉樹(shù)的表示）按位運(yùn)算（and，or，xor，shl，shr，一些應(yīng)用）圖論（圖論模型的建立，平面圖，歐拉公式與五色定理，求強(qiáng)連通分量，求割點(diǎn)和橋，歐拉回路，AOV問(wèn)題，AOE問(wèn)題，最小生成樹(shù)的三種算法，最短路的三種算法，標(biāo)號(hào)法，差分約束系統(tǒng)，驗(yàn)證二分圖，Konig定理，匈牙利算法，KM算法，穩(wěn)定婚姻系統(tǒng)，最大流算法，最小割最大流定理，最小費(fèi)用最大流算法）計(jì)算幾何（平面解幾及其應(yīng)用，向量，點(diǎn)積及其應(yīng)用，叉積及其應(yīng)用，半平面相交，求點(diǎn)集的凸包，最近點(diǎn)對(duì)問(wèn)題，凸多邊形的交，離散化與掃描）數(shù)據(jù)結(jié)構(gòu)（廣度優(yōu)先搜索，驗(yàn)證括號(hào)匹配，表達(dá)式計(jì)算，遞歸的編譯，Hash表，分段Hash，并查集，Tarjan算法，二叉堆，左偏樹(shù)，斜堆，二項(xiàng)堆，二叉查找樹(shù)，AVL，Treap，Splay，靜態(tài)二叉查找樹(shù)，2-d樹(shù)，線段樹(shù)，二維線段樹(shù)，矩形樹(shù)，Trie樹(shù)，塊狀鏈表）組合數(shù)學(xué)（排列與組合，鴿籠原理，容斥原理，遞推，F(xiàn)ibonacci數(shù)列，Catalan數(shù)列，Stirling數(shù)，差分序列，生成函數(shù)，置換，Polya原理）概率論（簡(jiǎn)單概率，條件概率，Bayes定理，期望值）矩陣（矩陣的概念和運(yùn)算，二分求解線性遞推方程，多米諾骨牌棋盤(pán)覆蓋方案數(shù)，高斯消元）字符串處理（KMP，后綴樹(shù)，有限狀態(tài)自動(dòng)機(jī)，Huffman編碼，簡(jiǎn)單密碼學(xué)）動(dòng)態(tài)規(guī)劃（單調(diào)隊(duì)列，凸完全單調(diào)性，樹(shù)型動(dòng)規(guī)，多叉轉(zhuǎn)二叉，狀態(tài)壓縮類(lèi)動(dòng)規(guī)，四邊形不等式）博奕論（Nim取子游戲，博弈樹(shù)，Shannon開(kāi)關(guān)游戲）搜索（A*，ID，IDA*，隨機(jī)調(diào)整，遺傳算法）微積分初步（極限思想，導(dǎo)數(shù)，積分，定積分，立體解析幾何）如何獲取知識(shí)讀書(shū)算法導(dǎo)論(IntroductiontoAlgorithms)組合數(shù)學(xué)數(shù)據(jù)結(jié)構(gòu)計(jì)算機(jī)算法設(shè)計(jì)與分析如何獲取知識(shí)讀論文歷年國(guó)家集訓(xùn)隊(duì)論文(中學(xué)生的論文)讀程序用批判+學(xué)習(xí)的眼光去讀別人的程序讀論文歷年國(guó)家集訓(xùn)隊(duì)論文(中學(xué)生的論文)網(wǎng)絡(luò)資料聚寶盆(博客)實(shí)踐篇寫(xiě)算法看書(shū),讀論文等的過(guò)程中,自己動(dòng)手把算法實(shí)現(xiàn)做題如數(shù)學(xué)一樣,是做出來(lái)的,不是想出來(lái)的動(dòng)手無(wú)論你是想做好ACM訓(xùn)練

還是想學(xué)好編程

請(qǐng)多動(dòng)手寫(xiě)程序