NOIP復(fù)賽試題類(lèi)型歸納課件

1、數(shù)學(xué)類(lèi)問(wèn)題精度處理（高精度、實(shí)數(shù)處理、REAL類(lèi)型處理方法）組合數(shù)學(xué)問(wèn)題（Fibonacci數(shù)列、類(lèi)數(shù)、卡特蘭數(shù)、POLYA原理、排列組合計(jì)數(shù)、加法原理與乘法原理）進(jìn)制問(wèn)題（特定二進(jìn)制串的統(tǒng)計(jì)、二分查找、利用二進(jìn)制進(jìn)行路徑、狀態(tài)描述、二進(jìn)制轉(zhuǎn)換）數(shù)學(xué)類(lèi)問(wèn)題遞推與遞歸關(guān)系（遞推關(guān)系式、通項(xiàng)公式、數(shù)列、博弈問(wèn)題）數(shù)位、數(shù)字、特定數(shù)值的查找、統(tǒng)計(jì)（數(shù)值處理、質(zhì)因子分解、冪次分解、數(shù)值表達(dá)式、添加運(yùn)算符、分式與實(shí)數(shù)運(yùn)算）數(shù)學(xué)雜題（回文數(shù)字、矩陣處理、約瑟夫與反約瑟夫問(wèn)題）數(shù)學(xué)剪枝（無(wú)解判定、解線性方程組、限定搜索范圍）數(shù)學(xué)類(lèi)問(wèn)題的思維過(guò)程相關(guān)公式、定理、原理的應(yīng)用尋找規(guī)律、歸納整理遞歸與遞推關(guān)系式按照

2、數(shù)學(xué)方法構(gòu)造、二進(jìn)制轉(zhuǎn)化等技巧性處理注意事項(xiàng)：規(guī)律準(zhǔn)確（小數(shù)據(jù)手工推算、搜索程序驗(yàn)證）數(shù)據(jù)類(lèi)型是否合理、數(shù)據(jù)范圍是否超界（大數(shù)據(jù)處理）Kathy函數(shù)(function.exe) Tiger非常喜歡數(shù)學(xué)，所以他參加了學(xué)校組織的數(shù)學(xué)課外興趣小組。在興趣小組的學(xué)習(xí)當(dāng)中，老師向Tiger介紹了Kathy函數(shù)，Kathy函數(shù)是這樣定義的：Tiger對(duì)Kathy函數(shù)產(chǎn)生了濃厚的興趣，他通過(guò)研究發(fā)現(xiàn)有很多的數(shù)n都滿足。對(duì)于一個(gè)給定的數(shù)m，他希望你求出所有的滿足的自然數(shù)n的個(gè)數(shù)，其中。輸入輸出要求輸入由文件”function.in”讀入，僅有一行，為正整數(shù)m，。輸出到文件”function.out”，輸出文件

3、僅有一個(gè)正整數(shù)，表示所有的滿足的自然數(shù)的個(gè)數(shù)。輸入輸出樣例Function.inFunction.out53字符、字串處理類(lèi)問(wèn)題讀入、分離和統(tǒng)計(jì)問(wèn)題（文件結(jié)束符、行結(jié)束符、空格符、回車(chē)符、字符組合分離、統(tǒng)計(jì)）插入、刪除、修改、替換等相關(guān)編輯問(wèn)題（字符距離、優(yōu)美編輯、初始狀態(tài)與目標(biāo)狀態(tài)的變換、迭代等處理性問(wèn)題）KMP算法及其改正回文串、高精度運(yùn)算及其以字符（串）作為處理對(duì)象的相關(guān)問(wèn)題一般性字符處理動(dòng)態(tài)規(guī)劃方法字符樹(shù)（查找、樹(shù)的前序、中序、后序遍歷）注意事項(xiàng)：讀入時(shí)小心（READ、READLN語(yǔ)句及結(jié)束標(biāo)記）字符串類(lèi)型與字符數(shù)組存貯及其壓縮存取表達(dá)式值的計(jì)算統(tǒng)計(jì)類(lèi)問(wèn)題方案總數(shù)統(tǒng)計(jì)（矩陣、三角形劃分

4、方案統(tǒng)計(jì)、問(wèn)題解集個(gè)數(shù)統(tǒng)計(jì)）特定、離散元素統(tǒng)計(jì)（01統(tǒng)計(jì)等二進(jìn)制統(tǒng)計(jì)問(wèn)題）橫向、縱向規(guī)?；瘑?wèn)題（數(shù)據(jù)范圍、數(shù)據(jù)維數(shù)巨大）離散化問(wèn)題掃描技術(shù)、歸類(lèi)統(tǒng)計(jì)及平面、空間坐標(biāo)體系變換等幾何學(xué)知識(shí)離散化思想線段樹(shù)處理方法降維、剪枝借助于數(shù)學(xué)方法進(jìn)行統(tǒng)計(jì)注意事項(xiàng)：統(tǒng)計(jì)計(jì)數(shù)：避免待統(tǒng)計(jì)元素的遺漏、重復(fù)多次讀文件、邊讀邊處理等大數(shù)據(jù)文件的處理技巧求正整數(shù)N和M之間具有最多真因子的數(shù)。本題中的真因子是這樣定義的：如果RP而且R能整除P，我們就稱(chēng)R是P的真因子，對(duì)于特殊整數(shù)1，我們認(rèn)為1是1的真因子。參數(shù)范圍：1NM999999999；M-N999999；順序查找法：依次統(tǒng)計(jì)規(guī)定范圍內(nèi)的各整數(shù)的真因子個(gè)數(shù)，記錄最優(yōu)

5、解。由于，分解質(zhì)因數(shù)的算法時(shí)間復(fù)雜度為平方根級(jí)的，因此這個(gè)算法的時(shí)間復(fù)雜度為O(m-n)*m0.5)。（二）標(biāo)號(hào)法：枚舉不同的因數(shù)，標(biāo)記它們的倍數(shù)。分段統(tǒng)計(jì)法：將給定區(qū)間分成不重復(fù)且不遺漏的若干個(gè)子區(qū)間，然后按方法二統(tǒng)計(jì)。 由于方法一每次處理單一元素，因此時(shí)間耗費(fèi)高，方法二將所有元素統(tǒng)一處理，因此空間需求大，而方法三則綜合前兩種方法的優(yōu)點(diǎn)，在充分利用空間的情況下，得到較高的時(shí)間效率。 方法三實(shí)質(zhì)就是分解法的應(yīng)用，由此我們將“分解法”定義如下：以一定的算法為原型，將大規(guī)模的問(wèn)題分解成若干個(gè)不遺漏且盡量不重復(fù)的相對(duì)獨(dú)立的子問(wèn)題，使得所有子問(wèn)題解集的全集就是原問(wèn)題的解集。模擬類(lèi)問(wèn)題按題設(shè)描述進(jìn)行直接

6、模擬隊(duì)列模型模擬（銀行事件驅(qū)動(dòng)、公交車(chē)站、牙醫(yī)診所）按時(shí)間（刻）順序模擬狀態(tài)（商船運(yùn)輸）類(lèi)Pascal語(yǔ)言程序（算法）運(yùn)行模擬按條件描述直接模擬注意事件發(fā)生的起止時(shí)間、狀態(tài)的變化按某一指標(biāo)（時(shí)間）排序進(jìn)行預(yù)處理注意事項(xiàng)：準(zhǔn)確理解題意，切忌加入個(gè)人想當(dāng)然思想，嚴(yán)格按題意進(jìn)行模擬一般來(lái)說(shuō)要考慮的因素較多，容易讓人思路糊涂，做題前要有絕對(duì)清晰的思路并逐步修正要考慮的各種因素搜索類(lèi)問(wèn)題枚舉類(lèi)問(wèn)題產(chǎn)生式系統(tǒng)無(wú)任何好的解決辦法或其他方法不能完成的問(wèn)題搜索與其他方法的結(jié)合（與動(dòng)態(tài)規(guī)劃的結(jié)合、與貪心思想的結(jié)合等）確定搜索對(duì)象和搜索策略選取適合的搜索方法（深度、廣度、記憶化搜索）注意與其他方法的結(jié)合（貪心回朔、

7、動(dòng)態(tài)規(guī)劃）減少搜索量（剪枝）注意事項(xiàng)：剪枝條件的正確性（加剪枝條件與不加剪條件的程序結(jié)果對(duì)照）搜索也是解決問(wèn)題的一種方法，有時(shí)搜索程序也可以收到較好的效果，只要有較好的優(yōu)化措施正方形剖分問(wèn)題問(wèn)題描述：將n n 個(gè)小格組成的大正方形分割成若干個(gè)較小的整數(shù)邊長(zhǎng)的正方形，要求分成的小正方形數(shù)目最小。范圍：1n32。編程環(huán)境：FreePascal。可用64MB空間n=7時(shí)的一個(gè)最小數(shù)目的剖分方案，需要9個(gè)小正方形。 分析當(dāng)n為偶數(shù)時(shí)最少需要4個(gè)小正方形：1234n/2n/2n/2n/2當(dāng)n為奇數(shù)時(shí)，很難發(fā)現(xiàn)有什么數(shù)學(xué)規(guī)律。設(shè)fi,j表示一個(gè)ij的矩形最少可以被剖分成多少個(gè)小正方形:n=7時(shí)，求出結(jié)果為

8、10，并不是最優(yōu)值。原因：最優(yōu)方案不一定能被某條直線分割。ijkj-kijki-kn711131719232931其他fn,n1012121414161616相同最優(yōu)值911111313131415相差111113210fn,n僅是一個(gè)可行解，不過(guò)其值與最優(yōu)解十分接近的。目前只能用搜索！優(yōu)化：搜索之前先用上述動(dòng)態(tài)規(guī)劃方程求出一個(gè)較優(yōu)值，限制搜索層次。 最優(yōu)化問(wèn)題圖論中的最優(yōu)化問(wèn)題規(guī)劃問(wèn)題特定指標(biāo)（長(zhǎng)度、次數(shù)等）最（極）值問(wèn)題 動(dòng)態(tài)規(guī)劃圖論中經(jīng)典算法及其改正貪心+搜索解決辦法貪心思想數(shù)學(xué)方法圖論問(wèn)題最小生成樹(shù)問(wèn)題路徑問(wèn)題（最短路、關(guān)鍵路徑、道路、回路（ERLUR回路、哈密頓回路）拓?fù)渑判騿?wèn)題（頂點(diǎn)的度）連通性問(wèn)題（添加、刪除邊、點(diǎn)增加或減少