历年NOIP提高组统计与简析
历年NOIP提高组统计与简析
之后还会有对蓝/绿题的详细总结，所以这里就暂且简析了。统计为主。
RT。
2018
3道树题。不过假如稍微了解基环树方法，旅行是可以拿全分的，更别说大部分分都给了直接DFS了。
气死我的是货币系统这一完全背包模板居然爆零...在考场上一直在想是不是巨凯的疑惑...唉，思路不通的时候真应该缓缓思维，寻找其他算法模型呀。
2017
小凯的疑惑...不说。 奶酪很好拿分，但是时间复杂度拿全分很难。除非把前两题的时间缩短，给够时间慢慢Hack自己咯。（我就是那种偷懒得下载一个数据、改一次、多过一个点，然后再下数据的人qwq）
2016
天天爱跑步...不说。 蚯蚓和愤怒的小鸟的正解设计是比较难想的。换教室的话，正解可能更容易想到一些？？？身边好多人都觉得这样的期望相对容易实现。
2015
斗地主是个用来练习DFS局面设计和搜索框架的好题目。这道题目虽然细节多，但是真正数据好像并没有那么刁钻（比如好多可以在该题AC的方法在增强版是会TLE或者WA的）
2014
飞扬的小鸟是今年DP相对容易想到的了。虽然正解的最后几个点需要的优化比较难，但是直接做也能拿很多分。
解方程里面就是“取模”对数据处理最妙的方法了，也有众所周知的秦九韶算法的加速技巧。
2013
2012
两道倍增也是服了...国王游戏的贪心也属于史诗级...不过同余方程是送分题啦
2011
Mayan游戏和上面的斗地主都是DFS（难）好题。聪明的质检员也是我所见过的二分答案、前缀和运用的最灵活的一次。
2010
今年出了三道经典题呀：引水入城是BFS好题，关押罪犯是（二分图）并查集好题，乌龟棋是多维DP入门题。
2009
Hankson的趣味题一点也不有趣...遇见数学立死系列...靶形数独个人认为出的虽不比之前提到的两道DFS经典，但也是数独问题的扩展吧。
2008
传纸条也是一种多维DP的模型级题目，虽然是以两个线性增长量作为阶段，但也不见得能现场想出来。双栈排序毒瘤。
2007
讨厌高精。我居然想不出树网的核的暴力分做法气死我了；这也是树的直径的相关应用的典型例题之一（不过还是好难啊啊啊啊）。
2006
第一眼看到能量项链题面的时候笑出声来了哈哈哈哈，这明明就是《算法导论》区间DP的例题嘛。过于经典的区间DP，值得一刷。（至少比上面的矩阵取数简单吧）。
2005
过河毒瘤。压缩路径DP也是服了。
2004
2003
神经网络是拓扑排序典例，很不错的一道题目。但是边界处理公认有歧义。 传染病控制让我意识到我的搜索功力还是挺弱的...
2002
矩形覆盖让我意识到我的搜索功力还是挺弱的...讨厌字符串（可能我太弱了）（呸明明就是）
2001
Car的旅行路线很能体现Floyd算法的优越性——忽视边的存在。其中的计算几何知识也是高中平面向量能学到的。
2000
方格取数是后来传纸条的重题来源（双倍经验哈哈哈哈）
1999
略
1998
简单统计：
-
2018年与2017年有3道紫题，以树形结构、倍增、搜索扩展为主。2012年的2道紫题也是考察倍增和树形结构。2016、2015各有1道，内容也如上。2018年的填数游戏、2017年的列队是什么鬼 w(ﾟДﾟ)w。 往前就没有紫题了。
-
黄橙题大概有模拟（其实好多时候不必贪心也能拿全分）、简单的图论（没有太多拓展的DFS、并查集等）、简单的同余应用占少数。
-
绿题以设计较简单的DP为主，简单的同余占少数。有一定处理难度的搜索在早年出现过。
-
蓝题所考的很有可能是我可解范围的天花板了。搜索的拓展和处理以及局面设计很麻烦、DP方程对我基本不可解（我在DP上花的功夫太少了，过于注重题解）、图论也需要一定程度的转化才能成为可接近的题目。
总结：
-
越来越难了。
-
真的假如把黄绿拿到手，再拿到蓝的部分分数，对我就差不多了...
-
当然树形结构和倍增还是需要格外注意的。
-
发现思路的明显不正确性、或者只适用于极小范围（比如本蒟蒻用尽扩欧功力只期望解得n<=3的数据（貌似还写崩了））后，应该让大脑稍微停一下，再想想其他算法模型。
-
DFS是基本功。