【题解】牛客网NOIP赛前集训营-普及组（第六场）

A金币

首先把[l,r]转化成[1,r]-[1,l-1]

从小到大枚举金币数i，记录当前剩余天数leave

当leave>=i^2时，将i^3加入答案，leave-=i^2；

否则将leave*i加入答案，并输出答案。

时间复杂度O(n^(1/3))

B网格

首先模拟求出s，然后枚举|s|次，每次把s最右的字符移到最左边，然后暴力比较和答案的字典序大小。

时间复杂度O(q*min(n,m)^2)

C

疏远度

先考虑给你一个集合

，如何求

。

然后把max的和通过暴力枚举每一个max的取值换成和的max：

这里的w是一个k维向量，每一维都是-1或者1。

然后交换枚举顺序：

然后将x，y的贡献分开计算：

时间复杂度

回到原问题，用并查集维护每个人所在的集合，现在我们需要支持合并两个合集，询问某个集合的答案。

当合并两个集合S,T的时候，新的最大值要么是原来的答案，要么是

。通过类似上面的方法，只需对每个S，w维护

即可

计算这个最大值。

时间复杂度

D

Wi-Fi

首先考虑如何计算覆盖所有公司需要的最小建设费用。

覆盖长度为len的一段的费用本来是A+len*B/2，

为了方便，我们令a=A*2，b=B，令费用=a+len*b，最后再把答案除掉2。

假设将所有公司坐标排好序后为 p_{1..n}。

注意到，可以把选择的费用分配到选择的边上。

可以理解为一开始在每个点都建一个基站，费用为n*a，然后每多选一条边，费用就变化len*b-a (设len为边的长度)。

所以答案就是

。

std

A:

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=40157825

B:

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=40157827

C:

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=37072606

D:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=40157832