【2018SCUACM FurtherTraining 24 贪心】

题目来源

A:UVA11054

B:UVA11491

C:UVA311

D:UVA1149

E:UVA1615

F:UVA11212

G:UVA12325

解题报告

A:类似于NOIP提高组2002的均分纸牌,不论是售酒,还是拿酒,最终到第\(i\)个点至少要花费\(abs(a[i])\)的代价,我们从左往右考虑,如果一个点\(i\)要出售\(a[i]\)单位的酒,我们就把它直接全部卖给它右边相邻的那个点(后续那个点再来处理剩下的酒);如果它需要\(a[i]\)单位的酒,我们就直接从相邻点拿\(a[i]\)单位的酒来(不用管够不够拿,不够的相当于是从更远的地方拿来的,如果不够相邻点的酒库存会变成负的,相当于更远的地方需要运这么多酒给它,答案是不变的)。因此,不论如何操作,相邻点的酒库存都会加上\(a[i]\),而总代价则会加上\(abs(a[i])\),从左往右扫一遍就行了。

B:设总数字个数为\(N\),需要删除\(D\)个数字,相当于留下\(E=N-D\)个数字,而要使数字最大,则就是从左往右连续选\(E\)个最大的数字就行了。

考虑到时间复杂度,每次去扫一遍未选的数字来找最大的复杂度会达到\(O(n^2)\),肯定是不行的。注意到我们只关注每个位置后的某一位数字\(k\)最早出现在哪,因此可以用\(next[i][k]\)表示位置\(i\)以后的数字\(k\)最早出现的位置。可以扫一遍记录每个数字的出现位置,然后对于每个数字\(x\),在它的出现位置\(i\)和下一个出现位置\(j\)之间的位置\(k\),\(next[k][x]=j\),\(next\)数组可在\(O(10n)\)的时间内求出,之后我们只需要保证对于位置\(i\),\(next[i][k]\)的\(k\)尽量大且选完之后还能留足位置选够\(E\)位即可。

C:思路不难,\(4×4\),\(5×5\),\(6×6\)的产品都得单独占一个箱子,剩下的就是尽可能多装并且尽可能先装大的。我们用\(Size[k]\)表示\(k×k\)的产品个数。

\(6×6\)的最简单,就能装它一个,答案增加\(Size[6]\)就行了

\(5×5\)的最多搭配11个\(1×1\)的箱子,答案增加\(Size[5]\)的同时\(Size[1]\)相应减少

\(4×4\)的优先搭配\(2×2\)的箱子,最多6个,不足再用\(1×1\)的去补,然后\(Size[2]\)和\(Size[1]\)相应减少

\(3×3\)的情况最复杂,要分成直接用4个填,或者是配合\(1×1\)与\(2×2\)的一起填的情况,而且1、2、3、4个\(3×3\)每个的最佳填法都不一样,要仔细画图,还要判定最佳填法填的时候诸如\(2×2\)不够了的情况

\(2×2\)的优先放满9个,不足的用\(1×1\)的去填

\(1×1\)的直接放就行了

D:既然一个箱子最多能装两件物品,自然是尽可能装两件。于是可以将物品重量排序,先选最重的,然后剩余空间找尽量重的塞进去,找不到就只有它独自占一个箱子了。注意到排序过后,从重到轻枚举,对于每一个当前最重,它对应的可以塞进去的最轻的物品的重量一定是单调递增的(因为上一个更重的选了更轻的配合装入),所以我们直接使用双指针法,head指向最轻,tail指向最重,然后两个指针一直往中心移动就可以了。

E:对于每个点,画个圆,找出交点\(A,B\),于是题目转变为\([A,B]\)内要修一个出口。整个题目就是要求在\([0,L]\)内使用一些点让要求的一些区间每个区间内都至少有一个点,简单的区间覆盖问题,将线段按照右端点小,左端点大的排序方式排序,这样小的区间一定排在前面(比如\([5,10]\)就排在\([3,10]\)前面),注意到这时就不用去判断区间包含了,因为小区间肯定先处理。至于每次选哪个点呢?答案是最右边的点,因为这样能尽量让后面的区间覆盖到。线性扫一遍线段,如果未覆盖,就使用这个线段的右端点,因为这个未覆盖线段一定是未覆盖的线段中最小的,如此往复直至全部覆盖完即可。

F:\(IDA*\)解题。定义一个“有正确后继”的数字为:它后面的那个数比它大1。则当所有数字都有正确后继时搜索完毕。

注意到对于四个数\(a\ b\ c\ d\),每次最多改变3个后继,比如改成\(a\ b\ d\ c\),\(b,d,c\)三个数的后继改变了,也就是说我们一次剪切+粘贴最多能让三个数字变得正确,因此不难得到估价函数:若剩余还能搜索的层数*3\(<\)当前层的错误数字数,那么无论如何在给定的最大深度都无法得解,直接返回即可。

具体搜索时,可枚举剪切的区间,再在剩余的字符里枚举粘贴点,模拟粘贴过程即可。

 

G:枚举+优化。

注意到物品1最多选\(N\div S_1\)个,物品2最多选\(N\div S_2\)个,令\(A=N\div S_1\),\(B=N\div S_2\)。

当\(A\)在可接受的枚举范围内时,枚举物品1,从\(0\)到\(A\)即可求得答案。

当\(B\)在可接受的枚举范围内时,枚举物品2,从\(0\)到\(B\)即可求得答案。

当\(A\)和\(B\)都不在可接受的枚举范围内时,\(S_1\)与\(S_2\)一定都很小,此时考虑选\(S_2\)个物品1和\(S_1\)个物品2,如果\(S_2*V_1\ge S_1*V_2\),则物品2不可能选大于等于\(S_1\)个,否则可以用\(S_2\)个物品1替换且价值更优,直接从\(0\)到\(S_1\)枚举物品2即可;反之从\(0\)到\(S_2\)枚举物品1即可。

 

stdKonjac

stdKonjac

一只挣扎的蒟蒻ACMer

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

留下你的评论

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

*