【题解】牛客OI周赛11-普及组

T1.多项式

20pts:

任何暴力做法大概都是可行的

50pts:

用个数组F储存这个多项式并最后进行统计

70pts:

对于i互不相同的情况，只要统计一共有多少个非零的系数。在50pts的基础上可以额外获得20pts

100pts:

在50pts的基础上用std::map来代替数组。时间复杂度 $O(nlogn)$
参考代码：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=40814364&scrollToDetail=1

T2.Game with numbers

20pts:

可能有我没想到的各种三次方的暴力呢？

50pts:

直接暴力。考虑从小到大枚举数字并检验是否合法。对于数字 $x$ ，如果它不在给出的数字范围内，就枚举 $1$ 到 $x$ 之间的数字并检验是否是它的真因数且是否合法。

100pts:

首先我们要知道正确枚举约数的姿势。对于每个数 $x$ 用vector来存它的约数。预处理时对于每个数字 $i$ ，都将 $i$ 丢到 $i$ 的倍数对应的vector里面。每次只需要检查数字 $x$ 的所有真因数是否合法就好了。
上面那个做法常数比较大我不确定是不是能过。考虑每次枚举 $i$ 并更新 $i$ 的倍数的情况，就可以丢掉常数巨大的vector。具体实现详见代码。时间复杂度 $O(nlogn)$
参考代码：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=40814346&scrollToDetail=1

T3.Colorful

10pts:

爆枚所有生成树并更新答案。

40pts:

爆枚所有的颜色集合，考虑当前颜色集合对应的那些边是否能让图联通。每次加入所有的边并检查。

100pts:

注意到对于一个颜色集合，我们并不需要知道确切哪些边是这些颜色的，我们只需要知道这些边能带来的联通信息。所以我们可以保留其中的至多 $n – 1$ 条边，并枚举颜色集合检查。时间复杂度 $O(n^{2}\times 2^{s} + m)$ 。 $O(n^{3} \times 2^{s} + m)$ 的做法应该能过60.
参考代码：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=40814363&scrollToDetail=1

T4.凸包的交

10pts:

寻找最大值并输出

20pts:

枚举所有合法的区间并统计答案

40pts:

二分答案x，对每个数都减去x，求一边前缀和并检查有没有距离大于 $L$ 的下标使得后面的比前面的大。可以通过维护前缀最小值实现。

额外的20pts:

注意到此时循环节长度至多是 $100$ 。考虑处理出一个完整的循环节。如果循环节总和是负的，只需要枚举区间长度大于等于 $L$ 的区间所覆盖的那坨循环节中第一个和最后一个所覆盖到的量。否则答案一定是占满中间所有的循环节，在序列中的头尾两个循环节枚举即可。

100pts

处理出前缀和 $s_{i}$ 。任意一段区间的贡献可以被表示为 $\frac{s_{i} – s_{j}}{i – j}$ ，其中 $L \leq i – j$ . 这显然是一个斜率的形式。那么我们维护点 $(i,s_{i})$ 所对应的下凸包并在凸包上二分获得答案。因为数据是随机的，所以凸包的大小很小，说不定有可能能过？？