\(\small {主要是我记得这一套题去年好像做过}\)
1.果园
本题主要考查的是模运算的规则(同余定理)，虽然 $ l $ , $ r $ 的 取值范围很大,直接跑两次循环的时间复杂度是 $\theta (r-l)^2 $ ，但是 \(m\) 的取值范围很小，所以考虑将 \(l \bmod m\) 作为左界, \(r \bmod m\) 作为右界时间复杂度优化至 \(\theta (m^2)\)
2.刷漆
对于区间修改，无脑选择差分，建立三个差分数组，分别代表红黄蓝，最后把数组遍历一次，查看对于下标为 \(i\) 的位置是否只有蓝和黄有颜料即可
3.着色
一道动态规划题
定义 $ dp_{i,j} $ 表示以第 \(i\) 棵树为结尾，且当前树选择了第 \(j\) 种颜料时所使用的金额最小值
状态转移方程
当然这么写直接就会炸掉
当然再次仔细观察一下数据范围 $ 1 \nmid n \nmid 10^5 \(,\) 1 \nmid m \nmid 300 $ ,再次观察状态转移方程,只和 \(i\) 与 \(i-1\) 有关 ,这就很滚动数组,只需要保留 2 个数就可以了
很好，时间又炸掉了
怎么办呢？ 再次观察状态转移方程,发现会有很多无效的循环, $ dp_{i,j} = min(dp_{i,j},dp_{i-1,k}+price_{i,j})$ 其中的 \(price_{i,j}\) 的值在循环中根本就没有变过,求 \(dp_{i-1,k}+price_{i,j}\) 的最小值进而变成了求 \(dp_{i-1,k}\) 的最小值,所以我们可以预处理出 \(dp_{i-1,k}\) 的最小值和次小值,以及最小值下标 \(min\) ,如果 \(k=mi \& min=dp_{i-1,k}\) 则取次小值 否则取最小值，这样我们就完成了时间复杂度的优化,可以优雅地过掉这一题
4.匹配
这一道题主要考查的是啥我也不知道 主要是考思维，只要想明白了每个循环节以内如何求有多少个相等的元素就简单了,把每种余数的情况枚举,并且枚举余数,就可以求出:)))))