NOIP 2018总结

### 总述 NOIP 2018已过去了五十余天了，连证书都已经到了，但我的总结迟迟未写，主要是被D2T2和D2T3这两道神奇的题目所困，花了很长时间才订正完成。由此可以看出，今年的题目区分度主要体现在难题上，这要求我们迅速完成较为简单的题目，并用剩下的时间在难题中拿到尽量高的分数。 ### D1T1 [铺设道路](https://www.luogu.org/problemnew/show/P5019) 这是一道思维较为困难、实现较为简单的题目。 #### 平均$\text{O}(n \log n)$ 最差 $\text{O}(n^2)$的方法 最简单直观的方法就是，直接扫描数组，找到当前范围的最小值；把最小值加到答案中，再把当前范围所有元素全部减去最小值，再用$0$（即原来的最小值）把当前范围分为若干个小块，对每个小块递归求解，直到所有元素都为$0$为止。 复杂度分析类似朴素快排，倒序数据（如$5,4,3,2,1$）即可把它卡到$\text{O}(n^2)$，这里有一份[hack数据](https://www.luogu.org/problemnew/show/U52578)。 #### $\text{O}(n \log n)$的方法 上面的方法由于暴力求最小值需要最差$\text{O}(n)$的复杂度，因此可能会被卡成$\text{O}(n^2)$。我们可以使用$\text{RMQ}$（即稀疏表，Sparse Table）来把求最小值的过程优化到$\text{O}(\log n)$，从而最差时间复杂度变为$\text{O}(n \log n)$，可以通过上述hack数据。 #### $\text{O}(n)$的正解 考虑动态规划。设$f[i]$为只把$1$到$i$的道路填平至少需要的操作数。那么，我们显然有$f[1]=a[1]$。 下面讨论$f[i]$的递推式。 如果$a[i]\le a[i-1]$，那么$f[i]=f[i-1]$，因为只需在操作$a[i-1]$的时候顺便操作$a[i]$即可，不需要额外的操作。 而如果$a[i]>a[i-1]$，那么我们就一定需要额外的操作来单独操作$a[i]$。如果要操作$a[i]$，那么就只有单独操作和区间操作两种；而区间操作必定涉及到$a[i-1]$，也就至多进行$a[i-1]$次；因此一定要进行至少$a[i]-a[i-1]$次的单独操作。于是我们得到$f[i]=f[i-1]+(a[i]-a[i-1])$。 于是，我们只需不断读入$a[i]$，并更新$f[i]$的值，最后输出$f[n]$即可。当然，实际上不需要数组存储。 关于这题的正解，有一道改编的数学题，题目和答案可以看[这里](https://sweetlemon.blog.luogu.org/rubbish)。 ### D1T2 [货币系统](https://www.luogu.org/problemnew/show/P5020) 这是一道比较简单的$\text{dp}$，但是在考场上我用了过于复杂的方法，导致浪费了大量时间。