【2018SCUACM Wednesday 5 Greedy】

题目来源

A:CodeForces 1040B

B:CodeForces 1019A

C:CodeForces 1015E1

D:CodeForces 1042C

E:CodeForces 1028D

解题报告

A:按照贪心的思路,从第一个点开始,每隔\(2k+1\)个点作为转动点,这样能保证没有肉会被重复转动。最后一定会剩下x个点没被转动且满足\(0\le x<k\)。我们将这\(x\)个点作为偏移量,将每个转动点往右边移动\(x\)即可。

B:先判断是否有党派原票数大于第一个党派的票数,如果没有,直接输出\(0\)就行。如果有,则枚举最终获胜票数\(x\),则最多剩下\(n-x\)个人保留原始投票,且每个其它党派最多拥有\(x-1\)张票。这\(n-x\)个人当然贿赂费越贵越好。所以首先不论党派,按照贿赂费从高到低排序。然后枚举每个人,如果这个人不是党派\(1\)的人,有两种情况:

①如果保留的人已经到\(n-x\)个人了,那不管直接贿赂他。

②如果保留的人还没有到\(n-x\)个人:

I.如果当前枚举的第\(k\)人所在党派票数还没有到\(x-1\),则让它保留原始投票,党派票数+1,剩余保留人数-1。

II.如果当前枚举的第\(k\)人所在党派票数已经到\(x-1\)了,那直接贿赂他。

枚举完每个\(x\)后用当前方案的\(cost\)与最低\(cost\)比较即可,如果小就更新最低\(cost\)。

注意:本题数据较大,需要用long long。

PS:一开始scanf和cin混用了,然后关了ios同步,结果疯狂WA…原来scanf和cin混用的时候不能关ios同步呀,缓冲区会乱,学习了……

 

C:大暴力,枚举除最外层之外的每个点,对于每个星星的中心点,找到它的最大半径并记录即可。注意本题样例坑人!样例下面的Note才是正解,样例将\(3,5\)这颗星记录作了半径分别为1和2的两颗星,在数据小的情况下这是没有问题的。但是注意题目说了星星数量不超过\(n*m\)!如果同一个中心被算作很多颗星星,最终答案是会超出\(n*m\)的!(然后就会WA on test 16)所以我们必须只记录最大半径的星星。记录的同时记得标记格子,最后判断是否全覆盖。

D:如果不看符号只看每个数的绝对值的话,显然只要存在非零的数\(x\),则答案就是这些数\(x\)的乘积,由于题目只要求一种解,所以不用管1操作的顺序。举个例子,比如5 8 2 1 3,无论怎么进行1操作,最后的答案总是\(5*8*2*1*3\)。

但是这道题存在负数和\(0\)。先来考虑负数吧,如果负数的数量是偶数,则不会影响答案,还是拿绝对值是5 8 2 1 3这个举例,无论是-5 -8 2 1 3还是-5 8 -2 1 3亦或是-5 -8 -2 -1 3都不会影响答案,因为负负得正,只要是偶数个负数,最后都会变成正数。

如果是奇数个负数怎么办呢?其实也很简单,删掉所有负数中绝对值最小,也就是最大的负数就可以了(稍后讨论用操作1还是操作2删除),比如-3 -2 -1,显然删掉-1后留下来的两个数-3和-2乘积为6是最大的。

再来考虑0,显然只要乘上0答案就会变成0。所以我们需要考虑答案真的是0和不是0的情况。

①答案是0的情况:显然,只有一个负数其余全0或者全部是0会导致最后的答案是0。其中:

I.如果只有一个负数其余全0,就用任意一个0通过操作1去消掉这个负数,然后所有0依次通过操作1消去,直到剩下最后一个0。

II.如果全是0,就通过操作1依次消去0,直到剩下最后一个0。

②答案不是0的情况:有两个以上绝对值非0的数存在即可。其中:

I.若负数是奇数个,找出最大的负数(其绝对值最小),若有0,则通过0消去它,然后通过操作1依次消去所有0,最后一个0通过操作2消去,剩余的数依次通过操作1消去即可。若无0,则直接通过操作2消去这个负数,再通过操作1消去剩余数字。

II.若负数是偶数个,不影响答案。若有多个0,消去到只剩下一个0,再通过操作2消去最后的0;如果只有一个0,直接操作2消去这个0,剩余数通过操作1消去。

 

E:这道题跟贪心有半毛钱关系呀……这道题相当于一个序列\(S\),需要找到一个分界点让左边的数全小于右边的数,并且满足题目中的条件。题目给的条件初读有点复杂,我们来慢慢理一下思路:

首先明确一下前提:不会出现重复元素\(x\)。

①如果这是一个\(Add\)操作:

我们假定已经知道了最大的\(buy\)和最小的\(sell\),那么如果\(Add\)的这个元素\(x\)小于最大的\(buy\),根据题目它一定是\(buy\);同理,如果这个元素\(x\)大于最小的\(sell\),它一定是一个\(sell\) ;如果它在最大的\(buy\)和最小的\(sell\)之间,在下一个\(Accept\)操作前它的属性是不能确定的,我们称其为“自由数”吧。

②如果这是一个\(Accept\)操作:

如果它操作的元素\(x\)属于\(sell\),由于这个\(x\)一定是\(sell\)中最小的(我们假定这个\(Accept\)合法),所以只要是大于\(x\)的元素都一定是\(sell\)。

同理,如果它操作的元素\(x\)属于\(buy\),由于这个\(x\)一定是\(buy\)中最大的,所以只要是小于\(x\)的元素都一定是\(buy\)。

因此不难看出,只要出现了一个\(Accept\)操作,除了它自身之外的所有\(Add\)操作添加的元素的属性都可以确认。

再来观察,如果这个\(Accept\)操作的是一个\(buy\)属性的元素,那么最小的\(sell\)不变,为大于这个\(buy\)的第一个元素;最大的\(buy\)变为小于这个\(buy\)的第一个元素。

如果这个\(Accept\)操作的是一个\(sell\)属性的元素,那么最大的\(buy\)不变,为小于这个\(sell\)的第一个元素;最小的\(sell\)变为大于这个\(sell\)的第一个元素。

其实这两种情况可以合并讨论,我们假设序列按从小到大排的三个元素分别是\(a_i\),\(a_j\),\(a_k\),\(a_i<a_j<ak\),如果\(Accept\)操作的是\(a_j\),那么最大的\(buy\)就是\(a_i\),最小的\(sell\)就是\(a_k\)。

那个怎么判断\(Accept\)合法不合法呢?

其实也很简单啦,在上一个\(Accept\)操作后我们已经确定了当前最大的\(buy\)和最小的\(sell\),如果这个\(Accpet\)操作的元素小于最大的\(buy\)或大于最小的\(sell\),显然它就是不合法的。

如果这个\(Accept\)操作的刚好是最大的\(buy\)或最小的\(sell\),那操作的元素的属性已经确定了,答案不变。

如果这个\(Accept\)操作的是最大的\(buy\)和最小的\(sell\)之间的元素(也就是上一个\(Accept\)到这个\(Accept\)之间通过\(Add\)添加的元素之一),那么这个元素的属性可以随便选。

举个例子,上次的最大\(buy\)为5,最小\(sell\)为8,中途添加进来一个\(7\),然后\(Accept\)操作的正是这个7,那么无论是\(buy 5\) \(buy 7\) \(sell 8\)还是\(buy 5\) \(sell 7\) \(sell 8\)都是合法的。

因此,这种情况下答案应该乘2。

但是还有一点需要考虑,最后一个\(Accept\)之后的元素怎么办?这些元素如果落在最后的最大的\(buy\)和最小的\(sell\)之间时,它们属性是不能确定的,也就是前文说的“自由数”。其实处理起来也很简单啦,既然没有\(Accept\)的限制,那么这些元素(假定有n个这样的元素)的属性可以是:

全部是\(sell\)

第一个是\(buy\),剩下全是\(sell\)

第一、二个是\(buy\),剩下全是\(sell\)

全部是\(buy\)

共有\(n+1\)种情况,所以答案乘上\(n+1\)即可。

综上,理一理思路,代码慢慢的就出来啦:

 

 

 

stdKonjac

stdKonjac

一只挣扎的蒟蒻ACMer

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

留下你的评论

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

*