本文轉(zhuǎn)自江蘇信息學(xué)競(jìng)賽
本文作者許昊然畢業(yè)于南京外國(guó)語(yǔ)學(xué)校，曾獲NOIP 2012一等獎(jiǎng)（590分，江蘇第一名）、NOI 2012金牌（485分，全國(guó)第19名）、IOI 2013金牌（世界第三名），高一獲清華保送資格，2014年被美國(guó)麻省理工學(xué)院錄取。
* 首先，如果你的水平已經(jīng)遠(yuǎn)超NOIP，自然是想怎么考怎么考了。
* 同理，如果你什么都不會(huì)，那么策略再好也是沒(méi)用的。
* 因此，下面說(shuō)的策略、技巧主要是針對(duì)水平中等，游走在分?jǐn)?shù)線附近的同學(xué)們的。
賽場(chǎng)策略的最終目標(biāo)就是一句話：多拿分。
這是考試，為了分?jǐn)?shù)應(yīng)當(dāng)使用任何你能想到的手段。(當(dāng)然作弊啥的除外......)
多拿分，具體來(lái)說(shuō)就是兩部分：
* 會(huì)做的subtask不丟分
* 不會(huì)做的subtask多騙分
1、先講一下“會(huì)做的subtask不丟分”。
subtask就是每道題目里各個(gè)部分分。如果一個(gè)subtask你會(huì)做，比如遇到了水題，或者某道題你會(huì)寫(xiě)30分的小數(shù)據(jù)，那么請(qǐng)務(wù)必確保你能拿到這部分分?jǐn)?shù)。
以及，不要嫌分?jǐn)?shù)少而懶得寫(xiě)！30分也是分，10分也是分，在分?jǐn)?shù)拉不開(kāi)的情況下(如果你水平并不優(yōu)秀，這就是你總是要面對(duì)的情況)，10分的差距就決定了你是一等還是二等。
記住，如果你因?yàn)榇中拇笠?，一個(gè)簡(jiǎn)單的subtask沒(méi)拿到分，你就不得不依靠更難的題目來(lái)把這部分分?jǐn)?shù)拉回來(lái)。
舉個(gè)例子，某A，第一題因打錯(cuò)文件名爆零，其余兩題滿分。某B，只會(huì)前兩題，第三題寫(xiě)了樸素得30分。最后A得200分，B得230分。難題和水題都是100分，評(píng)獎(jiǎng)可不管你到底寫(xiě)對(duì)的是難題還是水題。
請(qǐng)大家記?。涸诖蠖鄶?shù)OI比賽中，只要暴力分全部拿到，就是一等獎(jiǎng)(或金牌)。
但問(wèn)題是，大家都會(huì)寫(xiě)暴力，為啥一等獎(jiǎng)只有總名額的10%呢？因?yàn)榇蠖鄶?shù)人都會(huì)把暴力寫(xiě)錯(cuò)，或看暴力分少懶得寫(xiě)。如果你正確寫(xiě)出了所有暴力，不出意外你就是一等獎(jiǎng)了。
2、再講一下騙分的問(wèn)題?？紤]到這里可能有新初一的學(xué)生，介紹一下：
所謂騙分，就是用錯(cuò)誤的算法拿到分?jǐn)?shù)。按照往年NOIP的經(jīng)驗(yàn)看，NOIP的數(shù)據(jù)一般都不強(qiáng)。騙分拿到80分以上甚至滿分的分?jǐn)?shù)很常見(jiàn)。
數(shù)據(jù)是死的，人是活的，出題人是懶的。
數(shù)據(jù)是賽前就出好的，出題人并不知道你可能會(huì)用什么錯(cuò)誤的算法騙分。
騙分算法五花八門(mén)，你的各種錯(cuò)誤的亂搞算法，會(huì)讓出題人很頭疼。
加上出題人一般很懶，再加上NOIP一般每題只有10組數(shù)據(jù)，你的各種亂搞算法往往都是有收獲的。如果你能想出一個(gè)出題人很可能沒(méi)想到的亂搞算法，那你的收獲往往就更大了。
常見(jiàn)有效騙分算法試舉例：
* 若干個(gè)錯(cuò)誤的貪心、動(dòng)態(tài)規(guī)劃取最優(yōu)解——一個(gè)數(shù)據(jù)同時(shí)卡掉多個(gè)錯(cuò)誤算法很難；
* 暴力算法加奇怪剪枝——出題人不一定想得到你的奇怪剪枝，因此不一定卡的掉；
* 基于某些東西的暴力(比如樹(shù)上的題目和深度有關(guān)、和點(diǎn)的度數(shù)有關(guān)的暴力等)——原因同上；
* 代碼的常數(shù)優(yōu)化——配合上述優(yōu)化，進(jìn)一步增加卡過(guò)去的可能性。
3、下面我們?cè)僬f(shuō)一些技巧性的策略。
我下面說(shuō)的只是我個(gè)人比較喜歡的策略，但這些策略很可能因人而異，因此請(qǐng)同學(xué)們不要照搬，找到或發(fā)現(xiàn)適合自己的策略。
首先做題策略應(yīng)該是先做最簡(jiǎn)單的題目，先拿能確保拿到的分?jǐn)?shù)。
因此，拿到題目后建議先花半個(gè)小時(shí)左右的時(shí)間，把所有題目都看懂，每道題都仔細(xì)想一想。原因有兩個(gè)，一是題目不一定是按照難易程度排列的，都看一遍更容易找到最簡(jiǎn)單的題。二是，在還沒(méi)有寫(xiě)代碼，頭腦比較清醒的時(shí)候進(jìn)行思考更容易想出算法。
如果你發(fā)現(xiàn)三道題都會(huì)做，而且確定沒(méi)有看錯(cuò)題，那么你這場(chǎng)考試基本已經(jīng)塵埃落定了。
當(dāng)然更常見(jiàn)的情況是，想出了一題或兩題的大概做法，還有一題或兩題不太會(huì)做。本著“先拿確保能拿到的分?jǐn)?shù)”的原則，建議先把會(huì)寫(xiě)的分?jǐn)?shù)都寫(xiě)出來(lái)。不會(huì)的題目的暴力也都應(yīng)當(dāng)寫(xiě)一下，因?yàn)槿绻阕詈鬀](méi)做出來(lái)，那暴力可以交上去拿樸素分；如果你最后做出來(lái)了，也需要暴力來(lái)對(duì)拍。同時(shí)暴力也能為正解提供一些思路。
接下來(lái)，你的任務(wù)就是想出你還不會(huì)做的題目了。以下是一些可能有用的方法/技巧：
* 使用草稿紙，有用的性質(zhì)都可以記錄下來(lái)，零散的思路也可以畫(huà)下來(lái)，這很有助于思考。
* 嘗試加強(qiáng)/放寬題目的條件/約束，得到更特殊的模型。思考特殊模型的解法并嘗試推廣到原問(wèn)題。
* 探索是否存在隱藏的性質(zhì)，嘗試從邊界、特殊情況開(kāi)始考慮，猜測(cè)、證明性質(zhì)。
* 是否能換一個(gè)思路？從反面思考是否更簡(jiǎn)單？是否可以利用二分答案之類(lèi)的技巧進(jìn)行轉(zhuǎn)化？NOIP的題目對(duì)思維深度的要求一般不高，如果想了很久都沒(méi)想法，可能是你思維方向錯(cuò)了。
* 某某算法是否可能應(yīng)用于這個(gè)問(wèn)題？逐一確定。(如果你有思維死角，比如總是想不到用某個(gè)算法，可以考慮這樣)
還有一些我覺(jué)得很有效的技巧：
如果想一道題想了很久(比如20分鐘)都沒(méi)有想法，建議去上個(gè)廁所放松一下。如果發(fā)現(xiàn)了一個(gè)可能有用的性質(zhì)，建議去上個(gè)廁所放松一下。如果想出了某題的算法，建議去上個(gè)廁所放松一下。如果寫(xiě)完了某題的暴力，建議去上個(gè)廁所放松一下。如果寫(xiě)完了某題的正解，要開(kāi)始對(duì)拍了，建議去上個(gè)廁所放松一下。如果對(duì)拍掛了/通過(guò)了對(duì)拍，建議去上個(gè)廁所放松一下。
如果去廁所不方便，或者覺(jué)得太浪費(fèi)時(shí)間，也可以用在座位上伸懶腰、深呼吸什么的代替。目的只有一個(gè)：不要讓自己長(zhǎng)時(shí)間陷入某項(xiàng)工作(思考、調(diào)試)中。
原因一是人在長(zhǎng)時(shí)間思考或調(diào)試時(shí)會(huì)效率下降，而且容易“鉆牛角尖”，陷入錯(cuò)誤的思路中；二是時(shí)間也會(huì)不知不覺(jué)中過(guò)的特別快，容易出現(xiàn)類(lèi)似“臥槽考試只剩一個(gè)半小時(shí)了還一點(diǎn)想法沒(méi)有怎么辦”這種很糟糕的情況。
因此，如果你想了一段時(shí)間卻毫無(wú)想法/調(diào)試了很久找不到問(wèn)題所在，請(qǐng)務(wù)必從中跳出來(lái)，換一個(gè)思路，切勿陷入其中，白白浪費(fèi)時(shí)間。
總結(jié)一下:
會(huì)做的題不要寫(xiě)錯(cuò)!
不會(huì)做的題，要寫(xiě)暴力!要騙分!
不要鉆牛角尖，高效利用時(shí)間!
無(wú)論發(fā)生什么，保持心態(tài)穩(wěn)定!
1、關(guān)于NOI Linux
聽(tīng)說(shuō)NOIP也統(tǒng)一采用NOI Linux系統(tǒng)了?？紤]到這里大部分同學(xué)應(yīng)該沒(méi)用過(guò)這玩意，以下是一些注意點(diǎn)：
* NOI Linux似乎安裝比較麻煩，如果想自己熟悉環(huán)境但不會(huì)裝，用虛擬機(jī)裝Ubuntu也可以，界面什么都一樣的。
* 據(jù)說(shuō)考場(chǎng)是windows下裝NOI Linux虛擬機(jī)，能適應(yīng)NOI Linux環(huán)境最好，但如果不習(xí)慣想直接在windows下編碼，請(qǐng)務(wù)必記得提前測(cè)試能否在實(shí)體機(jī)和虛擬機(jī)之間拷貝文件!否則寫(xiě)完程序發(fā)現(xiàn)拷不進(jìn)虛擬機(jī)交不上去就真麻煩大了。
* Linux下64位整數(shù)輸出是%lld而不是%I64d，不要弄錯(cuò)了。
2、OI中犯低級(jí)錯(cuò)誤丟分是很悲劇的，也是很不應(yīng)該的。
下面是一些常見(jiàn)的低級(jí)錯(cuò)誤，望大家避免:
* 文件名打錯(cuò)/忘記用文件輸入/忘記用文件輸出/忘記關(guān)文件；
* 數(shù)組開(kāi)小；
* 爆了內(nèi)存限制；
* 運(yùn)算時(shí)爆int，忘記強(qiáng)制轉(zhuǎn)換為long long；
* 對(duì)答案取模的題目有地方忘記取模；
* 輸出時(shí)格式錯(cuò)誤；
* 輸出64位整數(shù)時(shí)沒(méi)有用%lld；
* 提交時(shí)交錯(cuò)文件/打錯(cuò)擴(kuò)展名；
* 等等等等......
NOIP近年難度變化較大，也沒(méi)有考綱啥的。我只能大概給一個(gè)列表。
* 模擬、枚舉、爆搜、高精度計(jì)算等較基礎(chǔ)內(nèi)容；
* 貪心、構(gòu)造、結(jié)論題等比較坑的；
* 動(dòng)態(tài)規(guī)劃及其優(yōu)化(以前出過(guò)單調(diào)隊(duì)列，但會(huì)不會(huì)出現(xiàn)更難的就不知道了)；
* 基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)(部分和、簡(jiǎn)單的線段樹(shù)等常見(jiàn)的維護(hù)方法)；
* 樹(shù)論，樹(shù)形dp，樹(shù)上的數(shù)據(jù)結(jié)構(gòu)(lca，倍增祖先，dfs序等)；
* 圖論，最短路，最小生成樹(shù)等；
* 簡(jiǎn)單數(shù)論(逆元、快速冪、素?cái)?shù)篩法、中國(guó)剩余定理等)；
* 常見(jiàn)轉(zhuǎn)化方法(二分答案、分治等)、常見(jiàn)技巧(壓位等)、推理分析的能力。
聯(lián)系客服
