NOIP2010~2017部分真题总结
2010
(吐槽)md这个时候的联赛还只有4题吗?
引水入城
只要发现对于有合法解的地图,每个蓄水厂贡献一段区间这个结论就很好做了
那么(O(n^3))对每个蓄水厂的dfs一遍,判掉有无解之后贪心线段覆盖
所以这是个爆搜+性质+贪心题?
关押罪犯
贪心+并查集
贪心显然正确,那么并查集维护一下每个点的补集就没了
机器翻译
暴力模拟
乌龟棋
dp
(f[i][j][p][q])表示剩余4中卡片多少张,四方枚举dp一下
或者(f[i][j][p][q])当前到第i格,三种卡片的张数(这样可以算出第四种剩多少),酱紫dp一下也行?
2011
铺地毯
模拟
既然你只询问一个格子,那么我也只维护一个格子好了,(O(n))
选择客栈
现在看来有个复杂的方法,
对每种颜色搞个前缀和,预处理个st表,
枚举左端点二分st查区间最小值
(O(nk))因为log比k小...
所以是个RMQ?
Mayan游戏
搜索
不会
计算系数
组合数
答案就是(a^n*b^m*inom{k}{n})
聪明的质监员
二分w,前缀和统计check
观光公交
贪心
发现加速器的使用互相独立,考虑每次选择对答案减少最多的路段减1,
可以每次(O(n))处理出公交车到达每个点的时间,以及每个路段能影响到的最后一个点(要停下来等人就算影响不到了),设为(f_i)
于是对i这段路减1的贡献就是(sum_{j=i+1}^{f_i}down_j)
前缀和维护下站人数即可
总复杂度:(O(nk))
2012
(吐槽)2012就两紫了woc...
(吐槽)还一年考两道倍增???
Vigenère 密码
好久远了,不记得了...
大概是模拟或者找规律?
国王游戏
贪心+高精
左手*右手大的放后面
关于这类排序贪心的证明可以考虑交换前后两个答案的变化
开车旅行
预处理出从每个点出发由A/B开车的下一个点以及距离(二分+树状数组搞一搞)
每次倍增求答案
同余方程
它大概是个...exgcd板子???
借教室
可以直接线段树直接维护最小值做
显然二分+差分更好写是吧
疫情控制
贪心+倍增
显然一个军队越靠近根越优,我们二分一个t,把军队尽量往上提,特判一下根的儿子的情况,
提的过程就倍增实现
2013
转圈游戏
它大概是个...快速幂模板???
火柴排队
我始终觉得此题巨火无比
发现一根火柴在第一列排第k,那么它就要与第二列火柴排第k的匹配,
然后因为只能swap相邻两个,
所以离散化之后映射到下标,(O(nlogn))求逆序对数就是答案
货车运输
构最大生成树,倍增
积木大赛
第一次写这个题wtm以为线段树的说...
每次在高度下降的时候统计答案就好
花匠
贪心,单调性改变时算答案
华容道
好难不会
2014
生活大爆炸版石头剪刀布
模拟
联合权值
这个东西dfs就好了吧,对相邻的点乘法原理搞一搞
飞扬的小鸟
好难啊
向上做完全背包
向下做01背包
好像对背包的顺序还有要求...
无线网络发射器选址
这不是暴力吗?
寻找道路
建反边bfs一遍找到所以满足条件1的点,再建图跑最短路
解方程
用小伟教的秦九韶(O(n))求多项式的值,
(O(mn))做就行
这个系数就考虑对大质数取模吧,多模几个稳一些
2015
神奇的幻方
按它的规则模拟就行
信息传递
有向图最小环
写个tarjan又不会死
斗地主
搜索啊,不会
跳石头
二分答案
子串
神仙dp
(f[i][j][k])表示A前i个,B前j个,匹配了k个的方案数
(s[i][j][k])表示A前i个,B前j个,匹配了k个且强制(A_i=B_j)的方案数
(s[i][j][k]=f[i-1][j-1][k-1]+s[i-1][j-1][k])
(f[i][j][k]=f[i-1][j][k]+s[i][j][k])
第一维滚掉
运输计划
先求出所有计划的时间
二分答案之后对超时的计划树上差分,找到一条被所有不合法计划都经过的边,
如果最大值-该边长度合法,那么该答案合法
2016
玩具谜题
模拟
天天爱跑步
有点长,看这里
换教室
设(f[i][j][0/1])表示前i个时间段,申请换了j次,当前这次成功与否
枚举转移就行
预处理就是跑一个(O(n^3))的最短路
组合数问题
注意到k是固定的,递推式求组合数模掉k,再求二维前缀和就没了
蚯蚓
不会呢
愤怒的小鸟
直接bfs搜过去了??
具体还可以看这里
2017
(吐槽)今年再考结论我就死了...
小凯的疑惑
a*b-a-b
时间复杂度
模拟,开栈记录变量名,标记一下是否在死掉的循环中
逛公园
k只有50,设(f[u][k])表示到u点比最短路长度不超过k的方案数
判0环:如果dp的时候搜到还在栈中的状态那么就有0环
具体还可以看这里
奶酪
把空洞,上下界看成点,把连通的并起来,最后看上下界是否连通
宝藏
状压dp
虽然复杂度可能有点假但能过就懒得管了
(f[s])表示已开发的集合为s的最小代价
枚举起点记搜一下
列队
暴力维护每一行和最后一列的splay显然爆空间
所以一开始一个点维护一行,操作就split开,这样空间大约就是(O(q))的