上海大學(xué)ACM集訓(xùn)隊(duì)培訓(xùn)資料(內(nèi)部使用)

上海大學(xué)ACM/icpc上海大學(xué)ACM/icpc集訓(xùn)隊(duì) 何琪辰2007.3.25#上海大學(xué)ACM集訓(xùn)隊(duì)培訓(xùn)資料(內(nèi)部使用)一、C++基礎(chǔ)基本知識所有的C++程序都是有函數(shù)組成的，函數(shù)又叫做子程序，且每個(gè)C++程序必須包含一個(gè)main函數(shù)，編譯器(能夠把源代碼轉(zhuǎn)換成目標(biāo)代碼的程序)把翻譯后的目標(biāo)代碼和一些啟動代碼組合起來，生成可執(zhí)行文件，main函數(shù)就是可執(zhí)行文件的入口，所以，每個(gè)C++程序有且只有一個(gè)main函數(shù)。下面我們看一個(gè)最簡單C++程序。(程序1.1)程序1.1intmain(){return0;}在這個(gè)程序中，如果缺少任何一個(gè)字符，編譯器就無法將其翻譯成機(jī)器代碼。此外，C++是對大小寫敏感的，這就意味著，如果我將mian()函數(shù)拼為Main(),哪么，編譯器在編譯這段程序的時(shí)候就會出錯(cuò)。編輯源文件能夠提共管理程序開發(fā)的所有步驟，包括編輯的程序成為集成開發(fā)環(huán)境(integrateddevelopmentevironments,IDE)o在windows系統(tǒng)下，使用較為廣泛的有MicrosoftVisualC++、Dev-Cpp等，在UNIX系統(tǒng)下，有Vim、emacs、eclipes等。這些程序都能提供一個(gè)較好的開發(fā)平臺，使我們能夠方便的開發(fā)一個(gè)程序，接下我們所要了解的都是標(biāo)準(zhǔn)C++,所有源代碼都在Dev-cpp下編寫，能夠編譯通過。如果我們修改程序1.1中的main()函數(shù)的名稱，將其改為Main(),那么，IDE就會給出錯(cuò)誤信息，比如“[Linkererror]undefinedreferenceto'WinMain@16'”，因?yàn)榫幾g器沒有找到main函數(shù)。接下來，我們來看一個(gè)經(jīng)典的C++例子(程序1.2)程序1.2#include<iostream>usingnamespacestd;intmain(void){cout<<"HelloWrold!"<<endl;return0;}運(yùn)行結(jié)果HelloWorld!程序說明第一行“#include<iostream>"，是一句預(yù)處理命令，相當(dāng)于把“iostream”這個(gè)文件的所有內(nèi)容復(fù)制到當(dāng)前位置，替換該行。因?yàn)樵谳敵霾僮髦行枰龊芏嗍?，C++編譯器就提供了很多已經(jīng)寫好的函數(shù)(成為C++標(biāo)準(zhǔn)庫)，我們做的只是拿來用就可以了。第二行的“usingnamespacestd;”是使用標(biāo)準(zhǔn)命名空間，因?yàn)槲覀冊诔绦蛑杏玫搅嗽跇?biāo)準(zhǔn)命名空間里的函數(shù)和對象。目前可以不了解其具體如何實(shí)現(xiàn)，在以后的程序設(shè)計(jì)中可以再對其進(jìn)行了解。在明函數(shù)中"cout<<”HelloWorld!”<<endl;”是在屏幕上打印“HelloWorld!”，“endl”表明打印完這句話之后需要換行。如果我們替換引號內(nèi)的內(nèi)容，程序的輸出就會相應(yīng)改變。另外一個(gè)C++程序例子//ourfunc.cpp--definingyourownfunction#include<iostream>voidsimon(int);//functionprototypeforsimon()intmain(){usingnamespacestd;simon(3);//callthesimon()functioncout<<"Pickaninteger:";intcount;cin>>count;simon(count);//callitagaincout<<"Done!"<<endl;return0;}voidsimon(intn)//definethesimon()function{usingnamespacestd;cout<<"Simonsaystouchyourtoes"<<n<<"times."<<endl;} //voidfunctionsdon'tneedreturnstatements下面試運(yùn)行情況：Simonsaystouchyourtoes3times.Pickaninteger:512Simonsaystouchyourtoes512times.Done!程序中包含了cin語句來從鍵盤上獲取數(shù)據(jù)。該程序中包含了除main函數(shù)以外的另一個(gè)函數(shù)simon()，他和main函數(shù)定義的格式相同，函數(shù)的統(tǒng)一格式如下：typefunctionname(argumentlist){statements}注意，定義simon()的代碼在main()函數(shù)的后面，C++中不允許將函數(shù)定義在另一個(gè)函數(shù)內(nèi)。每個(gè)函數(shù)的定義都是獨(dú)立的，所有的函數(shù)的創(chuàng)建都是平等的。simon()函數(shù)的函數(shù)頭定義如下：voidsimon(intn)以void開頭表明simon()沒有返回值，因此我們不能類是這樣的使用它。simple=simon(3);有返回值的函數(shù)如下//convert.cpp--convertsstonetopounds#include<iostream>intstonetolb(int);//functionprototypeintmain(){usingnamespacestd;intstone;cout<<"Entertheweightinstone:";cin>>stone;intpounds=stonetolb(stone);cout<<stone<<"stone=";cout<<pounds<<"pounds."<<endl;return0;}intstonetolb(intsts){return14*sts;}下面是運(yùn)行情況：Entertheweightinsone:1414stone=196pounds.程序通過cin語句給stone提供一個(gè)值，然后在main函數(shù)中，把這個(gè)值傳遞給stonetolb()函數(shù)，這個(gè)植被賦給sts之后，stonetolb(^return將14*sts返回給main()。函數(shù)頭中的int表明stonetolb()將返回一個(gè)整數(shù)。除了int類型之外，C++的內(nèi)置數(shù)據(jù)類型還有:unsignedlong、long、unsignedint>unsignedshort、short、char、unsignedchar、signedchar、bool、 float、double、longdouble。對于數(shù)據(jù)的輸入和輸出有幾道練習(xí)題/showproblem.php?pid=1089至/showproblem.php?pid=1096二、算法基礎(chǔ)什么是算法算法是完成特定任務(wù)的有限指令集。所有的算法必須滿足下面的標(biāo)準(zhǔn)：輸入。由外部題共零個(gè)或多個(gè)輸入量。

輸出。至少產(chǎn)生一個(gè)輸出量。明確性。每條指令必須清楚，不具模糊性。有限性。如果跟蹤算法的指令，那么對于所有的情況，算法經(jīng)過有限步以后終止。有效性。每條指令必須非?；A(chǔ)，原則上使用筆和紙就可以實(shí)現(xiàn)例選擇排序voidSelectionSort(Typea[],intn)//Sortthearrata[1:n]intonondecreasingorder.{for(inti=1;i<=n;i++){intj=1;for(intk=i+1;k<=n;k++)if(a[k]<a[j])j=k;Typet=a[i];a[i]=a[j];a[j]=t;}}使用該函數(shù)時(shí)，應(yīng)將Type替換為C++中的數(shù)據(jù)類型3．性能分析程序P所用時(shí)間定義為T(P),T(P)是編譯時(shí)間和運(yùn)行時(shí)間之和。下面我們計(jì)算一下選擇排序運(yùn)行時(shí)所要花費(fèi)的時(shí)間SelectionSortcostTOC\o"1-5"\h\zfor(inti=1;i<=n;i++) c1{intj=1; c2for(intk=i+1;k<=n;k++) c3if(a[k]<a[j]) c4j=k; c5timesnnZ(n-i)itimesnnZ(n-i)i=1Z(n-i)i=1tin那么該算法運(yùn)行的時(shí)間123i=14i=15i6T(n)=cn+cn+cZ(n-i)+cZ(n123i=14i=15i6那么，在最壞的條件下，t的值應(yīng)該是Z(n-i)ii=1所以，算法的運(yùn)行時(shí)間為() 1 1 1 1Tm)=(c+c+c——c——c——c)n+—(c+c+c)n21262342425 23454．漸進(jìn)符號定義：［大0函數(shù)f(n)=O(g(n))，念做f(n)是g(n)的大”oh”，當(dāng)且僅當(dāng)存在正常數(shù)c和n，使得對于所有的n(n>n)，有f(n)<cxg(n)。00例對于所有n>2有3n+2<4n，所以3n+2=O(n)。對于所有n>6有100n+6<101n，所以100n+6=O(n)對于所有n>100有1000n2+100n-6<1001n2，所以1000n2+100n-6=O(n2)當(dāng)然對于所有n>2有100n2+4n+2<10n4，所以10n2+4n+2=O(n4)定義：［0函數(shù)f(n)=Q(g(n))，念做f(n)是g(n)的"omega”，當(dāng)且僅當(dāng)存在正常數(shù)c和n，使得對于所有的n(n>n)，有f(n)>cxg(n)。00例對于所有n>1有6x2n+n2>2n，所以6x2n+n2=Q(2n)。當(dāng)然6x2n+n2=Q(n)，但是Q(n)wQ(2n)?，F(xiàn)然無論是O還是Q，都不能精確的描述一個(gè)函數(shù)定義：［日］函數(shù)f(n)=0(g(n))，念做f(n)是g(n)的”肥1屋，當(dāng)且僅當(dāng)存在正常數(shù)c,c12和n，使得對于所有的n(n>n)，有cg(n)<f(n)<cg(n)。0 01 2例對于n>2有3n+2>3n且3n+2<4n，所以3n+2=0(n)

0記號要比O和Q都要精確。排列生成器0(n!)voidPerm(Typea[],intk,intn){if(k==n){//Outputpermutation.for(inti-1;i<n;i++)cout<<a[i]<<"";}else//a[k:n]hasmorethanonepermutation.//Generatetheserecursively.for(inti=k;i<=n;i++){Typet=a[k];a[k]=a[i];a[i]=t;Perm(a,k+1,n);//Allpermutationsofa[k+1:n]t=a[k];a[k]=a[i];a[i]=t;}}對于下面的程序}else}else{inti;for(i=0;i<n;i++){cout<<a[i]<<'\t';}cout<<endl;}usingnamespacestd;voidPerm(inta[],intk,intn){if(k<n-1){inti,t;for(i=k;i<n;i++){t=a[k]; }a[k]=a[i];a[i]=t;Perm(a,k+1,n);t=a[k];a[i]=t;Perm(a,k+1,n);t=a[k];a[k]=a[i];a[i]=t;}intmain(void){inta[3]={1,2,3};Perm(a,0,3);return0;}該程序的運(yùn)行結(jié)果為1 2 3該程序的運(yùn)行結(jié)果為1 2 31 3 22 1 32 3 13 2 13 1 2那么，該函數(shù)就完成了對一個(gè)數(shù)組進(jìn)行全排列的操作下面，分析該程序，我用圓圈代表每次函數(shù)的調(diào)用每次函數(shù)的調(diào)用都用序號表示那么，該函數(shù)就完成了對一個(gè)數(shù)組進(jìn)行全排列的操作下面，分析該程序，我用圓圈代表每次函數(shù)的調(diào)用每次函數(shù)的調(diào)用都用序號表示a: 2 1 3 k: 2a: 2 3 1 k: 2a: 2 1 3 k: 2a: 2 3 1 k: 2a: 3 2 1 k: 1a: 3 2 1 k: 2a: 3 1 2 k: 2a: 1 23 k: 1a: 1 23 k: 2a: 1 32 k: 2a: 2 13 k: 1排列生成器的另外一個(gè)版本他將輸出給定n個(gè)布爾變量的所有可能的組合voidPerm(boola[],intk,intn){if(k==n){//statement}else{a[k]=true;Perm(a,k+1,n);a[k]=false;Perm(a,k+1,n);}}在上次冬季賽上有這么一道題競賽真理JUNNY在經(jīng)歷了無數(shù)次學(xué)科競賽的失敗以后，得到了一個(gè)真理：做一題就要對一題！但是要完全正確地做對一題是要花很多時(shí)間（包括調(diào)試時(shí)間），而競賽的時(shí)間有限。所以開始做題之前最好先認(rèn)真審題，估計(jì)一下每一題如果要完全正確地做出來所需要的時(shí)間，然后選擇一些有把握的題目先做。當(dāng)然，如果做完了預(yù)先選擇的題目之后還有時(shí)間，但是這些時(shí)間又不足以完全解決一道題目，應(yīng)該把其他的題目用貪心之類的算法隨便做做，爭取“騙”一點(diǎn)分?jǐn)?shù)。根據(jù)每一題解題時(shí)間的估計(jì)值，確定一種做題方案（即哪些題目認(rèn)真做，哪些題目“騙”分，哪些不做），使能在限定的時(shí)間內(nèi)獲得最高的得分。INPUTFORMAT:從標(biāo)準(zhǔn)輸入（。山恥2比等）讀入數(shù)據(jù)。數(shù)據(jù)有多組，先輸入K（K組數(shù)據(jù)）。每組第一行有兩個(gè)正整數(shù)N和T，表示題目的總數(shù)以及競賽的時(shí)限（單位秒）。以下的N行，每行4個(gè)正整數(shù)W1i、T1i、W2i、T2i，分別表示第i題：完全正確做出來的得分，完全正確做出來所花費(fèi)的時(shí)間（單位：秒），“騙”來的分?jǐn)?shù)，“騙”分所花費(fèi)的時(shí)間（單位秒）。其中，3WNW30，2WTW1080000，1WW1i、W2iW30000，1WT1i、T2iWT。OUTPUTFORMAT:直接把所求得的最高得分輸出。數(shù)據(jù)之間需換行。SAMPLEINPUT:2410800183600318002240001230002860000300032800024600037200505400109005072001090050540010900SAMPLEOUTPUT:5070下面我們對問題進(jìn)行簡化。我們只要考慮是做題還是不做題。從標(biāo)準(zhǔn)輸入1畝趾2比等）讀入數(shù)據(jù)。數(shù)據(jù)只有一組，先輸入K（K組數(shù)據(jù)）。每組第一行有兩個(gè)正整數(shù)N和T，表示題目的總數(shù)以及競賽的時(shí)限（單位秒）。以下的N行，每行2個(gè)正整數(shù)Wi、Ti，分別表示第i題：做出來的得分和做出來所花費(fèi)的時(shí)間（單位:秒），OUTPUTFORMAT:直接把所求得的最高得分輸出。數(shù)據(jù)之間需換行。SAMPLEINPUT:510120510415320210SAMPLEOUTPUT:65下面是用全排列生成器完成的代碼#include<iostream>usingnamespacestd;intm;intt[20][2];inttSum;voidwork(boola[],intn);voidf(boola[],intk,intn){if(k<n){a[k]=true;f(a,k+1,n);a[k]=false;f(a,k+1,n);}else{work(a,n);}}voidwork(boola[],intn){intx;inttime=0,score=0;for(x=0;x<n;x++){if(a[x]){score+=t[x][1];time+=t[x][0];}}if(time<=tSum){if(score>m){m=score;}}}intmain(void){boola[30];intn,c;cin>>n>>tSum;m=0;for(c=0;c<n;c++){cin>>t[c][0];cin>>t[c][1];}f(a,0,n);cout<<m<<endl;return0;}通過一個(gè)排列生成器將所有的可能送入work()函數(shù)內(nèi)，然后work函數(shù)找到在時(shí)間范圍內(nèi)的最高的分?jǐn)?shù)?，F(xiàn)在我們將其優(yōu)化，將work()和f()合并，就能得到更好的程序#include<iostream>usingnamespacestd;{dfs(k+1,n,cScore,cTime);dfs(k+1,n,cScore+t[k][1],cTimeintm;intt[20][2];inttSum;voiddfs(intk,