2011-2020 NOI 第一题 & NOIp 最后一题 解题报告

$Total\ 1674pts$

NOI 第一题

NOI 2011 兔农

$Unaccepted\ 75pts$

我们考虑用$f_i$表示第$i$个月的兔子对数，然后按照斐波那契数列递推
$$
f_1=f_2=1\\
f_i=f_{i-1}+f_{i-2}(i>2)
$$
按照题意，如果$f_i\equiv1\pmod k$，就让$f_i=f_i-1$。

最后答案就是$f_n\mod p$。

容易发现以上过程可以在$\mod kp$的意义下进行，这样开个long long就能够拿到$75pts$。

NOI 2012 随机数生成器

$Accepted$

显然是使用矩阵加速递推。
$$
\begin{pmatrix}
X_0 & X_1
\end{pmatrix}
\begin{pmatrix}
a & 0 \\
c & 1
\end{pmatrix}^n =
\begin{pmatrix}
X_n & X_{n+1}
\end{pmatrix}
$$
需要注意的是本题数据范围极大，运算过程中可能会爆unsigned long long，所以考虑使用龟速乘避免运算过程中的溢出。

NOI 2013 向量内积

$Accepted$

注意到本题$k$只能为2和3，所以从这里入手。

我们要找出两个向量其内积为$k$的整数倍，实际上就是在$\mod k$的意义下两个向量的内积为0。

一下所有操作在模意义下进行。

那么$k=2$的时候，所有向量就都由01组成。

于是我们考虑对于第$i$个向量，让它去乘前面的所有向量然后求和，假如这个向量无法和前面的向量组成合法解，那么这个和一定是$(i-1)\mod k$。

否则就暴力在它前面的向量中找合法解就可以了。

前缀和是可以在处理过程中$O(1)$维护的，所以总复杂度是$O(nd)$。

$k=3$的时候有点不一样，此时向量由012组成，求得的和也可能是012，但我们只希望有01两种结果。

此时注意到$1^2\equiv2^2\equiv1\pmod3$，所以我们按照$k=2$时的思路求前缀平方和就可以了。

同样道理，总复杂度是$O(nd^2)$。

NOI 2014 起床困难综合症

$Accepted$

考虑设int a = 0, b = 0x7fffffff，把每个门跑一遍，就能够得到每一位的真值表。

接下来对每一位进行贪心，0能够变1的话就变，1能够变1的话，如果不超过$m$的话也变，然后就能够贪心过掉本题。

NOI 2015 程序自动分析

$Accepted$

容易想到用并查集来维护相等的关系，然后对于每个不想等的关系，只需查询它们所属的集合是否不同即可。

本题需要离线操作，现将所有相等变量的并查集合并，然后查询不相等变量。

由于$i,j\leq10^9$，而$n\leq10^5$，$i,j$极大但$n$很小，所以需要对$i,j$进行离散化。

NOI 2016 优秀的拆分

$Unaccepted\ 95pts$

考虑暴力$hash$维护$a_i$和$b_i$分别表示以第$i$个字符开头和结尾的形如$AA$形式的串的个数，则答案为
$$
\sum\limits_{i=0}^{n-1}a_{i+1}b_i
$$
复杂度$O(n^2)$，可以拿到优秀的$95pts$。

NOI 2017 游戏

$Unaccepted\ 50pts$

$dfs$暴力搜索赛车的使用方案即可拿到$50pts$。

NOI 2018 归程

$Accepted$

首先，回家路线一定能够被分成两段，一部分坐车，一部分步行。

首先考虑坐车部分，我们考虑使用以海拔为关键字建立$Kruskal$重构树，此时重构树上，深度由浅到深的结点其海拔也是由高到低的。

这样对于每次询问中的$p_0$，我们就从$v_0$开始在树上倍增，找到点$v$使得$h_v>p_0$且$h_{fa(v)}\leq p_0$，这样，重构树上以$v$为根的子树中所有叶子结点在图中对应的结点就都是连通的，换言之，我们可以以$0$的花费到达这其中的任一结点。

所以只需要找出子树中哪个节点离家最近，这显然是个最短路，跑一遍$Dijkstra$，然后对于每次询问，在重构树上跑$dfs$维护以树中每个结点为根的子树中，到$1$的最短距离即可。

NOI 2019 回家路线

$Unaccepted\ 95pts$

$dfs$暴力搜索所有路线即可拿到$95pts$的优秀成绩。

NOI 2020 美食家

$Accepted$

除去美食节，本题可以简化一下：

求从$1$出发经过恰好$T$条边回到$1$的最长路。

这里为了方便结题我们使用了拆点，也就是说，对于一条$u\to v$的边，若$c_v=k$，我们就将这条边变为$u_1\to u_2\to\cdots\to u_k\to v$，其中，除了最后一条边边权为$c_v$之外，别的边权都为$0$。

容易想到朴素的$dp$
$$
dp_{i,j,k}=\max_p\{dp_{i-1,j,p}+G_{p,k}\}
$$
表示从$j$出发走$i$步到$k$的最长路，$G$为邻接矩阵。

容易想到矩阵加速$dp$
$$
dp_i=dp_{i-1}\times G
$$
但这里要重定义矩阵乘法为
$$
A\times B=C\\
C_{i,j}=\max_k\{A_{i,k}+B_{k,j}\}
$$
可以证明重定义后的矩阵乘法满足结合律
$$
A\times B\times C=D\\
\begin{aligned}
D_{i,j}&=\max_k\{(A\times B)_{i,k}+C_{k,j}\}\\
&=\max_k\{\max_p\{A_{i,p}+B_{p,k}\}+C_{k,j}\}\\
&=\max_{k,p}\{A_{i,p}+B_{p,k}+C_{k,j}\}\\
&=\max_p\{A_{i,p}+\max_k\{B_{p,k}+C_{k,j}\}\}\\
&=\max_p\{A_{i,p}+(B\times C)_{p,j}\}
\end{aligned}\\
Q.E.D.
$$
于是有
$$
dp_i=dp_0\times G^i
$$
接下来考虑美食节，我们把整个矩阵加速的过程分开就行了，在美食节举办的时间之间进行加速，举办时就在相应的位置加上$y$。

注意为了保证时间复杂度我们要对$G^{2^k}$进行预处理。

NOIp 最后一题

NOIp 2011 观光公交

$Accepted$

非常巧妙的贪心。

考虑对于每个车站设两个状态：

• $arrive_i$表示到达该车站的时间
• $latest_i$表示在该车站上车的乘客最晚的到站时间

于是，显然对于每个车站就有两种状态：

• $arrive_i<latest_i$，车等人，即车到了站人还没到
• $latest_i\leq arrive_i$，人等车，即人都到了站车还没到

对于每个$N2O$的使用位置我们都进行一次贪心，贪心的依据即是放在某段路上能够造福的乘客数量。

放到第$i$段路上后，会造成$D_i-1$，那么考虑$D_i-1$会对哪些$arrive$造成影响，只要对$arrive_k$造成影响，在$k$站下车的乘客就都会被造福。

容易想到，我们只需要从$i+1$开始往后找，直到找到第一个车等人现象时，这以后的$arrive$就都不会受到影响。

这样贪心就能够过掉本题。

NOIp 2012 疫情控制

$Accepted$

这题细节很多，代码调起来非常累。

考虑二分答案+贪心，

• 首先将所有军队在树上向上提，在限定时间内能走多高就走多高，最高走到根结点的子节点上

  于是出现了两种情况，

  • 走不到根结点的子节点，或走到根结点子节点无法再走的，就地停留，并标记该子树已被控制
  • 能够继续走的，我们将其存起来

• 检查当前的控制情况，将所有没有被控制的子树找出来

• 接下来，我们有了两个数组restArmy和noControl，将他们排序

  遍历noControl，接下来又有了两种情况，

  • 如果我们发现有一个restArmy就在当前noControl所处的那棵子树，那么就让这个restArmy去控制它，并标记其已被使用
  • 否则，找到一个能够走到noControl所处子树的restArmy，并标记其已被使用

这就是整个贪心策略，实现的时候，还要加入倍增对第一步贪心中将军队在树上向上提的过程进行优化。

这样就能过掉本题。

NOIp 2013 华容道

$Accepted$

这题首先是如何记录状态，固定的格子始终不会变，所以只需要一个全局bool数组记录即可，剩下的部分，我们只需要记录指定棋子和空白格两个位置就够了，剩下的格子全部是普通棋子。在移动的时候也是一样，直接考虑移动空白格。

再抽离一下状态，我们发现，有用的状态中空白格一定紧挨着指定棋子，所以我们的状态储存就只需要三个参数：

• 指定棋子$x$坐标
• 指定棋子$y$坐标
• 空白格在指定棋子的上/下/左/右

在所有有用状态中，我们用$bfs$在他们之间连边，边权是移动步数，然后每次询问我们只要在图上跑最短路即可。

NOIp 2014 解方程

$Accepted$

需要用到秦九韶算法，这样，每次检验一个根是否合法都只需要进行$n$次加法和$n$次乘法。

总复杂度就是$O(nm)$。

值得注意的是，这道题$|a_i|$巨大，打高精度肯定不现实，所以考虑用大质数取模。

比如模数取到$10^9+7$时就可以过掉本题，考场上其实为了保险，可以用双重模数降低出错的概率，虽然复杂度会多个2的常数，但仍然能够接受。

NOIp 2015 运输计划

$Unaccepted\ 25pts$

对于$n=100$的三个点，可以直接暴力枚举删边，$O(n^2m)$的复杂度拿到$15pts$。

另外还有$m=1$的两个点，这个时候我们只需要处理这一条路径上的边权和和最长边，最后答案就把它们作差即可，复杂度$O(n)$。

总得分$25pts$。

NOIp 2016 愤怒的小鸟

$Accepted$

最多18只猪，容易想到状压$dp$。

考虑用一个$n$位二进制数表示状态，0表示没有被打到的猪，1反之。

设$dp_i$表示状态为$i$时最少需要用多少只鸟。

这就是大体思路。

再来说一下二次函数怎么算。二次函数由两点确定，设这两点是$(x_i,y_i)$和$(x_j,y_j)$。

设解析式为$y=ax^2+bx$，于是有
$$
\begin{cases}
y_i=ax_i^2+bx_i \\
y_j=ax_j^2+bx_j
\end{cases} \\
$$
先考虑求$a$，两式左右分别乘上$x_j$和$x_i$就有
$$
\begin{cases}
y_ix_j=ax_i^2x_j+bx_ix_j \\
y_jx_i=ax_j^2x_i+bx_jx_i
\end{cases}
$$
两式相减得
$$
y_ix_j-y_jx_i=ax_i^2x_j-ax_j^2x_i
$$
然后就很明显了吧，把$x$除到左边来，
$$
\begin{aligned}
y_ix_j-y_jx_i&=a\left(x_i^2x_j-x_j^2x_i\right) \\
a&=\frac{y_ix_j-y_jx_i}{x_i^2x_j-x_j^2x_i}
\end{aligned}
$$
类似的方法可以求出$b$
$$
\begin{aligned}
&\begin{cases}
y_ix_j^2=ax_i^2x_j^2+bx_ix_j^2 \\
y_jx_i^2=ax_j^2x_i^2+bx_jx_i^2
\end{cases} \\
\implies&y_ix_j^2-y_jx_i^2=bx_ix_j^2-bx_jx_i^2 \\
\implies&y_ix_j^2-y_jx_i^2=b\left(x_ix_j^2-x_jx_i^2\right) \\
\implies&b=\frac{y_ix_j^2-y_jx_i^2}{x_ix_j^2-x_jx_i^2}
\end{aligned}
$$

NOIp 2017 列队

$Unaccepted\ 60pts$

首先前面$30pts$是可以直接暴力模拟拿到的不多说。

然后注意到有$30pts$的点保证所有操作$x=1$，这个时候我们发现，所有操作都只会影响到第一行和最后一列，并且最后一列每次操作都会移走第一行的元素，然后整体上移，再在最后添加一个元素，显然这是一个队列，所以就用$queue$维护就行了。

比较难搞的是第一行，会在中间拿走一个元素，为了保证复杂度，我们使用一个数组，最开始全部都是1，从中间拿走一个数后，就把相应位置改为0，再用树状数组维护前缀和，容易发现如果我们要拿走第$k$个元素，只需要查找前缀和为$k$的位置就可以了，查找的过程显然可以使用二分，这样复杂度就是两个$\log$，可以顺利拿到这$30pts$。

NOIp 2018 保卫王国

$Unaccepted\ 84pts$

首先，暴力给树染色的复杂度是$O(nm)$的，这就能够通过前11个测试点了。

然后再来考虑题目给出的特殊性质。

$A$实际上就是链的情况，这样只要考虑限制点编号的奇偶就可以了，所以能拿到$A1$，$A2$，$A3$三档分。

然后是询问限制，1的话我们直接提前按照顶点强制驻军给树染色一遍，这样就能做到询问$O(1)$了，可以拿到$B1$，$C1$两档分。

这样能拿到优秀的$84pts$。

CSP-S 2019 树的重心

$Unaccepted\ 55pts$

暴力加上特判性质$A$（链）的情况，可以拿到$55pts$。

NOIP 2020 微信步数

$Unaccepted\ 35pts$

直接按照题意模拟，如果步数超过$10^6$直接判断走不出去，这样可以顺利拿到第一档$30pts$，甚至能够混到第二档的$5pts$。

本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。