一、確定你的語言

NOIP包括三種語言c/c++/pascal，在最初必須確定自己使用的語言。沒有c/c++基礎的，個人建議使用pascal，因為它更容易上手，如果有充裕的時間，則建議c/c++，因為它們對你今後的程序編寫，更有益處。

二、從排序入手

排序是基礎中的基礎，快速排序是必備本領，方法就是背下來。c/c++是自帶快排的，因此很輕鬆。多關鍵字排序和穩定排序也是必須掌握的排序知識。

三、貪心和窮舉以及模擬——最簡單的程序

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

貪心演算法（又稱貪婪演算法）是指，在對問題求解時，總是做出在當前看來是最好的選擇。也就是說，不從整體最優上加以考慮，他所做出的是在某種意義上的局部最優解。但是貪心是可以得分的。

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

模擬演算法是指，通過逐步進行操作、逐步判斷來推斷是否符合題目中所給出的情況。非常耗時，一般不可能得到最優解，但是可以得到部分分數。

四、用動態規劃來訓練思維

比較難，對思維的周密程度和邏輯要求非常高。可以用來訓練思維，對於學習時間短的筒子，動態規劃可以幫助你迅速進入編程狀態，也有助於幫你發現題目背後可能隱藏的更簡便的演算法。

動態規劃主要的思考規律應該如下：

定義函數（動態轉移方程中轉移量的定義）——>建立方程——>確定初值和邊界

提醒！考場上想不到動態轉移方程，請選擇貪心、枚舉或模擬等方法來獲得部分分數。動態規劃最後得出的答案不正確時，也不要耗費大量時間來找出錯誤，因為這非常難，也非常耗時間，得不償失。

五、學習簡單的圖論

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

最短路中需要學習Dijkstra演算法和Floyd演算法。近年來圖論題目越來越難，知識點越來越多，所以時間不夠，請掌握這兩種。

最小生成樹需要掌握Prim演算法和Kruskal演算法。前者適用於稠密圖，後者適用於疏密圖。兩者可以比較學習，看到它們的優點和不足。

六、常用的數據結構——讓程序更快一點

最常用到的是堆（優先隊列）、並查集以及樹狀數組堆。

堆：只關注「直系親屬關係」，不關注「旁系」。常配合貪心使用。

並查集：快速判斷兩個元素是否有關聯，增加其他演算法，還可判斷元素間關係。

樹狀數組堆：平衡查詢和修改的操作複雜度的一種演算法，常用於解決需要查詢和修改的問題。

七、搜索——和枚舉很像

深度優先搜索和廣度優先搜索。

深度優先搜索：一條路走到底。

廣度優先搜索：每一步將下一步的可能性放入隊列中，然後按照隊列順序來探測。

複賽中往往會加入很多複雜的元素，所以也需要好好掌握。

八、最後列一下一定要學習的數學基礎知識

快速冪、高精度、篩法選素數、輾轉相除法

九、必要的刷題

信息學競賽的題庫在網上隨處可見如TYVJ,RQNOJ，洛谷，大視野測評等，為了方便大家尋找到適合自己的題庫，我們會在今後的推送內容中對當今網路上一些題庫進行專業的分析，幫你找到適合自己的題庫。

推薦閱讀：

相关文章