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
有时候你甚至可以试试找找规律结论什么的