noip複賽應該如何準備？

01-02

聲明：本答案回答對象為初學者（即編程或競賽經驗不豐富、對於演算法和數據結構還沒有體會和深入學習的）。

聲明2：答題者學習OI不超過2年（從大約2012年2月開始學習，此後我高中生涯中的兩次NOIP都參加並獲獎），因此對想要短時間內獲獎的人較為有用，對於長時間學習OI的人來說或許沒有太大幫助。

聲明3：我寫的並不是自學指南，如果有條件有能力，請務必找此方面的專家老師來進行教學，我所能說的只是淺薄的理解。身邊也有曾經的同學自學OI，雖然花了很多精力但是事倍功半，有老師指點是更好的方法。

1.確定你的語言

NOIP接受Pascal、C、C++三種語言的參賽者，在學習的開始，務必確定自己使用的語言。

在中途變更自己學習的語言，對學習NOIP來說是非常大的困難。若是初學者，對C、C++沒有基礎，我個人建議學習Pascal。Pascal可讀性高，對於初學者來說，比起C和C++，Pascal應該是更容易上手的。如果有較長時間的準備，不妨試試看學C或者C++，在以後的大學學習中也會有幫助，而且需要網上搜索題解時，C和C++的題解往往較多，更加方便閱讀參考。

（本人使用Pascal語言，所以後文回答可能涉及到具體程序的大多是Pascal思維。）

2.從排序入手

排序是信息競賽基礎中的基礎，值得我划出整整一塊來為排序進行說明。

快速排序是必備本領，在信息競賽中，若是不會快排，其他的知識就是空中閣樓，學習其他各種優化方法，排序卻丟了時間，是萬萬不可的。學習快排最簡單的方法是背。而C和C++應當是自帶快排的，所以快速排序很是輕鬆。

而個人認為，快速排序以外，必須掌握的排序知識還有多關鍵字排序以及穩定的O(nlogn)排序。

多關鍵字排序來說，我個人是引入比較函數，在確定兩個數字順序時不單純比大小，而使用函數處理判斷先後。

而穩定排序，我學習了歸併排序。它不僅是一個穩定排序，而且可以進行求逆序對等操作，對程序學習的幫助也非常大。

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

想要快速獲獎，必須熟練掌握貪心和窮舉以及模擬。它們雖然不能幫你得到滿分，但是可以幫助你從得不到分變為得到30分甚至60分，或者說，它是你想不出更好演算法時的救命稻草。

所謂貪心，就是通過局部最優來達成整體最優。每一步都獲得當前能取得的最優值，最終也能獲得最優值。雖然看似是非常正確的思路，但由於貪心演算法所能夠考慮因素往往具有局限性，得出的答案常常不會是最優解。但是，仍然需要強調的是，貪心在NOIP這一類比賽中，是能夠得分的。

所謂窮舉，就是列出所有可能的情況，然後從中尋找最優解。雖然看上去是非常簡單的操作方法，但是實際應用時，通過窮舉和剪枝（程序運行到一定程度由於能判斷必定不是最優解而不再繼續），可以達到意想不到的效果。

所謂模擬，常應用於給定步驟時。我們通過逐步進行操作、逐步判斷來推斷是否符合題目中所給出的情況。這種方法常常是非常耗費時間的，所以一般都不可能是最優解。但是，仍然是可以得到部分分數的一種簡單而粗暴的方法。

4.用動態規劃來訓練思維

動態規劃，我偶然跟母親說到這個的時候，母親想起了大學時的課程，然後一臉苦笑的樣子現在都令我印象深刻（笑）。

動態規劃是非常難的一個部分，雖然解題上有一定的規律，但是對於思維的周密程度和邏輯要求非常高。所以我會建議先通過動態規劃來訓練自己的思維。特別是在短時間內的學習的話，動態規劃可以幫助你快速進入編程狀態。並且，動態規劃的思考也可能幫你發現題目背後可能隱藏的更簡便的演算法。

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

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

由於沒有具體的題目，我也不能詳細說明動態規劃。動態規劃千變萬化，題目類型多種多樣，動態規劃的種類也多種多樣，難以一一贅述了。

需要提醒的是，在NOIP的考場上，千萬不要因為想不到動態轉移方程而放棄一道題目，嘗試使用貪心等看似並不完全正確的做法來做，能夠得到部分分數；也不要在動態規劃寫出後發現答案不正確後耗費太多的時間，經驗表明要找出動態規劃的錯誤點可能可以浪費你整場考試的時間。

5.學習簡單的圖論

我認為簡單圖論中包括的有：（單源或多源）最短路和（最小）生成樹。

最短路中需要學習的有Dijkstra演算法和Floyd演算法。Dijkstra演算法有點像圖論中的動態規劃，而Floyd則是圖論中的窮舉法。但是由於近年來圖論的題目越來越困難，加入的其他知識越來越多，沒有長時間準備的話，這兩種演算法掌握即可。如果想再深入一點的話，可以學習SPFA，SPFA也是非常實用的一種演算法。

最小生成樹就不得不提Prim演算法和Kruskal演算法。最小生成樹的演算法中，這兩種某種意義上都可以算是貪心的演算法。Prim演算法更適用於稠密圖，而Kruskal演算法更適用於稀疏圖。如果要學習最小生成樹的話，兩者都學習並且對比是一種很好的方法，能夠看到兩種演算法的優點和不足。

6.常用的數據結構——讓程序更快一點

數據結構中想說的NOIP常常能夠用到的是：堆（優先隊列）、並查集。更加深入學習還可以提到樹狀數組

堆，這種數據結構只關注「直系親屬」之間的關係，而不關注「旁系」。常常能夠配合貪心使用。例如NOIP的經典題合併果子，雖然能夠想出是貪心，但是如果不明白堆的話，程序也不能夠得到滿分。

並查集，能夠快速判斷兩個元素是否有關聯，增加了其他手法之後還能夠判斷元素之間關係。比如說上面提到的Kruskal，一種非常常見的寫法中就運用到了並查集來判斷兩個點是否已經被連接。

樹狀數組，能夠查詢和修改操作複雜度比較平衡的一種演算法，正因如此常用來解決同時需要查詢和修改的問題。

7.不知道該放在哪裡說的搜索——和枚舉很像

老師每次被要求講解搜索都會非常無奈，因為每次講解完搜索，同學們都會以一種「啊，原來是這樣」的眼神看著他，而幾個月後還會再重複這樣的場景（笑）。

搜索大題來說分為深度優先搜索和廣度優先搜索。深度優先搜索就是一條路走到死，撞牆了再回頭，而廣度優先搜索則是每一步就將下一步所有的可能性放入隊列中，然後按照隊列順序來探測。

初賽經常會考深度優先遍歷或廣度優先遍歷後是什麼順序，而複賽的搜索題會加入許多複雜的因素，所以也請好好學習一下這一部分。

8.最後的最後，一定要學習的數學基礎知識

簡單列舉一下：

快速冪
高精度
篩法選素數
擴展歐幾里得定理（輾轉相除法）

這些在考前一定要重新再看一遍，因為難度並不大但是NOIP考到的幾率並不小（會隱藏在第一題中）。

寫的有點長了。

以上。

想起了老師的推薦圖書：

《挑戰程序設計競賽（第2版）【世界頂級程序設計高手的經驗總結，ACM-ICPC全球總冠軍巫澤俊主譯】》秋葉拓哉，岩田陽一，北川宜稔　編，巫澤俊，庄俊元，李津羽　譯

可以作為參考。

量變導致質變。只有通過一定數量的科學的練習，能力才能得到提升。

首先要找一個好的Online judge
noip的話，強烈推薦洛谷。根據試煉場裡面的題目一步步學習。對於noip的準備者來說，是個非常棒的
然後買一本劉汝佳的《演算法競賽入門經典》，也是很好的入門書。

自學，可以的。

《騙分導論》。

-----------------------------------------------141005------------------------------------------------------

看到作者點贊，不禁再次對作者表示感謝。看了《導論》，以攪屎棍身份08年第三題的動規題用貪心騙了⑨個點拿獎，才有大學上，沒這個現在指不定在哪兒玩泥巴呢。直至今日，《導論》的第一條和最後一條依然受用。

刷USACO月賽金銀，務必AC每一題，不會就學，題解一片。

準備方法：

首先學c++ P黨請轉c++ 基本語法需要知道

然後學會鄰接表基礎數論線段樹 dfs 爆搜 bfs 貪心簡單的dp 最短路（floyd dij spfa）並查集 kruskal

以及STL里的priorityqueue和sort

有時間就學鏈剖 dinic traep spaly 後綴數組 AC自動機

不需要看書全機上訓練即可

把所有2008年以後的noip題目全做一遍

不會的可以看題解代碼實在太長的可以跳過

OJ我推薦luogu和vijos

其它的方法：考前買冰紅茶，考前暴力膜大神

我那時候如果有知乎就好了。

usaco絕對有用。

會有原題和改編題。

12年省一壓線。

1、確定自己的語言。找一個適合自己的OJ。

2、刷OJ題，刷OJ題，刷OJ題，重要的事情說三遍。三黨盡量從暑假開始準備，高一高二的同學趁著開學初學校還不忙多刷題，別到期中兩邊抓瞎。

3、經典演算法要耐下性子看，多想多問多寫。盡量把經典演算法找到題寫一遍。

4、最後兩個禮拜多練往屆題。水題過100%，中等題盡量做圓滿，難題有思路試著寫寫，沒思路就做觀賞，好好調整心態。

5、考試時一定穩住，能拿的分不要丟。最後記得騙分：）