[地址]http://hi.baidu.com/yali79/blog/item/3d231901230291007aec2c71.html
21世紀(jì)NOIP提高組復(fù)賽考察點(diǎn)詳細(xì)分析
By hpfdf @YALI
引用資料:
NOIP2000~2009原題。
| 題目編號(hào) | 題目名 | 主考察點(diǎn) | 知識(shí)點(diǎn) | 系數(shù) |
| NOIP-2000-A | 進(jìn)制轉(zhuǎn)換 | 數(shù)學(xué) | 初等代數(shù),找規(guī)律 | 0.6 |
| NOIP-2000-B | 乘積最大 | 動(dòng)態(tài)規(guī)劃 | 資源分配DP | 0.7 |
| NOIP-2000-C | 單詞接龍 | 搜索 | DFS,字符串,模擬 | 0.5 |
| NOIP-2000-D | 方格取數(shù) | 動(dòng)態(tài)規(guī)劃 | 多維狀態(tài) | 0.6 |
| NOIP-2001-A | 一元三次方程求解 | 數(shù)學(xué) | 數(shù)學(xué),枚舉,實(shí)數(shù)處理 | 0.5 |
| NOIP-2001-B | 數(shù)的劃分 | 動(dòng)態(tài)規(guī)劃 | 資源分配DP,多維狀態(tài)DP | 0.7 |
| NOIP-2001-C | 統(tǒng)計(jì)單詞個(gè)數(shù) | 動(dòng)態(tài)規(guī)劃 | 資源分配DP,字符串 | 0.3 |
| NOIP-2001-D | Car的旅行路線 | 圖論 | 最短路,實(shí)數(shù)處理 | 0.7 |
| NOIP-2002-A | 均分紙牌 | 貪心 | 貪心,模擬 | 0.8 |
| NOIP-2002-B | 字串變換 | 搜索 | BFS,字符串 | 0.5 |
| NOIP-2002-C | 自由落體 | 數(shù)學(xué) | 數(shù)學(xué),物理,模擬,實(shí)數(shù)處理 | 0.6 |
| NOIP-2002-D | 矩形覆蓋 | 構(gòu)造 | 動(dòng)態(tài)規(guī)劃/貪心/搜索剪枝 | 0.2 |
| NOIP-2003-A | 神經(jīng)網(wǎng)絡(luò) | 圖論 | 拓?fù)渑判?第推 | 0.4 |
| NOIP-2003-B | 偵探推理 | 模擬 | 枚舉,模擬,字符串 | 0.5 |
| NOIP-2003-C | 加分二叉樹 | 動(dòng)態(tài)規(guī)劃 | 樹,區(qū)間DP | 0.4 |
| NOIP-2003-D | 傳染病控制 | 構(gòu)造 | 隨機(jī)貪心/搜索剪枝 | 0.2 |
| NOIP-2004-A | 津津的儲(chǔ)蓄計(jì)劃 | 模擬 | 模擬 | 0.9 |
| NOIP-2004-B | 合并果子 | 貪心 | 最優(yōu)哈夫曼樹,排序 | 0.7 |
| NOIP-2004-C | 合唱隊(duì)形 | 動(dòng)態(tài)規(guī)劃 | 子序列DP | 0.7 |
| NOIP-2004-D | 蟲食算 | 搜索 | 搜索剪枝,模擬 | 0.2 |
| NOIP-2005-A | 誰拿了最多獎(jiǎng)學(xué)金 | 模擬 | 模擬,字符串 | 0.8 |
| NOIP-2005-B | 過河 | 動(dòng)態(tài)規(guī)劃 | 子序列DP,貪心優(yōu)化 | 0.2 |
| NOIP-2005-C | 篝火晚會(huì) | 數(shù)學(xué) | 置換群,貪心 | 0.2 |
| NOIP-2005-D | 等價(jià)表達(dá)式 | 模擬 | 字符串,抽樣檢測(cè),表達(dá)式 | 0.3 |
| NOIP-2006-A | 能量項(xiàng)鏈 | 動(dòng)態(tài)規(guī)劃 | 區(qū)間環(huán)DP | 0.6 |
| NOIP-2006-B | 金明的預(yù)算方案 | 動(dòng)態(tài)規(guī)劃 | 資源分配DP,構(gòu)造 | 0.6 |
| NOIP-2006-C | 作業(yè)調(diào)度方案 | 模擬 | 模擬 | 0.7 |
| NOIP-2006-D | 2^k進(jìn)制數(shù) | 動(dòng)態(tài)規(guī)劃 | 動(dòng)態(tài)規(guī)劃/組合數(shù)學(xué),高精度 | 0.5 |
| NOIP-2007-A | 統(tǒng)計(jì)數(shù)字 | 模擬 | 排序 | 1.0 |
| NOIP-2007-B | 字符串的展開 | 模擬 | 字符串,模擬 | 0.7 |
| NOIP-2007-C | 矩陣取數(shù)游戲 | 動(dòng)態(tài)規(guī)劃 | 區(qū)間DP,高精度 | 0.6 |
| NOIP-2007-D | 樹網(wǎng)的核 | 圖論 | 最短路,樹的直徑 | 0.4 |
| NOIP-2008-A | 笨小猴 | 模擬 | 質(zhì)數(shù)判斷,字符串 | 1.0 |
| NOIP-2008-B | 火柴棒等式 | 模擬 | 枚舉,優(yōu)化/開表 | 0.8 |
| NOIP-2008-C | 傳紙條 | 動(dòng)態(tài)規(guī)劃 | 多維狀態(tài)DP | 0.7 |
| NOIP-2008-D | 雙棧排序 | 構(gòu)造 | 枚舉,貪心/二分圖 | 0.4 |
| NOIP-2009-A | 潛伏者 | 模擬 | 字符串,模擬 | 0.9 |
| NOIP-2009-B | Hankson的趣味題 | 數(shù)學(xué) | 初等數(shù)論,質(zhì)因數(shù),組合數(shù)學(xué) | 0.4 |
| NOIP-2009-C | 最優(yōu)貿(mào)易 | 圖論 | 最短路 | 0.5 |
| NOIP-2009-D | 靶形數(shù)獨(dú) | 搜索 | 搜索優(yōu)化 | 0.3 |
動(dòng)態(tài)規(guī)劃：12
模擬：10
數(shù)學(xué)：5
圖論：4
搜索：4
構(gòu)造：3
貪心：2
【動(dòng)態(tài)規(guī)劃】平均難度系數(shù)：0.55
次項(xiàng)為歷屆NOIP考察次數(shù)最多的知識(shí)點(diǎn)。
主要有 1.區(qū)間模型 2.子序列模型 3.資源分配模型 以及一些簡(jiǎn)單的多維狀態(tài)設(shè)計(jì)技巧。
動(dòng)態(tài)規(guī)劃可以與圖,樹,高精度等知識(shí)點(diǎn)配合出題。
【模擬】平均難度系數(shù)：0.76
平均每屆NOIP都會(huì)出現(xiàn)1個(gè)模擬題。
這種題一般算法很簡(jiǎn)單，需要選手細(xì)心理解題目意思，注意細(xì)節(jié)。考察選手的代碼實(shí)現(xiàn)能力。
【數(shù)學(xué)】平均難度系數(shù)：0.46
需要掌握質(zhì)數(shù)及其性質(zhì)，基礎(chǔ)的實(shí)屬操作，加法原理和乘法原理。此類題需要選手對(duì)數(shù)學(xué)規(guī)律的靈感。
【圖論】平均難度系數(shù)：0.50
歷屆考察點(diǎn)基本上都是1.最短路問題 和 2.特殊圖的性質(zhì) 。特殊圖包括樹，拓?fù)鋱D，二分圖等。
歷屆NOIP在圖論上的考察并不是很多。
【搜索】平均難度系數(shù)：0.38
歷屆搜索題一般都比較難，搜索算法本身簡(jiǎn)單，于是題目會(huì)提高選手對(duì)其他方面的要求。
主要有搜索優(yōu)化和模擬。寫搜索題時(shí)應(yīng)該以盡量多得分為目標(biāo)。
【構(gòu)造】平均難度系數(shù)：0.27
構(gòu)造類題目一般沒有明確的算法，需要選手仔細(xì)分析題目的實(shí)質(zhì)，并得出解法。
這個(gè)解法通常不是唯一的。有時(shí)一個(gè)好的貪心可以得相當(dāng)多的分。有時(shí)搜索剪枝可以很大的提高效率。
同樣以多得分為目標(biāo)。
【貪心】平均難度系數(shù)：0.75
此類題需要選手對(duì)算法的直覺，貪心正確性一旦被證明，通常題目就很簡(jiǎn)單了。
(×)友情提醒：
考場(chǎng)上沒有標(biāo)示每道題屬于什么類型，光分析歷屆類型是沒用的。
想要得高分，還得多做題。