BZOJ 2510 弱题
有M个球,一开始每个球均有一个初始标号,标号范围为1~N且为整数,标号为i的球有ai个,并保证Σai = M。 每次操作等概率取出一个球(即取出每个球的概率均为1/M),若这个球标号为k(k < N),则将它重新标号为k + 1;若这个球标号为N,则将其重标号为1。(取出球后并不将其丢弃) 现在你需要求出,经过K次这样的操作后,每个标号的球的期望个数。
788 字
|
4 分钟
[NOIP2011] 玛雅游戏
Mayan puzzle 是最近流行起来的一个游戏。游戏界面是一个7 行5 列的棋盘,上面堆放着一些方块,方块不能悬空堆放,即方块必须放在最下面一行,或者放在其他方块之上。游戏通关是指在规定的步数内消除所有的方块,消除方块的规则如下:
1755 字
|
9 分钟
BZOJ 2090 [Poi2010] Monotonicity 2
给出N个正整数a[1..N],再给出K个关系符号(>、<或=)s[1..k]。 选出一个长度为L的子序列(不要求连续),要求这个子序列的第i项和第i+1项的的大小关系为s[(i-1)mod K+1]。 求出L的最大值。
525 字
|
3 分钟
BZOJ 2438 [中山市选2011] 杀人游戏
一位冷血的杀手潜入 Na-wiat,并假装成平民。警察希望能在 N 个人里面, 查出谁是杀手。 警察能够对每一个人进行查证,假如查证的对象是平民,他会告诉警察,他 认识的人, 谁是杀手, 谁是平民。 假如查证的对象是杀手, 杀手将会把警察干掉。 现在警察掌握了每一个人认识谁。 每一个人都有可能是杀手,可看作他们是杀手的概率是相同的。 问:根据最优的情况,保证警察自身安全并知道谁是杀手的概率最大是多 少?
664 字
|
3 分钟
COGS 1752 [BOI2007] 摩基亚Mokia
摩尔瓦多的移动电话公司摩基亚(Mokia)设计出了一种新的用户定位系统。和其他的定位系统一样,它能够迅速回答任何形如“用户C的位置在哪?”的问题,精确到毫米。但其真正高科技之处在于,它能够回答形如“给定区域内有多少名用户?”的问题。
863 字
|
4 分钟
COGS 2235 烤鸡翅
在焦作太行路上,有一家烤鸡翅的生意火爆。因为好吃,所以卖的特别好。排队的人就特别多,经常有很多人买不到鸡翅。 鸡翅会在每分钟烤出Xi个,每分钟也只会卖给一个客人,第i个客人需要买Yi个。因为生意火爆,老板可以选择在这分钟不卖给这个客人鸡翅,或者卖给这个顾客他需要的鸡翅, 如果现在剩余的鸡翅不够,那就肯定不能卖给这个客人。无论这个客人能否买到鸡翅,他必须离开队伍。 现在给定N分钟,且已经知道每分钟烤出的鸡翅个数Xi,也知道每个客人需要鸡翅的Yi个数,现在老板想知道,如何合理安排卖给与拒绝,最多可以满足多少人
558 字
|
3 分钟
BZOJ 3668 [NOI2014] 起床困难综合症
21 世纪,许多人得了一种奇怪的病:起床困难综合症,其临床表现为:起床难,起床后精神不佳。作为一名青春阳光好少年,atm 一直坚持与起床困难综合症作斗争。通过研究相关文献,他找到了该病的发病原因:在深邃的太平洋海底中,出现了一条名为 drd 的巨龙,它掌握着睡眠之精髓,能随意延长大家的睡眠时间。正是由于 drd 的活动,起床困难综合症愈演愈烈,以惊人的速度在世界上传播。为了彻底消灭这种病,atm 决定前往海底,消灭这条恶龙。历经千辛万苦,atm 终于来到了 drd 所在的地方,准备与其展开艰苦卓绝的战斗。drd 有着十分特殊的技能,他的防御战线能够使用一定的运算来改变他受到的伤害。具体说来,drd 的防御战线由 n扇防御门组成。每扇防御门包括一个运算op和一个参数t,其中运算一定是OR,XOR,AND中的一种,参数则一定为非负整数。如果还未通过防御门时攻击力为x,则其通过这扇防御门后攻击力将变为x op t。最终drd 受到的伤害为对方初始攻击力x依次经过所有n扇防御门后转变得到的攻击力。由于atm水平有限,他的初始攻击力只能为0到m之间的一个整数(即他的初始攻击力只能在0,1,…,m中任选,但在通过防御门之后的攻击力不受 m的限制)。为了节省体力,他希望通过选择合适的初始攻击力使得他的攻击能让 drd 受到最大的伤害,请你帮他计算一下,他的一次攻击最多能使 drd 受到多少伤害。
1348 字
|
7 分钟
COGS 2421 简单的Treap
Treap是一种平衡二叉搜索树,除二叉搜索树的基本性质外,Treap还满足一个性质: 每个节点都有一个确定的优先级,且每个节点的优先级都比它的两个儿子小(即它的优先级满足堆性质)。 不难证明在节点的优先级都事先给定且互不相同时,对应的Treap有且仅有一个。 现在,给定n个数和每个数对应的优先级,求出对应的以数的大小作为二叉搜索树比较依据的Treap的先序遍历结果。 对先序遍历的定义是:先访问根节点,再访问左子树,最后访问右子树。
642 字
|
3 分钟