2011~2018 年 NOIP 真题分析

作者: xht37 分类: 记录 发布时间: 2019-11-14 23:31

点击数:304

2011~2018 年 NOIP 真题

2011

铺地毯

  • 算法:枚举。
  • 思路:倒序处理,时间复杂度 $\mathcal O(n)$。

选择客栈

  • 算法:枚举。
  • 思路:用一个数组记录当前位置之前每个色调合法的客栈数量,时间复杂度 $\mathcal O(n)$。

Mayan 游戏

  • 算法:搜索,剪枝。
  • 思路:防 AK 题,暴力搜索,需要剪枝。

计算系数

  • 算法:组合计数。
  • 思路:$ans = a^nb^mC_{k}^{n}$。

聪明的质监员

  • 算法:二分答案,前缀和。
  • 思路:二分 $W$ 的值,$\mathcal O(n)$ 计算出只考虑 $w_i \ge W$ 时的 $v$ 的前缀和与数量前缀和,$\mathcal O(m)$ 扫一遍求出答案,时间复杂度 $\mathcal O((n+m)\log W)$。

观光公交

  • 算法:贪心。
  • 思路:先求出不使用氮气加速器时的时间安排,然后做 $k$ 次贪心,每次贪心找到能够减少时间最多的位置,时间复杂度 $\mathcal O(nk)$。

2012

Vigenère 密码

  • 算法:模拟。
  • 思路:其实是个 $26$ 进制不进位加法。

国王游戏

  • 算法:贪心,排序,高精度。
  • 思路:大臣按照左右手上的数的乘积由小到大排序是最优的,这个贪心可以通过「邻项交换」证明,最后需要手写高精度。

开车旅行

  • 算法:倍增。
  • 思路:首先预处理出两人从每个城市出发到达的下一个城市,可以用 set 维护,然后倍增处理出两人从每个城市出发到达的第 $2$ 的次幂个城市以及两人行驶的路程长度;考虑 $\text{calc}(S, X)$ 为「从城市 $S$ 出发最多行驶 $X$ 公里」时两人分别行驶的路程长度,计算时基于二进制划分思想拼成 $X$ 即可;总时间复杂度为 $\mathcal O((n + m)\log n)$。

同余方程

  • 算法:扩展欧几里得。
  • 思路:扩欧板子题。

借教室

  • 算法:二分答案,前缀和。
  • 思路:二分可行的订单数量,判定用前缀和优化,时间复杂度 $\mathcal O(n \log m)$。

疫情控制

  • 算法:二分答案,树上倍增,贪心
  • 思路:显然必须往祖先走,那么二分答案,往祖先走的过程可以倍增优化,最后扫一遍即可,时间复杂度 $\mathcal O(n \log n + \log w (m \log n + n))$。

2013

转圈游戏

  • 算法:快速幂。
  • 思路:$ans = (m \times 10^k + x) \bmod n$。

火柴排队

  • 算法:归并排序/树状数组。
  • 思路:显然大的要对应大的,那么离散化后就相当于对 $b$ 基于 $a$ 邻项交换排序,答案就是逆序对个数,归并排序或者树状数组求都行,时间复杂度 $\mathcal O(n \log n)$。

货车运输

  • 算法:kruskal,树上倍增。
  • 思路:先求最大生成树,然后找树上路径最大值,时间复杂度 $\mathcal O(n \alpha (n) + m \log m + q \log n)$。

积木大赛

  • 算法:贪心。
  • 思路:$ans = h_1 + \sum_{i=2}^n \max(a_i – a_{i-1}, 0)$。

花匠

  • 算法:dp。
  • 思路:设 $f[i][0/1]$ 表示以 $i$ 结尾的最后一段是上升/下降的最长子序列,然后随便转移一下就好了,时间复杂度 $\mathcal O(n)$。

华容道

  • 算法:搜索,剪枝。
  • 思路:防 AK 题,爆搜,大概可以 A*,好像还能跑最短路。

2014

生活大爆炸版石头剪刀布

  • 算法:模拟。
  • 思路:依照题意模拟即可。

联合权值

  • 算法:枚举。
  • 思路:枚举所有点,最大值就是周围所有点中最大的两个值相乘,和就是周围所有点的权值和的平方减去权值的平方和,时间复杂度 $\mathcal O(n + m)$。

飞扬的小鸟

  • 算法:dp,背包。
  • 思路:设 $f[i][j]$ 表示到坐标 $(i,j)$ 时的最小答案,暴力转移是 $\mathcal O(nm^2)$ 的,注意到上升实际上是完全背包,下降实际上是 $01$ 背包,那么可以直接优化到 $\mathcal O(nm)$。

无线网络发射器选址

  • 算法:模拟。
  • 思路:xjb 模拟 xjb 优化。

寻找道路

  • 算法:bfs。
  • 思路:先建反图把所有合法节点找到,再在合法节点找 bfs 找最短路。

解方程

  • 算法:模拟,hash。
  • 思路:$\mathcal O(nm)$ 模拟,利用 hash 思想,将 $a_i$ 在模意义下计算。

2015

神奇的幻方

  • 算法:模拟。
  • 思路:依照题意模拟即可。

信息传递

  • 算法:基环树。
  • 思路:基环森林找最小环,$\mathcal O(n)$ 做一遍就好了。

斗地主

  • 算法:贪心,搜索。
  • 思路:防 AK 题,贪心求出搜索的顺序然后爆搜就好了。

跳石头

  • 算法:二分答案。
  • 思路:二分最短跳跃距离的最大值,判定时小于这个值的石头就要移走,最后比较移走石头的数量与 $m$ 的大小,时间复杂度 $\mathcal O(n \log l)$。

子串

  • 算法:dp。
  • 思路:设 $f[i][j][k]$ 表示 $A$ 中考虑到前 $i$ 个,匹配了 $B$ 的前 $j$ 个,此时用掉了 $k$ 个子串,且 $A$ 中第 $i$ 个必须选的方案数,然后 xjb 转移一下就好了,时间复杂度 $\mathcal O(nmk)$。

运输计划

  • 算法:二分答案,树上倍增,树上差分。
  • 思路:二分最大时间,找到所有原本时间比此时答案大的链,树上差分找到被所有这样的链覆盖的边中消耗时间最大的,如果减掉后最大时间比此时答案小则合法,时间复杂度 $\log w(m \log n + n)$。

2016

玩具谜题

  • 算法:模拟。
  • 思路:依照题意模拟即可。

天天爱跑步

  • 算法:树上差分,线段树合并。
  • 思路:首先将路线拆成 $[s_i, \text{lca}(s_i,t_i)]$ 和 $(\text{lca}(s_i, t_i), t_i]$ 两段,两段方法类似;只考虑前者,将统计条件转化为一个简单的等式 $d[s_i] = d[x] + w[x]$;然后有两种解决方案,要么用线段树合并板子,要么再次利用「区间减法」性质,可以直接 $\mathcal O(n)$ 实现。

换教室

  • 算法:期望,dp,Floyd。
  • 思路:设 $f[i][j][0/1]$ 为考虑前 $i$ 个换了 $j$ 次最后一个是否换的最小期望值,然后 xjb 转移,两点间的最短路用 Floyd 预处理,时间复杂度 $\mathcal O(v^3 + nm)$。

组合数问题

  • 算法:组合数,二维前缀和。
  • 思路:$\mathcal O(nm)$ 处理出所有组合数 $\bmod k$ 的值,然后做一次二维前缀和即可做到 $O(1)$ 查询。

蚯蚓

  • 算法:模拟,队列。
  • 思路:依照题意模拟,由于具有单调性所以用三个队列即可,时间复杂度 $\mathcal O(n \log n + m)$。

愤怒的小鸟

  • 算法:状压。
  • 思路:看数据范围可以发现状压挺显然的,转移时加一点小优化时间复杂度可以到 $\mathcal O(Tn2^n)$。

2017

小凯的疑惑

  • 算法:数论。
  • 思路:$ans = a * b – a – b$。

时间复杂度

  • 算法:模拟。
  • 思路:依照题意模拟即可。

逛公园

  • 算法:dp。
  • 思路:要建反图,设 $f[i][j]$ 表示第 $i$ 个点到第 $n$ 个点多走 $j$ 时间的路线数量,然后 $\mathcal O(mk)$ dp 即可。

奶酪

  • 算法:bfs/dfs/并查集。
  • 思路:$\mathcal O(n^2)$ 随便做。

宝藏

  • 算法:状压。
  • 思路:按层状压,时间复杂度 $\mathcal O(n3^n + m2^n)$ 或 $\mathcal O(n^22^n)$。

列队

  • 算法:平衡树。
  • 思路:将方阵分为「最后一列」和「除去最后一列的每一行」共 $n+1$ 个序列,然后就是平衡树板子题了。

2018

铺设道路

  • 算法:贪心。
  • 思路:原题,$ans = h_1 + \sum_{i=2}^n \max(a_i – a_{i-1}, 0)$。

货币系统

  • 算法:贪心,数论,完全背包。
  • 思路:如果大的能被小的线性表示则不要大的,做个完全背包即可。

赛道修建

  • 算法:二分答案,贪心,树形 dp。
  • 思路:首先二分答案,然后可以根据「分支不超过 $3$」的部分分想出正解:进行一次类树形 dp 的过程,访问完点 $u$ 后将其儿子对应的最长链两两最优匹配,如果有剩下的,则将其中最大的作为 $u$ 的最长链往上传,用 multiset 实现非常简单,时间复杂度 $\mathcal O(n \log n)$。

旅行

  • 算法:贪心,dfs。
  • 思路:如果是树则直接贪心做,如果是基环树则暴力删边然后当成树做,时间复杂度 $\mathcal O(n^2)$。

填数游戏

  • 算法:打表找规律。
  • 思路:写个爆搜打个表找个规律就完事了。

保卫王国

  • 算法:树形 dp,换根 dp,树上倍增。
  • 思路:动态 dp 模板然而我不会;设 $f[i][0/1], g[i][0/1]$ 为 $i$ 的状态为 $0/1$ 时,以 $i$ 为根的子树和去掉这个子树的最小代价,这个树形 dp + 换根 dp 求即可;设 $h[i][j][0/1][0/1]$ 为 $i$ 的状态为 $0/1$,$i$ 的 $2^j$ 级祖先的状态为 $0/1$ 时,$i$ 的 $2^j$ 级祖先的子树去掉 $i$ 的子树的最小代价;对于每次询问,用类似求 $LCA$ 的方法同样倍增处理即可,时间复杂度 $\mathcal O((n + q) \log n)$。

总结

大概率考到的算法

  • 基础算法:枚举,模拟,贪心,递推,递归,搜索(剪枝)。
  • 基本技巧:位运算,二分(答案),前缀和/差分,(归并)排序,倍增,hash,打表找规律。
  • 数学:简单数论,简单组合计数,概率期望。
  • 数据结构:队列,栈,堆,并查集,树状数组。
  • 动态规划:线性 dp,背包,树形/换根 dp,状态压缩 dp,倍增优化 dp,概率期望 dp。
  • 图论:最短路(dijkstra/floyd),最小生成树(kruskal),树上倍增,树上差分,树的直径,树形/换根 dp,基环树。

发表评论

电子邮件地址不会被公开。 必填项已用*标注