【2018SCUACM FurtherTraining 25 分治】

题目来源

A:HDU1231

B:UVA1411

C:UVA1605

D:UVA12097

解题报告

A:经典动态规划问题,以\(maxSum[i]\)表示以\(a[i]\)为右边界的最大连续子序列和,显然\((maxSum[i]=max(maxSum[i-1]+a[i],a[i])\),更新答案的同时记录一下序列起点即可。

B:二分图最小权完备匹配。对于一个四边形\(ABCD\)(\(AC\),\(BD\)是对角线),其每条边的边长取端点之间的欧几里得距离,则一定有\(AC+BD>AD+BC\)且\(AC+BD>AB+DC\),即:交叉的边长之和总是最大的。题目要求点全部配对,并且线之间不交叉,于是对任意两黑点、两白点组成的四边形,一共有两种方案可选,我们总是取边权之和最小的那种配对方案,这种方案一定不是交叉的方案,问题转化为二分图最小权完备匹配,用费用流即可解决,最后看一下哪些边满流了,就是配对方案。

PS:本题网上大多数都是\(KM\)算法解的,有机会可以去学一学。

费用流建模方法见:https://www.byvoid.com/zhs/blog/match-km

C:思维题,要使得任意两个国家相邻,直观地想到对每一个国家,先给它摆好一排\(n\)个,然后从左至右在每一块上边叠一个不同的国家,对每个国家都这么干就行了。于是我们可以得出答案:摆两层,第一层\(n\)行,每行\(n\)个全部摆同一个国家;第二层\(n\)列,每列\(n\)个全部摆同一个国家。

 

D:二分答案,不断二分最大面积\(x\),看能不能能凑齐\(F+1\)块就行。

PS:被精度卡到自闭,pi最好取\(acos(-1)\)……

 

stdKonjac

stdKonjac

一只挣扎的蒟蒻ACMer

评论太激烈有些评论需要亲动动手指翻页

留下你的评论

*评论支持代码高亮<pre class="prettyprint linenums">代码</pre>

*