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