JAG Spring Contest 2015

提交地址

Overview:

做 ASC 42 的 B 题的时候遇到的问题。。。ASC 42 的题目是:
初始有 m 元钱,目标是恰好拥有 n 元钱
每轮你可以压至多当前你所拥有的钱数进行赌博,p 的概率翻倍,q 的概率失去赌注。
至多进行 t 个回合,问最优策略下达到目标的概率。
(t <= 300, p < 50。)

YY 了一下结论,假设当前有 m 元钱,每次压 min(m, n-m) 就可以了。
加之题目限制很强,模拟 DP 一下就出来了。在 camp 群里遂问了一下 p >= 50 的情况下结论还成立吗。。
果然有完整版的题目。

ゆっくり読んでください ...

ZOJ 2126. Rocket Mania

http://acm.bnu.edu.cn/v3/problem_show.php?pid=15645
http://cojs.tk/cogs/problem/problem.php?pid=1514

Brief description:

疯狂火箭(Rocket Mania)是幻想游戏系列中我最喜欢的游戏之一。在这个游戏中,左边有一些火柴,右边有一些火箭。在中间,有许多种类的带有导火索的格子。这些导火索可以被旋转0,90,180或270度。为了发射火箭,必须用导火索形成一条从火柴到火箭的连续通道。当一条完整的通路建立的时候,连接着火柴的所有火箭都将被发射。

你的任务是,给出初始情况,旋转一些导火索,使点燃某一根火柴后,发射的火箭数量尽量多。

ゆっくり読んでください ...

BZOJ 1435. [ZJOI2009]多米诺骨牌

Brief description:

给定一个 n×m 的矩形表格,其中有一些位置有障碍。现在要在这个表格内放一些 1×2 或者 2×1 的多米诺骨牌,使得任何两个多米诺骨牌没有重叠部分,任何一个骨牌不能放到障碍上。
并且满足任何相邻两行之间都有至少一个骨牌横跨,任何相邻两列之间也都至少有一个骨牌横跨。求有多少种不同的放置方法,注意你并不需要放满所有没有障碍的格子。

ゆっくり読んでください ...