标签归档:贪心

[UER #7] 短路

Description

“第七套广播体操,原地踏步——走!”

众所周知,跳蚤们最喜欢每天早起做早操,经常天还没亮就齐刷刷地站在操场做着反复纵跳热热身。跳晚国在研制三星 note7 的时候注意到了这点,于是他们打算让炸弹更快地引爆,这样就可以消灭更多早起的跳蚤。

三星 note7 的主板可以看作是由 (2n+1)×(2n+1)个中继器构成的,某些中继器会有导线连在一起,左上角和右下角的中继器分别连着电源的正负极。

电流流过一根导线的时间可忽略不计,但当电流经过中继器时,会延缓一段时间再从中继器流出。这个时间只跟该中继器本身有关,我们把这段时间的长度称为中继器的延时值。

这些中继器由导线连接围成一个一个的层,同个层的中继器的种类都一样,而不同层的种类都不一样,可以发现总共有 n+1 层。当 n=4时,主板大概长这样:

图1

跳晚们打算再加几根导线将某些中继器连接起来.凭借发达的重工业,他们能生产出无数条导线。但由于主板的限制,他们的导线只能和主板四周的边平行,且其长度只够连接相邻两个中继器。

现在他们想知道,他们改造的三星 note7 的电源正极流出的电流能在多短的时间到达电源负极从而造成短路,这样电池就会释放出巨大的能量摧毁跳蚤国的有生力量了。

请参考输入格式和样例配图来更好地理解题意。

继续阅读

贪心算法小结

写在前面

在信息学竞赛中有一类常用的算法,叫做贪心算法。所谓贪心,即对于当前的每一步决策都考虑选择最优的分支,从而使得整体最优,而对于一个问题划分成N个决策,在每次决策中选择最优的分支所需要的时间可以采用堆、左偏树、优先队列等实现(也有根据决策无需修改,在开始进行一次排序即可),进而将问题的时间复杂度大大缩减为O(NlogN)以内。贪心算法无疑是解决问题比较完美的方法,但他的局限在于无法顾及到全局,由于每次只考虑最优决策的局限性,贪心算法容易走入较差解乃至最差解的深坑中,所以在使用贪心算法前需要有对于算法正确性的严(bao)格(li)证(dui)明(pai)。笔者因为贪心学得不好,所以来补这篇文章,用于给自己做总结,希望高手能够指正文中的错误,不胜感激。

继续阅读

bzoj-USACO除草计划A

我已经做了30/30


继续阅读

[bzoj 4027][HEOI2015] 兔子与樱花

Description

很久很久之前,森林里住着一群兔子。有一天,兔子们突然决定要去看樱花。兔子们所在森林里的樱花树很特殊。樱花树由n个树枝分叉点组成,编号从0到n-1,这n个分叉点由n-1个树枝连接,我们可以把它看成一个有根树结构,其中0号节点是根节点。这个树的每个节点上都会有一些樱花,其中第i个节点有c_i朵樱花。樱花树的每一个节点都有最大的载重m,对于每一个节点i,它的儿子节点的个数和i节点上樱花个数之和不能超过m,即son(i) + c_i <= m,其中son(i)表示i的儿子的个数,如果i为叶子节点,则son(i) = 0

现在兔子们觉得樱花树上节点太多,希望去掉一些节点。当一个节点被去掉之后,这个节点上的樱花和它的儿子节点都被连到删掉节点的父节点上。如果父节点也被删除,那么就会继续向上连接,直到第一个没有被删除的节点为止。
现在兔子们希望计算在不违背最大载重的情况下,最多能删除多少节点。
注意根节点不能被删除,被删除的节点不被计入载重。

继续阅读

[bzoj 2525][Poi2011] Dynamite

Description

The Byteotian Cave is composed of  n chambers and n-1 corridors that connect them. For every pair of chambers there is unique way to move from one of them to another without leaving the cave. Dynamite charges are set up in certain chambers. A fuse is laid along every corridor. In every chamber the fuses from the adjacent corridors meet at one point, and are further connected to the dynamite charge if there is one in the chamber. It takes exactly one unit of time for the fuse between two neighbouring chambers to burn, and the dynamite charge explodes in the instant that fire reaches the chamber it is inside.
We would like to light the fuses in some m chambers (at the joints of fuses) in such a way that all the dynamite charges explode in the shortest time possible since the fuses are lit. Write a program that will determine the minimum such time possible.

继续阅读

[bzoj 1124][POI2008] 枪战

Description

有n个人,每个人手里有一把手枪。一开始所有人都选定一个人瞄准(有可能瞄准自己)。然后他们按某个顺序开枪,且任意时刻只有一个人开枪。因此,对于不同的开枪顺序,最后死的人也不同。

继续阅读