清華大學(xué)ACM集訓(xùn)隊(duì)培訓(xùn)資料(內(nèi)部使用).doc_第1頁(yè)
清華大學(xué)ACM集訓(xùn)隊(duì)培訓(xùn)資料(內(nèi)部使用).doc_第2頁(yè)
清華大學(xué)ACM集訓(xùn)隊(duì)培訓(xùn)資料(內(nèi)部使用).doc_第3頁(yè)
清華大學(xué)ACM集訓(xùn)隊(duì)培訓(xùn)資料(內(nèi)部使用).doc_第4頁(yè)
清華大學(xué)ACM集訓(xùn)隊(duì)培訓(xùn)資料(內(nèi)部使用).doc_第5頁(yè)
已閱讀5頁(yè),還剩5頁(yè)未讀, 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說(shuō)明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡(jiǎn)介

清華大學(xué)ACM/icpc集訓(xùn)隊(duì)2007.3.25清華大學(xué)ACM集訓(xùn)隊(duì)培訓(xùn)資料(內(nèi)部使用)一、C+基礎(chǔ)基本知識(shí)所有的C+程序都是有函數(shù)組成的, 函數(shù)又叫做子程序,且每個(gè)C+程序必須包含一個(gè)main函數(shù),編譯器(能夠把源代碼轉(zhuǎn)換成目標(biāo)代碼的程序)把翻譯后的目標(biāo)代碼和一些啟動(dòng)代碼組合起來(lái),生成可執(zhí)行文件,main函數(shù)就是可執(zhí)行文件的入口,所以,每個(gè)C+程序有且只有一個(gè)main函數(shù)。下面我們看一個(gè)最簡(jiǎn)單C+程序。(程序1.1)程序1.1int main()return 0;在這個(gè)程序中,如果缺少任何一個(gè)字符,編譯器就無(wú)法將其翻譯成機(jī)器代碼。此外,C+是對(duì)大小寫敏感的,這就意味著,如果我將mian()函數(shù)拼為Main(),哪么,編譯器在編譯這段程序的時(shí)候就會(huì)出錯(cuò)。編輯源文件能夠提共管理程序開(kāi)發(fā)的所有步驟,包括編輯的程序成為集成開(kāi)發(fā)環(huán)境(integrated development evironments, IDE)。在windows系統(tǒng)下,使用較為廣泛的有Microsoft Visual C+、Dev-Cpp等,在UNIX系統(tǒng)下,有Vim、emacs、eclipes等。這些程序都能提供一個(gè)較好的開(kāi)發(fā)平臺(tái),使我們能夠方便的開(kāi)發(fā)一個(gè)程序,接下我們所要了解的都是標(biāo)準(zhǔn)C+,所有源代碼都在Dev-cpp下編寫,能夠編譯通過(guò)。如果我們修改程序1.1中的main()函數(shù)的名稱,將其改為Main(),那么,IDE就會(huì)給出錯(cuò)誤信息,比如“ Linker error undefined reference to WinMain16”,因?yàn)榫幾g器沒(méi)有找到main函數(shù)。接下來(lái),我們來(lái)看一個(gè)經(jīng)典的C+例子(程序1.2)程序1.2#includeusing namespace std;int main(void)coutHello Wrold!endl;return 0;運(yùn)行結(jié)果Hello World!程序說(shuō)明第一行“#include”,是一句預(yù)處理命令,相當(dāng)于把“iostream”這個(gè)文件的所有內(nèi)容復(fù)制到當(dāng)前位置,替換該行。因?yàn)樵谳敵霾僮髦行枰龊芏嗍拢珻+編譯器就提供了很多已經(jīng)寫好的函數(shù)(成為C+標(biāo)準(zhǔn)庫(kù)),我們做的只是拿來(lái)用就可以了。第二行的“using namespace std;”是使用標(biāo)準(zhǔn)命名空間,因?yàn)槲覀冊(cè)诔绦蛑杏玫搅嗽跇?biāo)準(zhǔn)命名空間里的函數(shù)和對(duì)象。目前可以不了解其具體如何實(shí)現(xiàn),在以后的程序設(shè)計(jì)中可以再對(duì)其進(jìn)行了解。在明函數(shù)中“cout”Hello World!”endl;”是在屏幕上打印“Hello World!eHeH”,“endl”表明打印完這句話之后需要換行。如果我們替換引號(hào)內(nèi)的內(nèi)容,程序的輸出就會(huì)相應(yīng)改變。另外一個(gè)C+程序例子/ ourfunc.cpp - defining your own function#include void simon(int); / function prototype for simon()int main() using namespace std; simon(3); / call the simon() function cout count; simon(count); / call it again cout Done! endl; return 0;void simon(int n) / define the simon() function using namespace std; cout Simon says touch your toes n times. endl; / void functions dont need return statements下面試運(yùn)行情況:Simon says touch your toes 3 times.Pick an integer: 512Simon says touch your toes 512 times.Done!程序中包含了cin語(yǔ)句來(lái)從鍵盤上獲取數(shù)據(jù)。該程序中包含了除main函數(shù)以外的另一個(gè)函數(shù)simon(),他和main函數(shù)定義的格式相同,函數(shù)的統(tǒng)一格式如下:type functionname (argumentlist)statements注意,定義simon()的代碼在main()函數(shù)的后面,C+中不允許將函數(shù)定義在另一個(gè)函數(shù)內(nèi)。每個(gè)函數(shù)的定義都是獨(dú)立的,所有的函數(shù)的創(chuàng)建都是平等的。simon()函數(shù)的函數(shù)頭定義如下:void simon(int n)以void 開(kāi)頭表明simon()沒(méi)有返回值,因此我們不能類是這樣的使用它。simple = simon(3);有返回值的函數(shù)如下/ convert.cpp - converts stone to pounds#include int stonetolb(int); / function prototypeint main() using namespace std; int stone; cout stone; int pounds = stonetolb(stone); cout stone stone = ; cout pounds pounds. endl; return 0;int stonetolb(int sts) return 14 * sts;下面是運(yùn)行情況:Enter the weight in sone: 1414 stone = 196 pounds.程序通過(guò)cin語(yǔ)句給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ù)類型還有:unsigned long、long、unsigned int、unsigned short、short、char、unsigned char、signed char、bool、float、double、long double。對(duì)于數(shù)據(jù)的輸入和輸出有幾道練習(xí)題/showproblem.php?pid=1089至/showproblem.php?pid=1096二、算法基礎(chǔ)1. 什么是算法算法是完成特定任務(wù)的有限指令集。所有的算法必須滿足下面的標(biāo)準(zhǔn):a. 輸入。由外部題共零個(gè)或多個(gè)輸入量。b. 輸出。至少產(chǎn)生一個(gè)輸出量。c. 明確性。每條指令必須清楚,不具模糊性。d. 有限性。如果跟蹤算法的指令,那么對(duì)于所有的情況,算法經(jīng)過(guò)有限步以后終止。e. 有效性。每條指令必須非?;A(chǔ),原則上使用筆和紙就可以實(shí)現(xiàn)例 選擇排序void SelectionSort(Type a, int n)/Sort the arrat a1:n into nondecreasing order.for (int i=1; i=n; i+)int j=1;for (int k=i+1; k=n; k+)if (ak aj)j = k;Type t = ai;ai = aj;aj = 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í)間SelectionSortcosttimesfor (int i=1; i=n; i+)c1int j=1;c2for (int k=i+1; k=n; k+)c3if (ak aj)c4j = k;c5Type t = ai; ai = aj; aj = t;c6那么該算法運(yùn)行的時(shí)間那么,在最壞的條件下,的值應(yīng)該是所以,算法的運(yùn)行時(shí)間為4漸進(jìn)符號(hào)定義: 大O函數(shù),念做是的大”oh”,當(dāng)且僅當(dāng)存在正常數(shù)和,使得對(duì)于所有的,有。例對(duì)于所有有,所以。對(duì)于所有有,所以對(duì)于所有有,所以當(dāng)然對(duì)于所有有,所以定義: 函數(shù),念做是的”omega”,當(dāng)且僅當(dāng)存在正常數(shù)和,使得對(duì)于所有的,有。例對(duì)于所有有,所以。當(dāng)然,但是?,F(xiàn)然無(wú)論是O還是,都不能精確的描述一個(gè)函數(shù)定義: 函數(shù),念做是的”theta”,當(dāng)且僅當(dāng)存在正常數(shù)和,使得對(duì)于所有的,有。例對(duì)于有且,所以記號(hào)要比O和都要精確。排列生成器(n!)void Perm(Type a, int k, int n)if (k=n) /Output permutation.for (int i-1; in; i+) coutai ;else /ak:n has more than one permutation. / Generate these recursively.for (int i=k; i=n; i+)Type t=ak; ak=ai; ai=t;Perm(a, k+1, n);/All permutations of ak+1:nt=ak; ak=ai; ai=t;對(duì)于下面的程序10#includeusing namespace std;void Perm(int a, int k, int n)if (kn-1)int i, t;for (i=k; in; i+)t = ak;ak = ai;ai = t;Perm(a, k+1, n);t = ak;ak = ai;ai = t;elseint i;for (i=0; in; i+)coutait;coutendl;int main(void)int a3 = 1, 2, 3;Perm(a, 0, 3);return 0;該程序的運(yùn)行結(jié)果為123132213231321312那么,該函數(shù)就完成了對(duì)一個(gè)數(shù)組進(jìn)行全排列的操作下面,分析該程序,我用圓圈代表每次函數(shù)的調(diào)用每次函數(shù)的調(diào)用都用序號(hào)表示12853467910k=0k=1k=21. a: 1 2 3 k: 02. a: 1 2 3 k: 13. a: 1 2 3k: 24. a: 1 3 2k: 25. a: 2 1 3k: 16. a: 2 1 3k: 27. a: 2 3 1k: 28. a: 3 2 1k: 19. a: 3 2 1k: 210. a: 3 1 2k: 2排列生成器的另外一個(gè)版本他將輸出給定n個(gè)布爾變量的所有可能的組合void Perm (bool a, int k, int n)if (k = n)/statementelseak = true; Perm(a, k+1, n);ak = false;Perm(a, k+1, n);在上次冬季賽上有這么一道題競(jìng)賽真理 JUNNY在經(jīng)歷了無(wú)數(shù)次學(xué)科競(jìng)賽的失敗以后,得到了一個(gè)真理:做一題就要對(duì)一題!但是要完全正確地做對(duì)一題是要花很多時(shí)間(包括調(diào)試時(shí)間),而競(jìng)賽的時(shí)間有限。所以開(kāi)始做題之前最好先認(rèn)真審題,估計(jì)一下每一題如果要完全正確地做出來(lái)所需要的時(shí)間,然后選擇一些有把握的題目先做。 當(dāng)然,如果做完了預(yù)先選擇的題目之后還有時(shí)間,但是這些時(shí)間又不足以完全解決一道題目,應(yīng)該把其他的題目用貪心之類的算法隨便做做,爭(zhēng)取“騙”一點(diǎn)分?jǐn)?shù)。 根據(jù)每一題解題時(shí)間的估計(jì)值,確定一種做題方案(即哪些題目認(rèn)真做,哪些題目“騙”分,哪些不做),使能在限定的時(shí)間內(nèi)獲得最高的得分。 INPUT FORMAT: 從標(biāo)準(zhǔn)輸入(cin,scanf等)讀入數(shù)據(jù)。數(shù)據(jù)有多組,先輸入K(K組數(shù)據(jù))。每組第一行有兩個(gè)正整數(shù)N和T,表示題目的總數(shù)以及競(jìng)賽的時(shí)限(單位秒)。以下的N行,每行個(gè)正整數(shù)W1i 、T1i 、W2i 、T2i ,分別表示第i題:完全正確做出來(lái)的得分,完全正確做出來(lái)所花費(fèi)的時(shí)間(單位:秒),“騙”來(lái)的分?jǐn)?shù),“騙”分所花費(fèi)的時(shí)間(單位秒)。其中,3 N 30,2 T 1080000,1 W1i 、W2i 30000,1 T1i 、T2i T。 OUTPUT FORMAT: 直接把所求得的最高得分輸出。數(shù)據(jù)之間需換行。 SAMPLE INPUT: 2 4 10800 18 3600 3 1800 22 4000 12 3000 28 6000 0 3000 32 8000 24 6000 3 7200 50 5400 10 900 50 7200 10 900 50 5400 10 900 SAMPLE OUTPUT : 50 70下面我們對(duì)問(wèn)題進(jìn)行簡(jiǎn)化。我們只要考慮是做題還是不做題。從標(biāo)準(zhǔn)輸入(cin,scanf等)讀入數(shù)據(jù)。數(shù)據(jù)只有一組,先輸入K(K組數(shù)據(jù))。每組第一行有兩個(gè)正整數(shù)N和T,表示題目的總數(shù)以及競(jìng)賽的時(shí)限(單位秒)。以下的N行,每行個(gè)正整數(shù)Wi 、Ti,分別表示第i題:做出來(lái)的得分和做出來(lái)所花費(fèi)的時(shí)間(單位:秒),OUTPUT FORMAT: 直接把所求得的最高得分輸出。數(shù)據(jù)之間需換行。 SAMPLE INPUT: 5 101 205 104 153 202 10SAMPLE OUTPUT : 65下面是用全排列生成器完成的代碼#includeusing namespace std;int m;int t202;int tSum;void work(bool a, int n);void f(bool a, int k, int n)if (k n)ak = true;f(a, k+1, n);ak = false;f(a, k+1, n);elsework(a, n);void work(bool a, int n)int x;int time=0, score=0;for (x=0; xn; x+)if (ax)score += tx1;time += tx0;if (time m)m = score;int main(void)bool a30;int n, c;cinntSum;m = 0;for (c=0; ctc0;cintc1;f(a, 0, n);coutmendl;return 0;通過(guò)一個(gè)排列生成器將所有的可能送入work()函數(shù)內(nèi),然后work函數(shù)找到在時(shí)間范圍內(nèi)的最高的分?jǐn)?shù)?,F(xiàn)在我們將其優(yōu)化,將work()和f()合并,就能得到更好的程序#includeusing namespace std;int m;int t202;int tSum;void dfs(int k, int n, int cScore, int c

溫馨提示

  • 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。

最新文檔

評(píng)論

0/150

提交評(píng)論