NOIp历年真题整理解答
ModestCoder_ · · 个人记录
有时间的话再写几道吧，个人准备联赛的方式就是刷历年题目，主要是熟悉一下思维模式，算法方面
NOIp2012
- 摆花：普通DP，DP水平到一个层次就不用烦恼的题目
- 文化之旅：抛去数据水的槽点，
\text{n<=100} 一个O(n^3)floyd - 国王游戏：贪心套路，简便的数学推导解出最优策略，无耻的高精。。。
- 开车旅行：难题，倍增思想优化dp
- 同余方程：
exgcd 模板 - 借教室：二分
- 疫情控制：较难题，二分+贪心+倍增过程较复杂
NOIp2013
- 积木大赛：纯粹纪念一下（你懂的）
- 车站分级：虽然很卑微，但就是暴力
- 火柴排队：问题转化，逆序对
- 货车运输：最小瓶颈路模板，最小生成树+倍增思想
NOIp2014
- 子矩阵：暴力
dfs +dp - 寻找道路：图论思维，反向图套路，实际上不涉及最短路(用bfs可替换)
- 解方程：数论，秦九昭
- 联合权值：问题转化，距离为2--->某点所有邻居之间
- 飞扬的小鸟：套路dp
NOIp2015
- 推销员：贪心，NOIp数据规模开始变大
- 子串：dp+优化
- 斗地主：记忆化搜索，复杂模拟
- 信息传递：图论
- 运输计划：二分+树上差分
NOIp2016
- 天天爱跑步：难题，桶思想+树上差分，过程复杂
- 换教室：期望dp
- 蚯蚓：单调性
- 愤怒的小鸟：状压dp
NOIp2017
- 跳房子：二分+单调队列优化dp
- 小凯的疑惑：神坑结论题
- 时间复杂度：模拟
- 逛公园：计数dp用记忆化搜索解决
- 奶酪：并查集
- 宝藏：状压dp/退火
- 列队：动态开点线段树/平衡树
NOIp2018
- 摆渡车：dp
- 对称二叉树：暴力
- 铺设道路：NOIp:我贺我自己
- 货币系统：完全背包
- 铺设道路：二分+二分+贪心
- 旅行：图论，暴力
- 填数游戏：难题，数学
- 保卫王国：难题，倍增优化dp/ddp
总结：
- 规则1：每年3dp，普及(J)一只，提高(S)两只，第一天一只，第二天一只。暴力不论，正解一般是计数类dp、状压、倍增优化、套期望
- 规则2：数学成分增加
- 规则3：大山——图论，但按现在的趋势不会太复杂
- 规则4：基本套路二分贪心
- 规则5：部分分超级多，暴力打满500+
个人做题策略：暴力优先，思维压阵，二分贪心，暴力dp
有时候你甚至可以试试找找规律结论什么的