2019-11-02 23:06 已编辑中国石油大学（华东）计算机类

关注

【题解】牛客CSP-S提高组赛前集训营3

T1货物收集

部分分设置

对于 $30\%$ 的数据，给阶乘级别的搜索算法。

对于 $60\%$ 的数据，考虑对所有边权排序，然后每次增加的量肯定是某两个边权的差值。模拟增加过程，当满足条件时输出即可。时间复杂度 $\mathcal{O}(n^2)$

对于链上的情况，贪心向两端扩展即可。

题解思路

我们考虑经过一条边并不会减少我们的武力值。

我们只需要二分一个我们的武力值，然后O(n)判断一次当前能取到多少货物，就可以了。时间复杂度 $\mathcal{O}(nlogv)$

T2 货物分组

Notice: 这道题在考试过程中，为了卡掉一些剪枝的暴力，不小心把错误的贪心全部放过去了，正在重造数据。
UPD: T2数据已经重新构造，并且已经重测。为大家带来的不好体验，我表示万分抱歉。

部分分设置

对于10%的数据，我们暴力枚举分组数以及分组情况。

对于30%的部分分，留给 $n^3$ 暴力DP

对于60%的部分分，我们稍后会介绍一个 $n^2$ 暴力DP

正解思路

首先考虑一个DP

$f[n][m]$ 表示前n个分成m组的最小花费。我们只要枚举 $k$ 之后 $f[n][m]=min\{f[k][m-1]+m*(s(n)-s(k))+max(n \text{~} k+1)-min(n\text{~}k+1)\}$
其中 $s(n)$ 表示物品代价的前缀和。
这样转移是 $n^3$ 的。我们考虑使用先付代价来DP.

$f(n)$ 表示前n个分成若干组的最小代价。那么我们枚举k之后

$f(n)=min\{f[k]+cost(k+1,n) + sum\_all - sum(1\text{~}n)\}$

其中 $cost(l,r)$ 表示l~r的重量和加上其中最大值减最小值。

这样是 $n^2$ 的。

我们发现我们在转移过程中，可以用一个单调栈来维护最大值和最小值的变换，然后用线段树维护区间最值，就能每次 $\mathcal{O}(log\ n)$ 更新答案。

时间复杂度 $\mathcal{O}(nlogn)$

T3 地形计算

部分分设置

对于 $30\%$ 的分数，给直接 $\mathcal{O}(n^4)$ 暴力枚举点然后判断的做法。

对于 $60\%$ 的做法，给 $\mathcal{O}(n^2)$ 或可能存在的 $\mathcal{O}(n^2 poly(log(n)))$

解题思路

首先我们考虑一个很Naive的暴力，从每个点往下搜四层，如果回到了这个点，那么说明有一个四元环，我们把中间经过的点累加进答案。

这样每次扩展 $n$ 个点，扩展四次，时间复杂度 $\mathcal{O}(n^4)$ ，如果你的实现比较美观的话，是 $\mathcal{O}(n^3)$ 的，不过因为算法本质相同，并没有设置这两种实现方式的分数区分。

我们考虑另一种做法，不扩展四层，而是每次扩展两层，用一种MIM(Meet In Middle)的方式统计答案，时间复杂度就降到了 $\mathcal{O}(n^2)$ ，可以拿到60分。

似乎已经没有更好的方法了，但是我们考虑对于60分的做法，我们切换枚举顺序，从度数最大的点开始枚举。

每次枚举完毕以后，删去度数最大的点，然后重复这个过程，也能统计出答案。正确性显然，我们考虑这个做法的复杂度。每次都使 $n$ 减小1，那么复杂度为 $\mathcal{O}(n+(n-1)+(n-2)+...+1)=\mathcal{O}(n^2)$ 看起来没什么用，只是多了一个 $\frac{1}{2}$ 的常数。

~~但是因为Venn在这种做法上施加了魔法，所以复杂度是正确的。~~

其实我们上述复杂度的分析，给出的复杂度上界达不到，我们考虑 $O(n^2)$ 并不是他的时间复杂度。我们换一种分析方式，对于选择的每一个度数小于 $\sqrt{m}$ 的点，他向外会扩展最多 $sqrt(m)$ 次。对于度数大于 $\sqrt{m}$ 的点，他会向外扩展多次，但是由于所有点的度数之和不能超过2倍的 $m$ ,所以单次均摊是 $m$ 次扩展，这样的点不会超过 $\sqrt{m}$ 个，因为所有点的度数之和等于 $2m$ 。那么总时间复杂度就为 $\mathcal{O}(m\sqrt{m})$

全部评论

推荐最新楼层

Asuka_Minato

楼主

中国石油大学（华东）计算机类

对于T2,这道题在考试过程中，为了卡掉一些剪枝的暴力，不小心把错误的贪心全部放过去了，正在重造数据。 T3稍后也会加入更强的数据。对于数据很水，我表示非常抱歉。

送花回复

发布于 2019-11-02 22:23

End_donkey

电子科技大学

为什么T2无脑装满就能AC。。。。

送花回复

发布于 2019-11-02 22:16

滴滴

校招火热招聘中

官网直投

L______

C++

T2T3数据让老实人很愤怒

送花回复

发布于 2019-11-02 22:21

I™

C++

t1贪心能过，用bfs，每次选取边权最小的边

送花回复

发布于 2019-11-03 14:47

日子难过

C++

如果有std就更加好评了

送花回复

发布于 2019-11-03 15:44

Paulliant

算法工程师

我T3特判了度为1的菊花还是A了鸭？？n^2

送花回复

发布于 2019-11-03 08:10

User_Does_Not_Exist

C++

T3 最后两个点puts("0") 就过了。。。

送花回复

发布于 2019-11-03 08:35

gcp_

C++

第三题数据还是有点水啊，表示没从度数最大开始也A暴力掉了 https://ac.nowcoder.com/acm/contest/view-submission?submissionId=41580161

送花回复

发布于 2019-11-03 17:49

EquationX

北京理工大学

在？我发现了一个AC代码，然而连样例都过不去的？ https://ac.nowcoder.com/acm/contest/view-submission?submissionId=41573657

送花回复

发布于 2019-11-02 22:20

EquationX

北京理工大学

关于第二题： f[i]表示前i个分成若干组,后面的分成一组的最优解设Range(l,r)=max(a[l..r])-min(a[l..r]);这是极差设cost(l,r)=sum[r]-sum[l-1]+Range(l,r);一段区间和+极差 f[i]=min(f[k]+cost(k+1,i)+sum[n]-sum[i]) (k∈[0,k] and sum[i]-sum[k]<=W) 这样直接转移是O(n^2)的,下面考虑删除一些没用的决策k，类似单调队列的做法 (但不是队头最优),当然真正的大哥直接线段树维护了将上述方程化简得 f[i]=min(f[k]-sum[k]+Range(k+1,i))+sum[n] k∈[0,i] 仔细观察上方程，当i增加时我们发现，k的取值下界可能会增大，因为sum[i]-sum[k]>W 时不符合条件这样就可以排除一些没用的k。此外对于一组数据，有Range(k+1,x)>=Range(i+1,x) 其中k<i x>=i+1 因为Range表示的是一组数据的极差，这个结论是很显然的下面我们来看看f[k]-sum[k]，当i增加时，k可以取到i了，那么如果之前k<i的f[k]-sum[k]>=f[i]-sum[i] 由上述两个不等式可得f[k]-sum[k]+Range(k+1,x)>=f[i]-sum[i]+Range(i+1,x) 其中x>=i+1 这个时候不如取k=i的时候优秀，所以应当抛弃但f[k]-sum[k]<f[i]-sum[i]时就不知道了我们无法利用不等式基本定理来得到 f[k]-sum[k]+Range(k+1,x)与f[i]-sum[i]+Range(i+1,x)的关系其中x>=i+1 所以仍然需要枚举这些K值来看看哪个最小，但是此时的K已经很少了，枚举起来很快所以每次新增加一个i，就可以抛弃之前f[k]-sum[k]>=f[i]-sum[i]的无用k值所以可以创建一个单调队列，这里面的k值满足f[k]-sum[k]单调递增这样排除的时候就可以从右边一个个排除了代码：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=41588931

送花回复

发布于 2019-11-04 20:53

dz_ice

C++

强烈建议造强一点的数据重测！！

送花回复

发布于 2019-11-02 22:21

Nanjoko.

电气工程师

类比 day 1，强烈建议出题人首先保证数据正确性和强度。赛后弥补的话，依然会引起不管是骗到分的还是没骗到的选手的普遍不满。

送花回复

发布于 2019-11-02 22:33