2011~2018 年 NOIP 真题分析

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，基环树。