考试总结 模拟$112$

考试过程

在AFO之前终于拿到了一次Rank5

开场T1第一眼天空龙?然后开始死刚T1,发现事情并没有想象中的那么简单

暴力DP不会,只会个搜索,然后开始手玩小点,样例给的很充分

首先发现了当最大值特别大的时候,ans就被两个小的限制住了

不难接着想,另一种情况会不会能做到充分填满呢?

然后写上去就过对拍了,很开心,不过大点写不出来暴力,而且不会证明,感觉并不稳

T2一看找环,就想到了昨天刚刚听zzyy说了怎么topo找环,又很开心

第一次写getchar的读入,根本就不知道回车怎么写,只好写空格,所以最后也没有被卡

T3暴力很好写,写的时候已经飘了,以为230很高了,然后开始各种yy....

写完暴力最后40min就去T1,T2静态查错,T3dp没什么思考

题解

 T1「贪心」

abc升序

可以发现2*(a+b)<=c的情况就是a+b

否则每次一定可以全部填满,即(a+b+c)/3

T2「拓扑」

拓扑找环,注意读入

windos下回车是‘ '  linux 是’ '

T3「DP」

首先正反两遍最短路,跑出来dis[i],表示从i到B+1并返回的距离和

现在只要将前b个分组,每一组中每个点的贡献是dis×(组内元素个数-1)

定义f[i][j]表示考虑到第i个点,已经有了j个组

从小到大排序后,用调整法可证最优解一定是连续的一段

然后可以枚举到了那个点,分的组数和转移点

复杂度O(N^3)

进一步发现段长在减小,所以转移点$in[i-i/j,i)$

原文地址:https://www.cnblogs.com/casun547/p/11844835.html