圣才學(xué)習(xí)網(wǎng)為大家匯總了信息學(xué)奧賽（NOIP）復(fù)賽學(xué)習(xí)方法，歡迎大家點(diǎn)擊查看！

  一、確定你的語(yǔ)言

  NOIP包括三種語(yǔ)言c/c＋＋/pascal，在最初必須確定自己使用的語(yǔ)言。沒(méi)有c/c＋＋基礎(chǔ)的，個(gè)人建議使用pascal，因?yàn)樗菀咨鲜郑绻谐湓５臅r(shí)間，則建議c/c＋＋，因?yàn)樗鼈儗?duì)你今后的程序編寫，更有益處。

  二、從排序入手

  排序是基礎(chǔ)中的基礎(chǔ)，快速排序是必備本領(lǐng)，方法就是背下來(lái)。c/c＋＋是自帶快排的，因此很輕松。多關(guān)鍵字排序和穩(wěn)定排序也是必須掌握的排序知識(shí)。

  三、貪心和窮舉以及模擬——最簡(jiǎn)單的程序

  想得獎(jiǎng)，必須掌握貪心和窮舉以及模擬，雖然不能讓你得滿分，但可以給你拿到30-60分。它們是你想不出更好算法時(shí)的救命稻草。

  貪心算法（又稱貪婪算法）是指，在對(duì)問(wèn)題求解時(shí)，總是做出在當(dāng)前看來(lái)是的選擇。也就是說(shuō)，不從整體上加以考慮，他所做出的是在某種意義上的局部解。但是貪心是可以得分的。

  枚舉算法是指，列舉出所有可能的取值，從中找出解。

  模擬算法是指，通過(guò)逐步進(jìn)行操作、逐步判斷來(lái)推斷是否符合題目中所給出的情況。非常耗時(shí)，一般不可能得到解，但是可以得到部分分?jǐn)?shù)。

  四、用動(dòng)態(tài)規(guī)劃來(lái)訓(xùn)練思維

  比較難，對(duì)思維的周密程度和邏輯要求非常高。可以用來(lái)訓(xùn)練思維，對(duì)于學(xué)習(xí)時(shí)間短的筒子，動(dòng)態(tài)規(guī)劃可以幫助你迅速進(jìn)入編程狀態(tài)，也有助于幫你發(fā)現(xiàn)題目背后可能隱藏的更簡(jiǎn)便的算法。

  動(dòng)態(tài)規(guī)劃主要的思考規(guī)律應(yīng)該如下：

  定義函數(shù)（動(dòng)態(tài)轉(zhuǎn)移方程中轉(zhuǎn)移量的定義）——>建立方程——>確定初值和邊界

  提醒！考場(chǎng)上想不到動(dòng)態(tài)轉(zhuǎn)移方程，請(qǐng)選擇貪心、枚舉或模擬等方法來(lái)獲得部分分?jǐn)?shù)。動(dòng)態(tài)規(guī)劃最后得出的答案不正確時(shí)，也不要耗費(fèi)大量時(shí)間來(lái)找出錯(cuò)誤，因?yàn)檫@非常難，也非常耗時(shí)間，得不償失。

  五、學(xué)習(xí)簡(jiǎn)單的圖論

  包括：（單源或多源）最短路和（最小）生成樹(shù)。

  最短路中需要學(xué)習(xí)Dijkstra算法和Floyd算法。近年來(lái)圖論題目越來(lái)越難，知識(shí)點(diǎn)越來(lái)越多，所以時(shí)間不夠，請(qǐng)掌握這兩種。

  最小生成樹(shù)需要掌握Prim算法和Kruskal算法。前者適用于稠密圖，后者適用于疏密圖。兩者可以比較學(xué)習(xí)，看到它們的優(yōu)點(diǎn)和不足。

  六、常用的數(shù)據(jù)結(jié)構(gòu)——讓程序更快一點(diǎn)

  最常用到的是堆（優(yōu)先隊(duì)列）、并查集以及樹(shù)狀數(shù)組堆。

  堆：只關(guān)注“直系親屬關(guān)系”，不關(guān)注“旁系”。常配合貪心使用。

  并查集：快速判斷兩個(gè)元素是否有關(guān)聯(lián)，增加其他算法，還可判斷元素間關(guān)系。

  樹(shù)狀數(shù)組堆：平衡查詢和修改的操作復(fù)雜度的一種算法，常用于解決需要查詢和修改的問(wèn)題。

  七、搜索——和枚舉很像

  深度優(yōu)先搜索和廣度優(yōu)先搜索。

  深度優(yōu)先搜索：一條路走到底。

  廣度優(yōu)先搜索：每一步將下一步的可能性放入隊(duì)列中，然后按照隊(duì)列順序來(lái)探測(cè)。

  復(fù)賽中往往會(huì)加入很多復(fù)雜的元素，所以也需要好好掌握。

  八、最后列一下一定要學(xué)習(xí)的數(shù)學(xué)基礎(chǔ)知識(shí)

  快速冪、高精度、篩法選素?cái)?shù)、輾轉(zhuǎn)相除法

  編輯推薦：