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

T1.多项式

20pts:

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

50pts:

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

70pts:

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

100pts:

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

T2.Game with numbers

20pts:

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

50pts:

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

100pts:

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

T3.Colorful

10pts:

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

40pts:

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

100pts:

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

T4.凸包的交

10pts:

寻找最大值并输出

20pts:

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

40pts:

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

额外的20pts:

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

100pts

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

现在我们考虑另一种操作，每次把凸包头部的点都删掉，直到留下来的第一个点的是当前最优解。不难发现复杂度变成了线性的。考虑脑补它的正确性。如果某个点的最优解被提前删掉了，肯定意味着有一个更优的点在前面。于是它就是正确的了。时间复杂度。

详细证明：考虑某个点，它所配对的最优解不幸被之前的操作删去了。我们假设在对点的操作时删去了点的最优解，删去的最优解意味的最优解在后面，显然斜率更大（因为下凸包斜率递增），于是乎的答案被删掉了也无伤大雅。

参考代码https://ac.nowcoder.com/acm/contest/view-submission?submissionId=40814359&scrollToDetail=1
//综合来看，这套题放PJ应该是比较简单易AK的，大家做题快乐。