Krydom: 暁の水平线に胜利を刻むのです

ソロモンの悪夢、見せてあげる!

@krydom12月前

07/16
14:28
模拟

[bzoj 2548] [Ctsc2002]灭鼠行动

♦♦♦♦♦♦   Description   ♦♦♦♦♦♦

 最近,有一些繁殖力很强的老鼠在下水道非常猖獗,灭鼠特工队正在计划消灭这些老鼠。下水道只有东西方向和南北方向的管道,如图所示。
1(5)

灭鼠特工队的队员拥有强大的武器。他们将在某些时刻t在某些位置(x,y)放置武器。他们所使用的武器包括:

  1. 强力炸弹:它的攻击范围限定在管道内部,是沿竖直和水平方向,离(x,y)的距离不超过L的区域,但是不能穿透下水道壁。它将在放置之后立刻爆炸,且攻击范围内的老鼠将被全部炸死。
  2. 神秘射线:它的攻击范围是以(x,y)为圆心,半径为R的圆,而且可以穿透下水道壁。射线在时刻t施放后,将使攻击范围内的所有老鼠立刻陷入昏迷状态,失去知觉,停止一切生理活动,待到第t+3时刻才能恢复(保持失去知觉前的朝向)。如果在昏迷状态中再次受到射线攻击,那么它将再推迟3个时刻恢复。例如,若老鼠在时刻t和时刻t+1个受到一次射线的攻击,则它要昏迷到第t+3+3时刻才能恢复知觉。恢复知觉以后,老鼠将继续以前的生理活动。
  3. 定时炸弹:它的攻击范围仅包括(x,y)。它在时刻t放置后,将在第t+3时刻爆炸,爆炸时处在(x,y)点的老鼠将全部被炸死。
  4. 生物炸弹:它的攻击范围仅包括(x,y)。它将在放置之后立刻爆炸,使处在(x,y)点的所有老鼠的性别改变(无论大小,雌变成雄,雄变成雌),但不影响老鼠的正常生理活动。

虽然特工队的实力很强,但是老鼠的实力也不容忽视。

我们定义,相邻两个时刻之间是一个时间单位。从t=0时刻开始,每只老鼠就从初始位置向某一初始方向运动。只要前方有管道,如上图中沿方向N到达点A,老鼠就会一直向前走,运动速度为1。否则,如果只有左边或者只有右边有管道,如上图中沿方向E到达点B时,再不能沿原方向继续前进,它就会花费一个时间单位朝该方向原地转动90度,即它将改变方向朝向S。如果它左边和右边都有管道,如上图中沿方向W到达点C,老鼠会回忆这是第几次处于这种情况。如果是第奇数次遇到,它会向左转,第偶数次就向右转。如果它处于一条死路的尽头,如上图中沿方向W到达点D,那么它会花费两个时间单位连续向右转两次,即它将改变方向朝向E。

如果在t时刻某点恰好只有两只老鼠,一只为成年雄老鼠,一只为成年雌老鼠,则它们将会因为进行繁殖而在该点停留两个单位时间,t+2时刻会在该点对每个有管道的方向生出一只朝着该方向的小老鼠,南北方向为雄小老鼠,东西方向为雌小老鼠。如上图中的C点,t时刻恰好只有两只老鼠,它们都已成年且性别相异,那么在第t+2时刻就会在该点生出三只小老鼠,它们分别朝向N、S、E,性别分别是雄性、雄性、雌性。小老鼠一出生就立刻开始移动,而成年老鼠需要再休息一个时间单位,即在t+3时刻继续活动(两只老鼠都保持生育前的朝向)。小老鼠需要成长5个时间单位才会长成为成年老鼠。

特工队现在制定了一套灭鼠计划,其中包括在下水管道放置武器的位置、时间和类型。你需要帮他们计算灭鼠行动的效果,如果在该计划实施的过程中,老鼠的数量超过了某个限定值,就会爆发鼠疫。

Read More →

[bzoj 2548] [Ctsc2002]灭鼠行动

@krydom12月前

07/16
08:48
模拟 贪心

[bzoj 3709] [PA2014]Bohater

♦♦♦♦♦♦   Description   ♦♦♦♦♦♦

 在一款电脑游戏中,你需要打败n只怪物(从1到n编号)。为了打败第i只怪物,你需要消耗d[i]点生命值,但怪物死后会掉落血药,使你恢复a[i]点生命值。任何时候你的生命值都不能降到0(或0以下)。请问是否存在一种打怪顺序,使得你可以打完这n只怪物而不死掉

Read More →

[bzoj 3709] [PA2014]Bohater

@krydom12月前

07/16
08:25
模拟

[bzoj 1216] [HNOI2003]操作系统

♦♦♦♦♦♦   Description   ♦♦♦♦♦♦

 写一个程序来模拟操作系统的进程调度。假设该系统只有一个CPU,每一个进程的到达时间,执行时间和运行优先级都是已知的。其中运行优先级用自然数表示,数字越大,则优先级越高。如果一个进程到达的时候CPU是空闲的,则它会一直占用CPU直到该进程结束。除非在这个过程中,有一个比它优先级高的进程要运行。在这种情况下,这个新的(优先级更高的)进程会占用CPU,而老的只有等待。如果一个进程到达时,CPU正在处理一个比它优先级高或优先级相同的进程,则这个(新到达的)进程必须等待。一旦CPU空闲,如果此时有进程在等待,则选择优先级最高的先运行。如果有多个优先级最高的进程,则选择到达时间最早的。

Read More →

[bzoj 1216] [HNOI2003]操作系统

@krydom12月前

07/15
20:07
模拟

[bzoj 1033] [ZJOI2008]杀蚂蚁antbuster

♦♦♦♦♦♦   Description   ♦♦♦♦♦♦

 最近,佳佳迷上了一款好玩的小游戏:antbuster。游戏规则非常简单:在一张地图上,左上角是蚂蚁窝,右下角是蛋糕,蚂蚁会源源不断地从窝里爬出来,试图把蛋糕搬回蚂蚁窝。而你的任务,就是用原始资金以及杀蚂蚁获得的奖金造防御塔,杀掉这些试图跟你抢蛋糕的蚂蚁~下附一张游戏截图:
1
  为了拿到尽可能高的分数,佳佳设计了很多种造塔的方案,但在尝试了其中的一小部分后,佳佳发现,这个游戏实在是太费时间了。为了节省时间,佳佳决定写个程序,对于每一种方案,模拟游戏进程,根据效果来判断方案的优劣。根据自己在游戏中积累的一些经验,以及上网搜到的一些参数,佳佳猜了蚂蚁爬行的算法,并且假设游戏中的蚂蚁也是按这个规则选择路线:1、每一秒钟开始的时候,蚂蚁都在平面中的某个整点上。如果蚂蚁没有扛着蛋糕,它会在该点留下2单位的信息素,否则它会留下5单位的信息素。然后蚂蚁会在正北、正南、正东、正西四个方向中选择一个爬过去。2、选择方向的规则是:首先,爬完一个单位长度后到达的那个点上,不能有其他蚂蚁或是防御塔,并且那个点不能是蚂蚁上一秒所在的点(除非上一个时刻蚂蚁就被卡住,且这个时刻它仍无法动),当然,蚂蚁也不会爬出地图的边界(我们定义这些点为不可达点)。如果此时有多个选择,蚂蚁会选择信息素最多的那个点爬过去。3、如果此时仍有多种选择,蚂蚁先面向正东,如果正东不是可选择的某个方向,它会顺时针转90°,再次判断,如果还不是,再转90°...直到找到可以去的方向。4、如果将每只蚂蚁在洞口出现的时间作为它的活动时间的第1秒,那么每当这只蚂蚁的活动时间秒数为5的倍数的时候,它先按规则1~3确定一个方向,面对该方向后逆时针转90°,若它沿当前方向会走到一个不可达点,它会不停地每次逆时针转90°,直到它面对着一个可达的点,这样定下的方向才是蚂蚁最终要爬去的方向。5、如果蚂蚁的四周都是不可达点,那么蚂蚁在这一秒内会选择停留在当前点。下一秒判断移动方向时,它上一秒所在点为其当前停留的点。6、你可以认为蚂蚁在选定方向后,瞬间移动到它的目标点,这一秒钟剩下的时间里,它就停留在目标点。7、蚂蚁按出生的顺序移动,出生得比较早的蚂蚁先移动。然后,是一些有关地图的信息:1、 每一秒,地图所有点上的信息素会损失1单位,如果那个点上有信息素的话。2、 地图上某些地方是炮台。炮台的坐标在输入中给出。3、 地图的长、宽在输入中给出,对于n * m的地图,它的左上角坐标为(0,0),右下角坐标为(n,m)。蚂蚁洞的位置为(0,0),蛋糕的位置为(n,m)。4、 你可以把蚂蚁看做一个直径为1单位的圆,圆心位于蚂蚁所在的整点。5、 游戏开始时,地图上没有蚂蚁,每个点上的信息素含量均为0。一些有关炮塔的信息:1、 炮塔被放置在地图上的整点处。2、 为了简单一些,我们认为这些炮塔都是激光塔。激光塔的射速是1秒/次,它的攻击伤害为d/次,攻击范围为r。你可以认为每秒蚂蚁移动完毕后,塔才开始攻击。并且,只有当代表蚂蚁的圆的圆心与塔的直线距离不超过r时,塔才算打得到那只蚂蚁。3、 如果一只蚂蚁扛着蛋糕,那么它会成为target,也就是说,任何打得到它的塔的炮口都会对准它。如果蛋糕好好地呆在原位,那么每个塔都会挑离它最近的蚂蚁进行攻击,如果有多只蚂蚁,它会选出生较早的一只。4、 激光塔有个比较奇怪的特性:它在选定了打击目标后,只要目标在其射程内,塔到目标蚂蚁圆心的连线上的所有蚂蚁(这里“被打到”的判定变成了表示激光的线段与表示蚂蚁的圆有公共点)都会被打到并损d格血,但激光不会穿透它的打击目标打到后面的蚂蚁。5、 尽管在真实游戏中,塔是可以升级的,但在这里我们认为塔的布局和等级就此定了下来,不再变动。再介绍一下蚂蚁窝:1、 如果地图上的蚂蚁不足6只,并且洞口没有蚂蚁,那么窝中每秒会爬出一只蚂蚁,直到地图上的蚂蚁数为6只。2、 刚出生的蚂蚁站在洞口。3、 每只蚂蚁有一个级别,级别决定了蚂蚁的血量,级别为k的蚂蚁的血量为int(4*1.1^k)(int(x)表示对x取下整)。每被塔打一次,蚂蚁的血减少d。注意,血量为0的蚂蚁仍能精力充沛地四处乱爬,只有一只蚂蚁的血被打成负数时,它才算挂了。 4、 蚂蚁的级别是这样算的:前6只出生的蚂蚁是1级,第7~12只是2级,依此类推。最后给出关于蛋糕的介绍:1、 简单起见,你可以认为此时只剩最后一块蛋糕了。如果有蚂蚁走到蛋糕的位置,并且此时蛋糕没有被扛走,那么这只蚂蚁就扛上了蛋糕。蚂蚁被打死后蛋糕归位。2、 如果一只扛着蛋糕的蚂蚁走到蚂蚁窝的位置,我们就认为蚂蚁成功抢到了蛋糕,游戏结束。3、 蚂蚁扛上蛋糕时,血量会增加int(该蚂蚁出生时血量 / 2),但不会超过上限。整理一下1秒钟内发生的事件: 1秒的最初,如果地图上蚂蚁数不足6,一只蚂蚁就会在洞口出生。接着,蚂蚁们在自己所在点留下一些信息素后,考虑移动。先出生的蚂蚁先移动。移动完毕后,如果有蚂蚁在蛋糕的位置上并且蛋糕没被拿走,它把蛋糕扛上,血量增加,并在这时被所有塔设成target。然后所有塔同时开始攻击。如果攻击结束后那只扛着蛋糕的蚂蚁挂了,蛋糕瞬间归位。攻击结束后,如果发现扛蛋糕的蚂蚁没死并在窝的位置,就认为蚂蚁抢到了蛋糕。游戏也在此时结束。最后,地图上所有点的信息素损失1单位。所有蚂蚁的年龄加1。漫长的1秒到此结束。

Read More →

[bzoj 1033] [ZJOI2008]杀蚂蚁antbuster

@krydom1年前

01/10
13:57
模拟

[bzoj 1689] Usaco2005Open Muddy roads 泥泞的路

00:00/00:00

♦♦♦♦♦♦   Description   ♦♦♦♦♦♦

Farmer John has a problem: the dirt road from his farm to town has suffered in the recent rainstorms and now contains (1 <= N <= 10,000) mud pools. Farmer John has a collection of wooden planks of length L that he can use to bridge these mud pools. He can overlap planks and the ends do not need to be anchored on the ground. However, he must cover each pool completely. Given the mud pools, help FJ figure out the minimum number of planks he needs in order to completely cover all the mud pools. Read More →

[bzoj 1689] Usaco2005Open Muddy roads 泥泞的路

@krydom2年前

12/27
15:14
模拟 贪心

[bzoj 3016] Usaco2012 Nov Clumsy Cows

00:00/00:00

♦♦♦♦♦♦   Description   ♦♦♦♦♦♦

Bessie the cow is trying to type a balanced string of parentheses into her new laptop, but she is sufficiently clumsy (due to her large hooves) that she keeps mis-typing characters. Please help her by computing the minimum number of characters in the string that one must reverse (e.g., changing a left parenthesis to a right parenthesis, or vice versa) so that the string would become balanced. There are several ways to define what it means for a string of parentheses to be "balanced". Perhaps the simplest definition is that there must be the same total number of ('s and )'s, and for any prefix of the string, there must be at least as many ('s as )'s. For example, the following strings are all balanced:

Read More →

[bzoj 3016] Usaco2012 Nov Clumsy Cows

@krydom2年前

12/27
14:49
模拟

[bzoj 1088] SCOI2005 扫雷Mine

00:00/00:00

♦♦♦♦♦♦   Description   ♦♦♦♦♦♦

 相信大家都玩过扫雷的游戏。那是在一个n*m的矩阵里面有一些雷,要你根据一些信息找出雷来。万圣节到了,“余”人国流行起了一种简单的扫雷游戏,这个游戏规则和扫雷一样,如果某个格子没有雷,那么它里面的数字表示和它8连通的格子里面雷的数目。现在棋盘是n×2的,第一列里面某些格子是雷,而第二列没有雷,如下图: 由于第一列的雷可能有多种方案满足第二列的数的限制,你的任务即根据第二列的信息确定第一列雷有多少种摆放方案。

Read More →

[bzoj 1088] SCOI2005 扫雷Mine

@krydom2年前

12/27
13:21
暴力 模拟

[bzoj 1028] JSOI2007 麻将

00:00/00:00

♦♦♦♦♦♦   Description   ♦♦♦♦♦♦

 麻将是中国传统的娱乐工具之一。麻将牌的牌可以分为字牌(共有东、南、西、北、中、发、白七种)和序数牌(分为条子、饼子、万子三种花色,每种花色各有一到九的九种牌),每种牌各四张。在麻将中,通常情况下一组和了的牌(即完成的牌)由十四张牌组成。十四张牌中的两张组成对子(即完全相同的两张牌),剩余的十二张组成三张一组的四组,每一组须为顺子(即同花色且序数相连的序数牌,例如条子的三、四、五)或者是刻子(即完全相同的三张牌)。一组听牌的牌是指一组十三张牌,且再加上某一张牌就可以组成和牌。那一张加上的牌可以称为等待牌。  在这里,我们考虑一种特殊的麻将。在这种特殊的麻将里,没有字牌,花色也只有一种。但是,序数不被限制在一到九的范围内,而是在1到n的范围内。同时,也没有每一种牌四张的限制。一组和了的牌由3m + 2张牌组成,其中两张组成对子,其余3m张组成三张一组的m组,每组须为顺子或刻子。现给出一组3m + 1张的牌,要求判断该组牌是否为听牌(即还差一张就可以和牌)。如果是的话,输出所有可能的等待牌。

Read More →

[bzoj 1028] JSOI2007 麻将