动态规划 - Page 16

「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,060递推与动规

「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,468递推与动规,二分法
「BZOJ2023 / 1630」[Usaco2005 Nov] Ant Counting 数蚂蚁
Description 有一天，贝茜无聊地坐在蚂蚁洞前看蚂蚁们进进出出地搬运食物．很快贝茜发现有些蚂蚁长得几乎一模一样，于是她认为那些蚂蚁是兄弟，也就是说它们是同一个家族里的成员．她也发现整个蚂蚁群里有时只有一只出来觅食，有时是几只，有时干脆整个蚁群一起出来．这样一来，蚂蚁们出行觅食时的组队方案就有很多种．作为一头有数学头脑的奶牛，贝茜注意到整个蚂蚁群由T(1≤T≤1000)个家族组成，她将这些家族按1到T依...
12014年10月2日4,358递推与动规
「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,918递推与动规
「NOIP模拟赛」交通
黄金大神国的首都位于hzwer河中的一座岛屿。一道上班的时候，成千上万辆汽车通过岛屿从西岸的住宅区（由桥连接岛的西部）到东岸的工业区（由桥连接岛的东部）。该岛类似于矩形，它的边平行于主方向。故可将它看作是笛卡尔坐标系中的一个A*B的矩形，它的对角分别为（0,0）和（A,B）。岛上有n个交通节点（后宫建筑），编号为1…n，第i个节点坐标为(xi,yi)。如果一个节点的坐标为(0,y)，它就位于岛的西岸。类似的，坐标为(A,y)的...
02014年9月27日3,646树形动规,图的连通
「BZOJ3631」[JLOI2014] 松鼠的新家
Description松鼠的新家是一棵树，前几天刚刚装修了新家，新家有n个房间，并且有n-1根树枝连接，每个房间都可以相互到达，且俩个房间之间的路线都是唯一的。天哪，他居然真的住在“树”上。松鼠想邀请小熊维尼前来参观，并且还指定一份参观指南，他希望维尼能够按照他的指南顺序，先去a1，再去a2，……，最后到an，去参观新家。可是这样会导致维尼重复走很多房间，懒惰的维尼不听地推辞。可是松鼠告诉他，每走到一个房间，他就可以...
22014年9月25日5,220深度搜索,树形动规
NOIP2001统计单词个数
题目描述Description给出一个长度不超过200的由小写英文字母组成的字母串(约定;该字串以每行20个字母的方式输入，且保证每行一定为20个)。要求将此字母串分成k份(1<k<=40)，且每份中包含的单词个数加起来总数最大(每份中包含的单词可以部分重叠。当选用一个单词之后，其第一个字母不能再用。例如字符串this中可包含this和is，选用this之后就不能包含th)（管理员注：这里的不能再用指的是位置，不是字母本身。比如thisis可以...
02014年9月22日3,065递推与动规
「BZOJ1057」[ZJOI2007] 棋盘制作
Description国际象棋是世界上最古老的博弈游戏之一，和中国的围棋、象棋以及日本的将棋同享盛名。据说国际象棋起源于易经的思想，棋盘是一个8*8大小的黑白相间的方阵，对应八八六十四卦，黑白对应阴阳。而我们的主人公小Q，正是国际象棋的狂热爱好者。作为一个顶尖高手，他已不满足于普通的棋盘与规则，于是他跟他的好朋友小W决定将棋盘扩大以适应他们的新规则。小Q找到了一张由N*M个正方形的格子组成的矩形纸片，每个格子被...
02014年9月20日4,448递推与动规
「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,281递推与动规
「CF467D」Fedor and Essay
AfteryouhadhelpedFedortofindfriendsinthe«CallofSoldiers3»game,hestoppedstudyingcompletely.Today,theEnglishteachertoldhimtoprepareanessay.Fedordidn'twanttopreparetheessay,soheaskedAlexforhelp.AlexcametohelpandwrotetheessayforFedor.ButFedordidn'tliketheessayatall.NowFedorisgoingtochangetheessayusingthesynonymdictionaryoftheEnglishlanguage.Fedordoesnotwanttochangethemeaningoftheessa...
02014年9月19日3,232树形动规,图的连通
「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,058递推与动规
「BZOJ3687」「FJ2014集训」简单题
「题目描述」小呆开始研究集合论了，他提出了关于一个数集四个问题：1.子集的异或和的算术和。2.子集的异或和的异或和。3.子集的算术和的算术和。4.子集的算术和的异或和。目前为止，小呆已经解决了前三个问题，还剩下最后一个问题还没有解决，他决定把这个问题交给你，未来的集训队队员来实现。「输入格式」从xor.in中输入数据第一行，一个整数n。第二行，n个正整数，表示a1,a2,...,an「输出格式」输出到xor.out中一行，包含一个整...
22014年9月14日6,216深度搜索,背包动规