南開2008暑假集訓(xùn)1簡(jiǎn)單知識(shí)

1、部分名詞的簡(jiǎn)單解釋目錄 TOC o 1-3 h z u HYPERLINK l _Toc205341392 部分名詞的簡(jiǎn)單解釋 PAGEREF _Toc205341392 h 1 HYPERLINK l _Toc205341393 OJ PAGEREF _Toc205341393 h 1 HYPERLINK l _Toc205341394 Multi-cases PAGEREF _Toc205341394 h 1 HYPERLINK l _Toc205341395 Multi-cases (Detailed Mode) PAGEREF _Toc205341395 h 1 HYPERLINK l

2、 _Toc205341396 Special Judge PAGEREF _Toc205341396 h 2 HYPERLINK l _Toc205341397 STL PAGEREF _Toc205341397 h 2 HYPERLINK l _Toc205341398 復(fù)雜度 PAGEREF _Toc205341398 h 2 HYPERLINK l _Toc205341399 關(guān)于C語言的輸入輸出 PAGEREF _Toc205341399 h 2 HYPERLINK l _Toc205341400 處理多組數(shù)據(jù) PAGEREF _Toc205341400 h 2 HYPERLINK l

3、 _Toc205341401 DP PAGEREF _Toc205341401 h 3 HYPERLINK l _Toc205341402 貪心算法 PAGEREF _Toc205341402 h 3 HYPERLINK l _Toc205341403 最優(yōu)解 PAGEREF _Toc205341403 h 3 HYPERLINK l _Toc205341404 枚舉 PAGEREF _Toc205341404 h 3 HYPERLINK l _Toc205341405 搜索 PAGEREF _Toc205341405 h 3 HYPERLINK l _Toc205341406 數(shù)據(jù)結(jié)構(gòu) PA

4、GEREF _Toc205341406 h 3 HYPERLINK l _Toc205341407 數(shù)據(jù)規(guī)模 PAGEREF _Toc205341407 h 3 HYPERLINK l _Toc205341408 高精度計(jì)算 PAGEREF _Toc205341408 h 4OJ即Online Judge，在線評(píng)測(cè)系統(tǒng)。Multi-cases即輸入數(shù)據(jù)分別存在幾個(gè)文件之中。Multi-cases (Detailed Mode)即輸入數(shù)據(jù)分別存在幾個(gè)文件之中，且會(huì)顯示出正確、錯(cuò)誤及格式錯(cuò)誤的數(shù)量。Special Judge某些題目會(huì)出現(xiàn)多解，這些題目往往使用Special Judge。Speci

5、al Judge會(huì)根據(jù)輸入數(shù)據(jù)和你的輸出數(shù)據(jù)自動(dòng)判斷你的程序是否正確。STL即Standard Template Library，標(biāo)準(zhǔn)模板庫，其中提供了大量函數(shù)和容器模板，方便了程序的設(shè)計(jì)。常用的有函數(shù)模板sort、lower_bound，容器模板vector、set等等。關(guān)于STL，可參考 HYPERLINK /acm/data/download/CppReference.chm C+函數(shù)庫電子手冊(cè) 及 HYPERLINK /acm/data/download/STL_Programmer_Guide.chm STL_Programmer_Guide 。復(fù)雜度算法分析中用來衡量程序優(yōu)劣的量度

6、。一般包括時(shí)間復(fù)雜度和空間復(fù)雜度，分別對(duì)程序的運(yùn)行時(shí)間和占用內(nèi)存提供參考。關(guān)于C語言的輸入輸出對(duì)于某些數(shù)據(jù)量較大的題目，使用C語言的輸入輸出方式可以明顯的減少運(yùn)行時(shí)間。C語言的輸入輸出方式有：scanf 格式 scanf(“%d”, &n); 第一個(gè)參數(shù)是一個(gè)字符串，表示輸入數(shù)據(jù)的格式，每一個(gè)格式對(duì)應(yīng)一個(gè)數(shù)值，存入之后對(duì)應(yīng)的地址之中，之后的參數(shù)表示輸入數(shù)據(jù)保存的地址。本例等價(jià)于C+語言的 cin n; 。scanf的返回值為int型，表示正確輸入數(shù)據(jù)的個(gè)數(shù)。printf 格式 printf(“%d”, n); 第一個(gè)參數(shù)是一個(gè)字符串，表示輸出數(shù)據(jù)的格式，每一個(gè)格式對(duì)應(yīng)一個(gè)數(shù)值，輸出之后對(duì)應(yīng)的變量（或常量），之后的參數(shù)表示輸出數(shù)據(jù)。本例等價(jià)于C+語言的 cout ab)while(gets(ch)DPDynamic Programming，即動(dòng)態(tài)規(guī)劃。動(dòng)態(tài)規(guī)劃利用問題的性質(zhì)減少程序中的重復(fù)計(jì)算，提高程序的運(yùn)行效率。貪心算法即只考慮當(dāng)前最優(yōu)結(jié)果的算法。例如在一些數(shù)中取若干使之和最大，可每次取出當(dāng)前數(shù)中最大的。最優(yōu)解即題目要求的最好的結(jié)果。表述一般為求某一量的最大值、最小值等等。枚舉將所有的情況列舉一遍的算法。一般是針對(duì)數(shù)據(jù)量小的題目的算法。搜索在所有狀態(tài)中尋找可行解的算法。一般情況下為指數(shù)級(jí)的時(shí)間復(fù)雜度。數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)是存儲(chǔ)和組織數(shù)據(jù)的一種形式，以便于對(duì)數(shù)據(jù)進(jìn)行訪問和修改。基本