您當前位置： 首頁>>教務公告

信息學奧賽（NOIP）復賽學習方法推薦

掃碼手機閱讀
用圣才電子書APP或微信掃一掃，在手機上閱讀本文，也可分享給你的朋友。
評論（0）


  圣才學習網為大家匯總了信息學奧賽（NOIP）復賽學習方法，歡迎大家點擊查看！

 

  一、確定你的語言

 

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

 

  二、從排序入手

 

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

 

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

 

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

 

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

 

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

 

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

 

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

 

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

 

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

 

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

 

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

 

  五、學習簡單的圖論

 

  包括：（單源或多源）最短路和（最?。┥蓸?。

 

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

 

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

 

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

 

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

 

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

 

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

 

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

 

  七、搜索——和枚舉很像

 

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

 

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

 

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

 

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

 

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

 

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

 

  編輯推薦：


學科競賽類電子書（題庫）

查看全部>>

小編工資已與此賞掛鉤！一賞一分錢！求打賞↓ ↓ ↓

如果你喜歡本文章，請賜賞：

已賜賞的人
最新評論（共0條）評論一句