递推与动规 - Page 9

「NOIP模拟赛」数字
「问题描述」一个数字被称为好数字当他满足下列条件：它有2*n个数位，n是正整数(允许有前导0)。构成它的每个数字都在给定的数字集合S中。它前n位之和与后n位之和相等或者它奇数位之和与偶数位之和相等例如对于n=2,S={1,2}，合法的好数字有1111,1122,1212,1221,2112,2121,2211,2222这样8种。已知n，求合法的好数字的个数mod999983。「输入格式」第一行一个数n。接下来一个长度不超过10的字符串，表示给定的数字集合。「输出格式」...
22014年10月6日3,074递推与动规

「NOIP模拟赛」球的序列
N个编号为1-n的球，每个球都有唯一的编号。这些球被排成两种序列，分别为A、B序列，现在需要重新寻找一个球的序列l，对于这个子序列l中任意的两个球，要求j,k(j<k)，都要求满足lj在A中位置比lk在A中位置靠前，却lj在B中位置比lk在B中位置靠前，请你计算这个子序列l的最大长度。输入:第一行一个整数，表示N。第二行N个整数，表示A序列。第三行N个整数，表示B序列。样例输入51243552341样例输出2样例说明L可以是{2,3...
02014年10月4日3,486递推与动规,二分法
「BZOJ2023 / 1630」[Usaco2005 Nov] Ant Counting 数蚂蚁
Description 有一天，贝茜无聊地坐在蚂蚁洞前看蚂蚁们进进出出地搬运食物．很快贝茜发现有些蚂蚁长得几乎一模一样，于是她认为那些蚂蚁是兄弟，也就是说它们是同一个家族里的成员．她也发现整个蚂蚁群里有时只有一只出来觅食，有时是几只，有时干脆整个蚁群一起出来．这样一来，蚂蚁们出行觅食时的组队方案就有很多种．作为一头有数学头脑的奶牛，贝茜注意到整个蚂蚁群由T(1≤T≤1000)个家族组成，她将这些家族按1到T依...
12014年10月2日4,373递推与动规
「BZOJ3297」[USACO2011 Open] forgot
Description发生了这么多，贝茜已经忘记了她cowtube密码。然而，她记得一些有用的信息。首先，她记得她的密码（记为变量P）长度为L（1<=L<=1,000）字符串，并可以被分成一个或多个词（不一定是唯一的），词来自于字典中NW（1<=NW<=1,000）个独特的词。一个词W_i，被定义为一个长度1..20的小写字母序列('a'..'z')。她还记得她密码中某些字母的位置。请看下面的例子。贝西知道她的密码看起来像"a??l?ban???????...
12014年10月1日2,935递推与动规
NOIP2001统计单词个数
题目描述Description给出一个长度不超过200的由小写英文字母组成的字母串(约定;该字串以每行20个字母的方式输入，且保证每行一定为20个)。要求将此字母串分成k份(1<k<=40)，且每份中包含的单词个数加起来总数最大(每份中包含的单词可以部分重叠。当选用一个单词之后，其第一个字母不能再用。例如字符串this中可包含this和is，选用this之后就不能包含th)（管理员注：这里的不能再用指的是位置，不是字母本身。比如thisis可以...
02014年9月22日3,080递推与动规
「BZOJ1057」[ZJOI2007] 棋盘制作
Description国际象棋是世界上最古老的博弈游戏之一，和中国的围棋、象棋以及日本的将棋同享盛名。据说国际象棋起源于易经的思想，棋盘是一个8*8大小的黑白相间的方阵，对应八八六十四卦，黑白对应阴阳。而我们的主人公小Q，正是国际象棋的狂热爱好者。作为一个顶尖高手，他已不满足于普通的棋盘与规则，于是他跟他的好朋友小W决定将棋盘扩大以适应他们的新规则。小Q找到了一张由N*M个正方形的格子组成的矩形纸片，每个格子被...
02014年9月20日4,459递推与动规
「CFgym100486J」 Saving the Universe
heurbanlegendgoesthatifyougototheGooglehomepageandsearchforGoogle,theuniversewillimplode.Wehaveasecrettoshare...Itistrue!Pleasedon'ttryit,ortellanyone.Allright,maybenot.WearejustkiddingThesameisnottrueforauniversefarfaraway.Inthatuniverse,ifyousearchonanysearchengineforthatsearchengine'sname,theuniversedoesimplode!Tocombatthis,peoplecameupwithaninterestingsolution.Allqueriesarepooledt...
02014年9月20日2,298递推与动规
「CF467C」George and Job
ThenewITone6hasbeenreleasedrecentlyandGeorgegotreallykeentobuyit.Unfortunately,hedidn'thaveenoughmoney,soGeorgewasgoingtoworkasaprogrammer.Nowhefacedthefollowingproblematthework.Givenasequenceofnintegersp1, p2, ..., pn.Youaretochoosekpairsofintegers:[l1, r1], [l2, r2], ..., [lk, rk] (1 ≤ l1 ≤ r1 < l2 ≤ r2 < ... < lk ≤ rk ≤ n; ri - li + 1 = m)...
12014年9月19日4,075递推与动规
「BZOJ1025」[SCOI2009] 游戏
Descriptionwindy学会了一种游戏。对于1到N这N个数字，都有唯一且不同的1到N的数字与之对应。最开始windy把数字按顺序1，2，3，……，N写一排在纸上。然后再在这一排下面写上它们对应的数字。然后又在新的一排下面写上它们对应的数字。如此反复，直到序列再次变为1，2，3，……，N。如：123456对应的关系为1->22->33->14->55->46->6windy的操作如下123456231546312456123546231456312546123456这时，我们就...
02014年9月13日6,973递推与动规,筛法
「BZOJ2364」城市美化
Description城市A需要美化市容市貌，现在有n个楼房排成一列，每个楼房的高都在[1,1000]的范围内。市长请了一批工程师来对其中一些楼房进行修建，使楼房高度得到上升（不能让楼房高度下降），对一栋楼房修建，使其高度上升x，需要x2的费用。当所有修建完成后，我们把相邻两楼高度的绝对值乘以c(0<=c<=1000)，得到的就是城市损失的钱，我们把它同样看作是费用。现在想请你合理安排修建楼房的方案，使得所需费用最小。Input第...
32014年9月13日3,949递推与动规,单调栈
「NOIP模拟赛」琪露诺
题目描述在幻想乡，琪露诺是以笨蛋闻名的冰之妖精。某一天，琪露诺又在玩速冻青蛙，就是用冰把青蛙瞬间冻起来。但是这只青蛙比以往的要聪明许多，在琪露诺来之前就已经跑到了河的对岸。于是琪露诺决定到河岸去追青蛙。小河可以看作一列格子依次编号为0到N，琪露诺只能从编号小的格子移动到编号大的格子。而且琪露诺按照一种特殊的方式进行移动，当她在格子i时，她只会移动到i+L到i+R中的一格。你问为什么她这么移动，这还不简单...
22014年9月10日2,927递推与动规
「BZOJ1044」[HAOI2008] 木棍分割
Description有n根木棍,第i根木棍的长度为Li,n根木棍依次连结了一起,总共有n-1个连接处.现在允许你最多砍断m个连接处,砍完后n根木棍被分成了很多段,要求满足总长度最大的一段长度最小,并且输出有多少种砍的方法使得总长度最大的一段长度最小.并将结果mod10007。。。Input输入文件第一行有2个数n,m.接下来n行每行一个正整数Li,表示第i根木棍的长度.Output输出有2个数,第一个数是总长度最大的一段的长度最小值,第二个数是有多少种...
02014年9月2日5,261递推与动规