【题解】牛客NOIP暑期七天营-普及组1

该题解同步于我的博客与我的牛客博客

A

对于 $100\%$ ，直接开个桶统计即可。入门题目。

代码：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=41153707&scrollToDetail=1

B

对于 $100\%$ ，直接按题目模拟就好。每次两个指针扫一下就是 $O(n)$ 的了。整个加起来是 $O(\max(n,len)\times m)$ 的复杂度。可以结合代码理解。

代码：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=41153710

C

对于 $10\%$ 直接copy代码然后完善一下头文件什么的就行了。
考虑这个 $dp$ 是在干什么，其实就是求对于每个位置往前的前 $k$ 大的数的和。
那么对于 $40\%$ ,直接删掉第三重循环（考虑如果不选这个数，可以直接直接从 $f[i-1][j]$ 转移，所以第三重循环完全多余）
对于 $100\%$ ,用一个数据结构动态维护前 $k$ 大即可。（这里用 $set$ 或者小根堆，都行）
复杂度 $O(n\log n)$

代码：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=41153712

D

对于 $10\%$ ，很明显是个 $O(n^6 )$ 的算法..那么直接暴力枚举两个端点，然后暴力统计和取 $\max$ 即可。
对于 $30\%$ ，注意到这个矩阵的生成方式有点特别，把它写出来，就会发现一个矩阵的和是一段 $a_i$ 乘上一段 $b_j$ ，那么便可以省去统计两重循环，复杂度 $O(n^4)$
对于 $50\%$ ，考虑优化 $30$ 分的做法，30分的统计就是一个前缀和相乘的形式，那么要让它最大无非3种情况，正数最大 $\times$ 正数最大，负数最小 $\times$ 负数最小，正数最小 $\times$ 负数最大，第三种又可以分为正数最小在 $A$ 中，正数最小在 $B$ 中两种情况，于是维护前缀 $\max$ 和前缀 $\min$ ，分类讨论一下，就可以 $O(n^2)$ 解决了。
对于 $100\%$ ，既然是一段 $a_i$ 乘上一段 $b_j$ ，那么分别统计最大子段和和最小子段和即可。
最后根据 $50\%$ 的做法分四类情况讨论一下就好。这部分其实就是把 $30$ 和 $50$ 分做法综合起来而已。
复杂度 $O(n)$
至于怎么算最小子段和？全部取反求最大子段和再重新重新乘 $-1$ 即可。