递推与动规 - Page 6

「CF498B」Name That Tune
ItturnsoutthatyouareagreatfanofrockbandAC/PE.Peterlearnedthatandstartedthefollowinggame:heplaysthefirstsongofthelistofnsongsofthegroup,andyouhavetofindoutthenameofthesong.Afteryoutellthesongname,Peterimmediatelyplaysthefollowingsonginorder,andsoon.Thei-thsongofAC/PEhasitsrecognizabilitypi.Thismeansthatifthesonghasnotyetbeenrecognizedbyyou,youlistentoitforexactlyonemoresecondandwithpr...
12014年12月25日3,625递推与动规,概率与期望

「BZOJ1485」[HNOI2009] 有趣的数列
Description 我们称一个长度为2n的数列是有趣的，当且仅当该数列满足以下三个条件： (1)它是从1到2n共2n个整数的一个排列{ai}； (2)所有的奇数项满足a1<a3<…<a2n-1，所有的偶数项满足a2<a4<…<a2n； (3)任意相邻的两项a2i-1与a2i(1≤i≤n)满足奇数项小于偶数项，即：a2i-1<a2i。现在的任务是：对于给定的n，请求出有多少个不同的长度为2n的有趣的数列。因为最后的答案可能很大，所以只要求输...
12014年12月23日5,399递推与动规,卡特兰数
「BZOJ2281」[SDOI2011] 黑白棋
Description黑白棋（game）「问题描述」小A和小B又想到了一个新的游戏。这个游戏是在一个1*n的棋盘上进行的，棋盘上有k个棋子，一半是黑色，一半是白色。最左边是白色棋子，最右边是黑色棋子，相邻的棋子颜色不同。小A可以移动白色棋子，小B可以移动黑色的棋子，他们每次操作可以移动1到d个棋子。每当移动某一个棋子时，这个棋子不能跨越两边的棋子，当然也不可以出界。当谁不可以操作时，谁就失败了。小A和小B轮流操作，现...
22014年12月22日7,110递推与动规,博弈论,排列组合
「BZOJ1924」[SDOI2010] 所驼门王的宝藏
「问题描述」==============================================================在宽广的非洲荒漠中,生活着一群勤劳勇敢的羊驼家族。被族人恭称为“先知”的AlpacaL.Sotomon是这个家族的领袖,外人也称其为“所驼门王”。所驼门王毕生致力于维护家族的安定与和谐,他曾亲自率军粉碎河蟹帝国主义的野蛮侵略,为族人立下赫赫战功。所驼门王一生财宝无数,但因其生性节俭低调,他将财宝埋藏在自己设计的地下宫殿里,这也是今天HenryCurt...
02014年12月20日6,236递推与动规,STL,图的连通
NOI2009管道取珠
DescriptionInput第一行包含两个整数n,m，分别表示上下两个管道中球的数目。第二行为一个AB字符串，长度为n，表示上管道中从左到右球的类型。其中A表示浅色球，B表示深色球。第三行为一个AB字符串，长度为m，表示下管道中的情形。Output仅包含一行，即为Sigma(Ai^2)i从1到k除以1024523的余数。SampleInput21ABBSampleOutput5HINT样例即为文中(图3)。共有两种不同的输出序列形式，序列BAB有1种产生方式，而...
02014年12月17日3,764递推与动规
「BZOJ2431」[HAOI2009] 逆序对数列
Description对于一个数列{ai}，如果有i<j且ai>aj，那么我们称ai与aj为一对逆序对数。若对于任意一个由1~n自然数组成的数列，可以很容易求出有多少个逆序对数。那么逆序对数为k的这样自然数数列到底有多少个？Input第一行为两个整数n，k。Output写入一个整数，表示符合条件的数列个数，由于这个数可能很大，你只需输出该数对10000求余数后的结果。SampleInput样例输入41SampleOutput样例输出3样例说明：下列3个数列逆序...
02014年12月16日3,885递推与动规
「BZOJ3791」作业
Description众所周知，白神是具有神奇的能力的。比如说，他对数学作业说一声“数”，数学作业就会出于畏惧而自己完成；对语文作业说一声“语”，语文作业就会出于畏惧而自己完成。今天，语文老师和数学老师布置了许多作业，同学们纷纷寻找白神寻求帮助。白神作为一个助人为乐的人，便答应下来。回到家，白神将这N份作业按顺序摊开，发现语文作业数学作业混在一起，这就让白神苦恼起来，他如果对连续一段作业喊出“数”，那么里面...
02014年12月15日2,691递推与动规
「CF494B」Obsessive String
Hamedhasrecentlyfoundastringtandsuddenlybecamequitefondofit.Hespentseveraldaystryingtofindalloccurrencesoftinotherstringshehad.Finallyhebecametiredandstartedthinkingaboutthefollowingproblem.Givenastringshowmanywaysaretheretoextractk ≥ 1non-overlappingsubstringsfromitsuchthateachofthemcontainsstringtasasubstring?Moreformally,youneedtocalculatethenumberofwaystochoosetwosequencesa1, a2, ......
02014年12月14日4,313递推与动规,KMP
「BZOJ1487」[HNOI2009] 无归岛
DescriptionNeverland是个神奇的地方，它由一些岛屿环形排列组成，每个岛上都生活着之中与众不同的物种。但是这些物种都有一个共同的生活习性：对于同一个岛上的任意两个生物，他们有且仅有一个公共朋友，即对同一岛上的任意两个生物a和b有且仅有一个生物c既是a的朋友也是b的朋友，当然某些岛上也可能会只有一个生物孤单地生活着。这一习性有一个明显的好处，当两个生物发生矛盾的时候，他们可以请那个唯一的公共朋友来裁决谁对谁...
32014年12月12日4,494递推与动规,仙人掌
「BZOJ3174」[TJOI2013] 拯救小矮人
Description一群小矮人掉进了一个很深的陷阱里，由于太矮爬不上来，于是他们决定搭一个人梯。即：一个小矮人站在另一小矮人的肩膀上，知道最顶端的小矮人伸直胳膊可以碰到陷阱口。对于每一个小矮人，我们知道他从脚到肩膀的高度Ai，并且他的胳膊长度为Bi。陷阱深度为H。如果我们利用矮人1，矮人2，矮人3,。。。矮人k搭一个梯子，满足A1+A2+A3+....+Ak+Bk>=H,那么矮人k就可以离开陷阱逃跑了，一旦一个矮人逃跑了，他就...
02014年12月9日3,665递推与动规
「BZOJ3770」疯狂的限制
Description给定k个限制条件，其中第i个条件用c[i],l[i],r[i]表示：字符c[i]在字符串中的出现次数大等于l[i]，小等于r[i]。若一个字符串满足的限制条件的个数大等于L，小等于R，则称该串为StenisString给定一小写字母串s，求s有多少个子串是SteinsString。Input第一行一个非空的小写字母串s第二行三个整数k,L,R。以下k行，每行1个字符和2个整数表示c[i],l[i],r[i]Output一个整数，表示答案SampleInputelpsycongroo312...
42014年12月8日3,106递推与动规
「BZOJ3769」「SPOJ 8549 BST again
Description求有多少棵大小为n的深度为h的二叉树。（树根深度为0；左右子树有别；答案对1000000007取模）Input第一行一个整数T，表示数据组数。以下T行，每行2个整数n和h。Output共T行，每行一个整数表示答案（对1000000007取模）SampleInput22132SampleOutput24HINT对于100%的数据，1<=n<=600,0<=h<=600,1<=T<=10题解f[i][j]表示大小i，深度小于j的二叉树数量则f[i][j]=(1<=k<=i)Σf[k-1]...
02014年12月3日2,915递推与动规