Problem 1: whyleast
为什么最少

问题描述
    时间过得真快， 16号就是我的19岁生日了。为了让自己在新的一岁里人品加加，本菜鸟特地准备了原创菜题大餐供各位大牛享乐，希望大家人人400分。我们今天的第一题巨 菜无比，此题乃经典的Hanoi塔问题。在1号塔上有n个盘子，你需要按照Hanoi塔的要求把所有的盘子都移动到3号塔上。
    我一直想不通的是，为什么那些智力题总是要求人们用最少的步骤完成题目中的要求。为什么非要最少呢？这次我们来点特别的，我希望你的程序能够用最多的步数达到要求，而且在此过程中不重复出现任何一种状态。

输入数据
    输入数据只有一个正整数n，表示Hanoi塔问题的金片个数。

输出数据
    第一行输出在不重复出现状态的情况下完成n阶Hanoi塔的最多步数。
    以下若干行依次表示你的操作步骤，每一行两个数a,b表示在这一步应该把a号柱最顶上的金片移动到b号柱上。
    如果有多种方案，你只需要输出其中一种即可。评测系统可以判断你的方案的正确性。

样例输入
2

样例输出
8
1 2
2 3
1 2
3 2
2 1
2 3
1 2
2 3

数据规模
    对于所有数据，n<=12。

附：Hanoi塔问题简介（摘自http://www.matrix67.com/blog/article.asp?id=29）




Problem 2: height
身高控制计划

问题描述
     不要总以为MM只担心自己的体重。经过Matrix67的观察，他发现他身边的MM们更关注自己的身高。MM们都希望自己能长高一些但不要长得太高。如果 两个MM的身高相差不多，矮的MM会羡慕较高的MM，希望能长得和她一样修长；如果两个MM的身高相差太大，高的MM反而会想变得和较矮的MM一样娇小。 Matrix67为了控制GF们的身高，采取了一项身高控制计划：任意两个女生A和B之间，假设A要比B高一些，如果A高出B的1/4，则A应该以B的身 高为目标；相反，如果A的身高小于等于B的1.25倍（但仍然比B高），则B应该努力向A的身高看齐。我们假设不存在身高相等的MM。这样， Matrix67的n个MM之间产生了n(n-1)/2个单向的“榜样”关系。
    之后，Matrix67发现，这样的关系设定存在一个问 题：有可能出现A以B为学习目标，B以C为学习目标，C又以A为学习目标的情况。这不相当于自己是自己的榜样么？这样的循环非常可笑，显然是不科学的。 Matrix67希望调整一些关系的方向从而消除所有的循环。Matrix67每次改变其中一对MM之间的关系方向，你需要写程序判断，每一次改变后n个 MM之间的“榜样”关系是否存在循环。

输入数据
    第一行输入两个用空格隔开的正整数n和m，分别表示MM的个数和改变方向的总次数。
    以下n行每行一个数，其中第i行表示编号为i的MM的身高。为了避免身高相等的情况，高度值已经被“放大”过，所有高度均为不超过2 000 000 000的正整数。
    接下来的m行里每行有用空格隔开的两个不相等的正整数A, B，表示Matrix67对编号为A的MM和编号为B的MM之间的单向关系进行反向。

输出数据
    对于Matrix67的每一次操作，你需要输出是否存在某个MM以自己为学习目标的情况（即关系图中是否存在循环）。如果是，则输出“YES”，如果不是，请输出“NO”。
    你的输出应该有m行。

样例输入
4 3
10
7
8
9
3 4
1 2
4 1

样例输出
YES
NO
YES

样例说明
        
    10超过了7的5/4，因此身高为10的MM向身高为7的MM学习；
    10小于等于8的5/4，因此身高为8的MM向身高为10的MM学习。
    同样地，还有9-->10,7-->8,9-->7,8-->9。
    这一组关系中存在多个循环，比如①-->②-->③-->①，再比如①-->②-->③-->④-->①。
    第一次Matrix67将改变③和④之间的方向，这消除了上述第二个循环，但前一个循环仍然存在。
    第二次Matrix67将改变①和②之间的方向，此时关系图中已经不存在循环了。
    第三次Matrix67改变了①和④之间的方向，这将导致新的循环①-->④-->③-->①的出现。

数据规模：
    对于30%的数据，n<=10, m<=100；
    对于50%的数据，n<=100, m<=1000；
    对于70%的数据，n<=1000, m<=100 000；
    对于100%的数据，n<=100 000, m<=100 000。



Problem 3: wolf
狼的复仇

问题描述
    山谷里有n座森林，这些森林从1到n编号。某些森林之间有小路相连，总共m条小路连通了这n座森林，任意两座森林之间都有至少一条路径可以互相到达。
     很久很久以前，这里是狼的家园。在每一座森林里都有一匹狼，每一匹狼都静静地守护着它所在的森林。直到有一天，人类出现了。它们疯狂地开垦1号森林，并且 杀死了1号森林的狼。以后，这座森林就好像属于人类了一样，不时有人来到1号森林。其余的n-1匹狼不愿看到悲剧再次发生，它们希望集合它们的力量，为种 族，为大自然报仇。
    机会来了。一次偶然的机会，大灰狼们获得了一个重要的情报——有一个小MM经常独自游荡于1号森林。消息传遍了整个狼 群，小MM细腻的皮肤和鲜嫩的肉令它们的血液沸腾起来，每一匹狼都幻想着能扑上前去撕裂MM的身体，舔拭那温热的血液。唯一的问题是，它们需要尽快察觉小 MM的出现并快速奔向目的地。但由于山谷地形复杂，在第一时间里观察到小MM的出现谈何容易。因此，狼群计划在某些森林建立瞭望塔。当小MM再次出现在1 号森林里时，所在的森林里有瞭望塔的狼可以立即发现这一情况，并且沿着最短路径奔向MM。有时最短路不止一条，在途中每当有多条路可以选择时，狼总会选择 前往编号较小的森林。这些狼的行动将唤起最短路上沿途经过的狼，这些最短路上的狼将会闻声而起，一同对MM发起进攻。每匹狼都有自己的攻击力，最终对小 MM的攻击力即是所有到达1号森林的狼的攻击力总和。注意攻击力的值有可能为负数，因为有一些狼很可能会“拖后腿”，对整个种族的复仇计划反而不利。
     由于森林的地形不同，在不同的地方建造瞭望塔需要的材料不同。现在狼群里一共有k个单位的建筑材料，并且它们已经计算出在n-1座森林中建造瞭望塔各自需 要的材料数目。请你来计算一下，在哪些森林里建造瞭望塔可以使得最终到达1号森林的狼群攻击力总和最大。当然，建筑材料不一定要全部用完，但你的方案所需 要的建筑材料不能超过总的材料数k。

输入数据
    第一行输入三个用空格隔开的正整数k, n, m，分别表示材料的总数量，森林的数量和小路的数量。1号森林总是MM出没的地方，其余n-1座森林是狼所在的地方。
    第二行到第n行每行有两个用空格隔开的整数，依次表示2号森林到n号森林里的狼的攻击力和在这里建造瞭望塔所需要的材料数。狼的攻击力绝对值不超过10000（可能为负数），每个瞭望塔的材料耗费都是不超过100的正整数。
    接下来m行每行有三个用空格隔开的数x,y,d，表示在x森林和y森林之间存在一条长度为d的路。路的长度是不超过10000的正整数。

输出数据
    输出在满足材料数限制下建造瞭望塔，最多可以给MM带去多大的攻击力。

样例输入
8 7 10
1 4
1 2
2 4
-3 5
9 4
2 1
1 4 2
4 3 4
2 3 3
5 1 2
2 4 1
1 2 3
6 7 1
2 7 4
2 6 8
5 6 5

样例输出
10

样例说明
    输入数据如下图所示，我们用AP来表示攻击力，用cost来表示瞭望塔的材料花费。在涂有蓝色的节点上建造瞭望塔花费仅为7，由于7<=8，因此这种方案未超过材料预算。我们下面计算这种方案所带来的攻击力。
        
     这三匹狼的行走路线已经用箭头表示了出来。注意3号森林和7号森林的狼有多个到达节点1的最短路径，它总是选择标号较小的节点前进。这些路线经过了两个绿 色的节点，这两个绿色的节点所对应的狼的攻击力也将加入总攻击力中（必须加入计算且仅算一次）。这种方案的攻击力为1+1+2+9-3=10。事实上，攻 击力最大为10，没有其它的建造方案使得总攻击力大于10且材料花费不超过8。

数据规模
    对于30%的数据， k<=1, n<=10, m<=100
    对于50%的数据， k<=10, n<=100, m<=1000
    对于100%的数据，k<=100, n<=1000, m<=10000

Matrix67提醒各位女同学：独自外出时请注意安全。



Problem 4: garden
和MM逛花园

问题描述
    花园设计强调，简单就是美。Matrix67常去的花园有着非常简单的布局：花园的所有景点的位置都是“对齐”了的，这些景点可以看作是平面坐标上的格点。相邻的景点之间有小路相连，这些小路全部平行于坐标轴。景点和小路组成了一个“不完整的网格”。
    一个典型的花园布局如左图所示。花园布局在6行4列的网格上，花园的16个景点的位置用红色标注在了图中。黑色线条表示景点间的小路，其余灰色部分实际并不存在。
        

    Matrix67 的生日那天，他要带着他的MM在花园里游玩。Matrix67不会带MM两次经过同一个景点，因此每个景点最多被游览一次。他和他的MM边走边聊，他们是 如此的投入以致于他们从不会“主动地拐弯”。也就是说，除非前方已没有景点或是前方的景点已经访问过，否则他们会一直往前走下去。当前方景点不存在或已游 览过时，Matrix67会带MM另选一个方向继续前进。由于景点个数有限，访问过的景点将越来越多，迟早会出现不能再走的情况（即四个方向上的相邻景点 都访问过了），此时他们将结束花园的游览。Matrix67希望知道以这种方式游览花园是否有可能遍历所有的景点。Matrix67可以选择从任意一个景 点开始游览，以任意一个景点结束。
    在上图所示的花园布局中，一种可能的游览方式如右图所示。这种浏览方式从(1,2)出发，以(2,4)结束，经过每个景点恰好一次。

输入数据
    第一行输入两个用空格隔开的正整数m和n，表示花园被布局在m行n列的网格上。
    以下m行每行n个字符，字符“0”表示该位置没有景点，字符“1”表示对应位置有景点。这些数字之间没有空格。

输出数据
    你的程序需要寻找满足“不主动拐弯”性质且遍历所有景点的游览路线。
    如果没有这样的游览路线，请输出一行“Impossible”（不带引号，注意大小写）。
    如果存在游览路线，请依次输出你的方案中访问的景点的坐标，每行输出一个。坐标的表示格式为“(x,y)”，代表第x行第y列。
    如果有多种方案，你只需要输出其中一种即可。评测系统可以判断你的方案的正确性。

样例输入
6 4
1100
1001
1111
1100
1110
1110

样例输出
(1,2)
(1,1)
(2,1)
(3,1)
(4,1)
(5,1)
(6,1)
(6,2)
(6,3)
(5,3)
(5,2)
(4,2)
(3,2)
(3,3)
(3,4)
(2,4)

数据规模
    对于30%的数据，n,m<=5；
    对于100%的数据，n,m<=10。

题解

Problem 1: 为什么最少
    如果你还不熟悉Hanoi塔的解法，去题目中提到的那篇日志看看 吧。如果你已经熟悉Hanoi塔的解法，你会立刻想到这道题的解法：依然是递归地解决。至于怎么递归，样例已经告诉我们了：把前n-1个金片从1号柱搬到 3号柱，把第n片移到2号柱，又把那n-1片从3号柱搬回1号柱，再把第n片搬到3号柱，最后把那n-1个金片又搬过来，完成整个操作。
    我们下面解决三个问题：为什么这样不会重复出现状态，这样的移动步数是多少，为什么这样的操作步数是最多的。
    为什么这样不会出现重复的状态呢？因为我们假设前n-1个金片的移动过程中没有重复状态，而三次对n-1的调用时整个状态由于第n个金片的位置不同而不同。
    这样的方法获得的操作步数是多少呢？答案是3^n-1。我们可以用数学归纳法证明，n=1时步数为2显然正确，而f(n+1)=3f(n)+2=3*(3^n-1)+2=3^(n+1)-1。
    为什么这样的操作步数是最多的呢？废话，这样的操作步数当然是最多的，因为总的状态数也只有3^n个（每个金片的三种可能的位置确定了一种状态），你的移动步骤能比这个数目还多就见鬼了。

    这道题有人用了math库，没有提供math库导致无法编译是我的失误，向大家道歉。

    Hanoi问题的变种太多了，比如多根柱子、单向移动、双色金片等等。dd上次不是也出了一题么。

    这题代码很短，我公布在下面。



Problem 2: 身高控制计划
    一个竞赛图是指任两个点之间都有一条有向边的图。竞赛图有很多奇妙的性质，比如一个竞赛图必然存在一条经过所有节点的路等等。
    下面我们证明，竞赛图中不存在环当且仅当所有顶点的出度从小到大排列依次为0, 1, 2, ... , n-1 ：
     如果一个有向图的所有点出度都至少为1，那么这个图一定有环，因为在找到环之前DFS总可以找到新的节点。如果有向图无环，必然存在一个点没有出度。由于 任两点之间都有有向边，那么其它所有点都要连一条边指向它，这样其它所有点的出度都至少为1了。删掉这个出度为0的点后剩下的图仍然无环，不断对剩下的图 继续上面的过程就得到了我们的结论。
    现在我们的算法就很明确了，首先统计初始状态下的出度，然后设计某种数据结构完成两种操作：改变一个数（加一减一），询问所有数是否恰好为0, 1, 2, ... , n-1 。
     统计初始状态下的出度方法有很多，这里介绍两个。首先对身高排序，然后对于每个人进行二分，寻找有序数列中该数的4/5和5/4各在什么地方。还有一种方 法也是先排序，然后从左到右扫描整个序列，并保持两个指针始终指向4/5和5/4处。每次开始处理一个新的数时都把两个指针适当地右移直到超出了这个数的 4/5或5/4为止。两种方法都是O(nlogn)。别以为第二种方法是线性的哦，线性算法之前还有一个排序呢。
    操作的处理也有不少方法。最简单的方法就是统计当前图中出度的数目有多少种。就是说，用a[i]表示出度为i的点有多少个，然后不断更新a[i]>0的有多少个。当这个数目等于n时我们就认为图中没有环（因为出度可能的取值只有从0到n-1共n种）。
    注意，由于同一条边可能被操作多次，因此需要一个Hash表（开散列）来判重。具体地说，你需要判断这条边以前被操作过奇数次还是偶数次，以决定哪边的出度要增加，哪边的出度要减小。


Problem 3: 狼的复仇

     把这个问题中所有的最短路都画出来是什么样子？它一定是一棵树！为什么？首先，图肯定是连通的，因为源点到任一个点都有一条最短路；其次，图肯定无环，因 为源点到任一个点只有一条最短路（环的出现将意味着某些点有更短的路存在）。仔细想一下Dijkstra的算法过程，不难想到Dijkstra算法的实质 就是在建这棵树——每一次由x节点加上边x-y扩展到y节点就记作x是y的父亲。注意观察上图中左图是如何变成右图的。这样，题目变成了这种形式：在有根 树上，除根节点之外的其它节点中选择一些节点，使得这些节点和它们所有祖先的权值和最大。这是一个经典的树型动态规划模型。我们用f[i,j]表示以节点 i为根节点的子树花费j个单位的材料最多可以得到多大的攻击力。令节点1的材料和攻击力都为0，那么最后输出f[1,0..k]中的最大值即可。决策分为 两类，要么该位置建一个塔，要么把所有材料适当地分给儿子（自己就不需要再建了）。但这样的复杂度太高，我们需要用DP嵌套或者更巧妙的多叉转二叉来解 决。
    DP嵌套理解起来更简单，它主要是解决这样一个子问题：若某个节点有m个儿子，我们需要寻找当j1+j2+...+jm等于某个定值 时f[儿子1,j1]+f[儿子2,j2]+...+f[儿子m,jm]的最大值。这个子问题与我的某次模拟赛中论文课题选择那道DP题几乎是一模一样， 看一看那道题就明白了。下面简单描述多叉转二叉的方法。

     如果你还不知道多叉转二叉的话，这道题是一个绝好的学习材料。一棵多叉树可以用“左儿子右兄弟”的方法转为二叉树，具体的说就是把多叉树转化为这种形式： 节点的左儿子才是真正的儿子，节点的右儿子只是和它同辈的兄弟。注意看上图的左图是如何变成右图的。现在，我们的f[i,j]表示在这棵二叉树上的子树花 费j个材料的最大值。它有这样五种决策：
    1. 自己把材料用了；
    2. 自己把材料用了后剩下的给右边；
    3. j个材料全部用到左边去，加上自己的权值；
    4. j个材料全部用到右边去，不加自己的权值；
    5. j个材料左边用一点，右边用一点，加上自己的权值。
    注意思考决策3-5中为什么有的决策要算自己的权值，有的不算自己的权值。转化后的二叉树并不是原来的树，左边和右边的意义是不同的。在原图中对比一下你就能看到这些决策的实质了。
    状态O(nk)个，决策为O(k)，因此这道题可以在O(nk^2)的时间内解决。

     这题有很多细节需要注意。比如，建树时如何处理多条最短路优先选择编号较小节点，解决方法是在Dijkstra的更新过程中，当新的最短路与原来相同但新 的父亲比原父亲编号小时仍然要更新。还有几种特殊情况需要输出0，比如所有的花费都大于k时，再比如所有的攻击力都小于0时。


Problem 4: 和MM逛花园
    这题搜索，DFS枚举方向，没什么好说的。在这里说一下位运算优化。
     用State[x]表示第x行的状态（0表示还没走过，1表示已经走过），用Map[x,y]表示地图第x行第y列的位置是否有景点。假如当前位置是 (x,y)，枚举方向d后进行下面的while循环可以飞快地确定最终状态。细心的人会发现State的储存是“反”的（和实际状态左右颠倒）。这没关 系，只要State的储存一直是反的就没事了。

(比赛时间2007.5.3 )

Bomb

【问题描述】

      一场战争正在A国与B国之间如火如荼的展开。

      B国凭借其强大的经济实力开发除了无数的远程攻击导弹，B国的领导人希望，通过这些导弹直接毁灭A国的指挥部，从而得到战斗的胜利！当然，A国人民不会允许这样那个的事情发生，所以这个世界上还存在再拦截导弹。

      现在，你是一名A国负责导弹拦截的高级助理。

      B国的导弹有效的形成了三维立体打击，我们可以将这些导弹的位置抽象三维中间的点（大小忽略），为了简单起见，我们只考虑一个瞬时的状态，即他们静止的状态。

      拦截导弹设计非常精良，可以精准的引爆对方导弹而不需要自身损失，但是A国面临的一个技术难题是，这些导弹只懂得直线上升。精确的说，这里的直线上升指xyz三维坐标单调上升。

      给所有的B国导弹按照1至N标号，一枚拦截导弹可以打击的对象可以用一个xyz严格单调上升的序列来表示，例如：

B国导弹位置：(0, 0, 0) (1, 1, 0) (1, 1, 1), (2, 2, 2)   一个合法的打击序列为：{1, 3, 4} 一个不合法的打击序列为{1, 2, 4}

      A国领导人将一份导弹位置的清单交给你，并且向你提出了两个最简单不过的问题（假装它最简单吧）：

1．一枚拦截导弹最多可以摧毁多少B国的导弹？

2．最少使用多少拦截导弹才能摧毁B国的所有导弹？

不管是为了个人荣誉还是国家容易，更多的是为了饭碗，你，都应该好好的把这个问题解决掉！

 

【算法分析】

      我们先假定所有导弹按照z的非降顺序排列（通过排序得到）。

 

      本题有两个小问：

1．一枚拦截导弹最多可以摧毁多少B国的导弹？

2．最少使用多少拦截导弹才能摧毁B国的所有导弹？

 

小问1通过动态规划解决。记录F(i)表示导弹序列1~i中拦截导弹最后击中导弹i，此时做多击中的导弹个数。那么有：

F(i) = max{F(j)} + 1  （其中导弹j的xyz严格小于导弹i）

因为导弹序列的z非降，所以这个转移是充分的。其实时间复杂度为O(N²)。

 

小问2可以理解成为，需要把导弹序列P剖分为K个不相交的导弹序列P(k)，使得这些导弹序列P(k)的并集为P。对于其中每个导弹序列P(k)满足xyz单调上升。

如果仍然尝试使用动态规划，这样一个问题不易解决，我们需要利用一些其他的思想。

 

根据定义，对于每个导弹序列P(k)，存在且仅存在一个最小的导弹（即xyz最小的导弹）；其他的导弹有且只有一个前驱（即xyz小于该导弹中，xyz最大的导弹）。注意到，k = 无前驱的导弹数 = 导弹总数 – 有前驱的导弹数。因此，问题可以看作是尝试给尽量多的导弹找到自己的前驱。

 

这就是一个最大匹配问题的模型。

 

对于每个导弹p，拆分为两个结点Xp与Yp。若是导弹p的xyz严格大于导弹q的xyz，那么连一条边Xp -> Yq。

求以上二部图的最大匹配，就求出了有前驱的导弹数，问题得以解决。

 

【补充】

      本题涉及偏序集的最小路径覆盖数问题，有兴趣的同学可以查找相关资料。

双亲数

Parents

【问题描述】

      小D是一名数学爱好者，他对数字的着迷到了疯狂的程度。

      我们以d = gcd(a, b)表示a、b的最大公约数，小D执著的认为，这样亲密的关系足可以用双亲来描述，此时，我们称有序数对(a, b)为d的双亲数。

      与正常双亲不太相同的是，对于同一个d，他的双亲太多了 >_<

      比如，(4, 6), (6, 4), (2, 100)都是2的双亲数。

      于是一个这样的问题摆在眼前，对于0 < a <= A, 0 < b <= B，有多少有序数对(a, b)是d的双亲数？

 

【算法分析】

      这是一个明显的动态规划题，关键在于如何压缩状态。由于d的出现并没有什么意义，因为若d > 1，则问题(A, B, d)等价于问题(A / d, B / d, 1)，所以简单起见我们认为d = 1。

 

      以F(A, B)表示满足0 < a <= A, 0 < b <= B的二元组(a, b)中gcd(a, b) = 1的个数。那么我们有：

F(A, B) = A * B – sigma{F(A / d, B / d)}  (1 < d < A, B)   （*）

      其意义是，F(A, B)的方案数为二元组的总个数(A * B)，减去最大公约数大于1的二元组的个数（枚举最大公约数d）。

 

      表面上看，这个方程的状态数为A * B，转移复杂度为O(A + B)，这样总的时间复杂度就高达O((A + B)²)，不能承受。实际上，我们这个方程很有特点：

      所有有用的状态都是F(A / d, B / d)形式的。

      记录G(d) = F(A / d, B / d)，那么(*)可以被改写成为：

G(d) = (A / d) * (B / d) – sigma{G(d’)}   (d|d’, d’ > d, d’ <= A, B)

      注意到，这个方程的状态数为O(A + B)，转移总数为(A + B) / 1 + (A + B) / 2 + (A + B) / 3 + …… + (A + B) / (A + B) = O((A + B)lg(A + B))。这个时间复杂度完全可以接受。

新打鼹鼠

Strike

【问题描述】

Hst是个爱思考的好孩子。这一天LL博士给了他一道题目做：如下：

鼹鼠是一种很喜欢挖洞的动物，但每过一定的时间，它还是喜欢把头探出到地面上来透透气的。根据这个特点阿牛编写了一个打鼹鼠的游戏：在一个n*n的网格中，在某些时刻鼹鼠会在某一个网格探出头来透透气。你可以控制一个机器人来打鼹鼠，如果i时刻鼹鼠在某个网格中出现，而机器人也处于同一网格的话，那么这个鼹鼠就会被机器人打死。而机器人每一时刻只能够移动一格或停留在原地不动。机器人的移动是指从当前所处的网格移向相邻的网格，即从坐标为（i,j）的网格移向(i-1, j),(i+1, j),(i,j-1),(i,j+1)四个网格，机器人不能走出整个n*n的网格。游戏开始时，你可以自由选定机器人的初始位置。 现在知道在一段时间内，鼹鼠出现的时间和地点，请编写一个程序使机器人在这一段时间内打死尽可能多的鼹鼠。 【输入格式】（input.txt） 从文件input.txt中读入数据，文件第一行为n（n<=1000）, m（m<=10000），其中m表示在这一段时间内出现的鼹鼠的个数，接下来的m行中每行有三个数据time,x,y表示有一只鼹鼠在游戏开始后time个时刻，在第x行第y个网格里出现了一只鼹鼠。Time按递增的顺序给出。注意同一时刻可能出现多只鼹鼠，但同一时刻同一地点只可能出现一只鼹鼠。 【输出格式】（output.txt） 输出文件output.txt中仅包含一个正整数，表示被打死鼹鼠的最大数目。 【输入输出样例】 input.txt        output.txt 2 2            1 1 1 1 2 2 2

这不是我们的问题，当然这道题相信大家都知道是出自HNOI2004的第一题：打鼹鼠。Hst可是很聪明的哟，他花了0.5分钟就想出来怎么做并且编完了。但是他又提出了一个新的问题：

有m只鼹鼠出现在一个1 ~ n的长条上。对于第k只鼹鼠，我们用t[k], w[k], x[k]来描述。即在t[k]时刻，会有一只分值为w[k]的鼹鼠k出现在位置x[k]上。现在你有一个锤头，每一时刻它都停留在一个位置上。你可以用它不费时间的敲死一只鼹鼠并得到相应的分值。但是每个时刻你的锤头最多只能移动p格。也就是说如果s时刻你在位置pos，那么s + 1时刻你运动到位置pos – p ~ pos + p。

在零时刻你的锤子可以在任意位置。鼹鼠出现的时刻大于0。同时我们保证同一时间同一位置不会有两只鼹鼠出现，因为他们太胖了。

 

【算法分析】

      我们对本题的理解应该是一道入门动态规划，然而当范围增大之后，我们不得不在算法上做出一些大的改进以解决问题。

 

      让我们先回顾一下动态规划的解决方法。以状态F(t, pos)表示时刻t，锤头停留在了位置pos上，此时我们能够得到的最大分值，那么有转移方程：

F(t, pos) = max{ F(t – 1, k) } + value(t, pos)    (*)

      其中，value(t, pos)表示时刻t位置pos上鼹鼠的分值（没有则为0）并且abs(k – pos) <= p。

      不难发现，这个方程的时间复杂度为O(NTP)，空间复杂度为O(NT)，不能解决本题。

 

      我们必须看到，这个方程中存在着太多的冗余。实际上，F(t, pos)只有在一个有鼹鼠出现的时间、位置才有意义。因此，我们定义状态G(u)，表示锤头在鼹鼠x出现的时刻以及位置时所获得的最大分值，我们有：

G(u) = max{ G(v) } + value(u)     (**)

      其中，abs(Xu – Xv) <= (Tu – Tv) * p。

 

      (**)较(*)来说有了很大的改进，状态数下降为O(M)，时间复杂度下降为O(M²)。接下来我们要做的，是找出有效的状态转移。

 

      我们考虑把所有的有效状态投射到一个平面上，(Xu, Tu)。观察状态u能够使用的状态转移，都在一个倒漏斗状的图形中：

      我们将这个平面缩放旋转一下，可以将这个问题理解为：平面上有M个点，每个点有一个权值value(k)，需要找一条路径，这条路径只沿向上或者向右的方向移动，需要使这条路径经过的点的总权和最大。这个也是一个经典的动态规划问题了，我们知道它可以在O(MlogM)的时间内解决，这里就不加赘述了。

 

复原序列

Recover

【问题描述】

      本题中，我们考察的是一类特殊的序列，这类序列只有+、-（正号，负号）两种符号构成，比如：-+++---++

      我们将其中连续的+的长度按从左到右的顺序写出，即其派生序列，如-+++---++的派生序列为（3，2）。

      现在的问题是，我们已知一个序列A的派生序列B，但是A的部分符号已经模糊到不能辨认的地步了。我们需要确定尽量多的符号。

 

【输入文件】

      输入文件有两行。

第一行一个由+、-、？构成的序列，描述A，其中？表示已经无法辨认的符号。

第二行有若干整数描述A的生成序列B。

 

【输出文件】

      输出一行，一个序列描述你恢复后的序列A（不能多余的空格），如果无解则输出一行No Solution。

 

【数据约定】

对于30%的数据满足|A| < 11

对于50%的数据满足|A| < 101

对于100%的数据满足|A| < 20001

B的元素属于[1 … |A|]

 

【样例】

输入样例1                                          输出样例1

+-?+-+++                                         +-++-+++

1 2 3

 

输入样例2

???                                                   ?+?

2

 

输入样例3

--                                                      No Solution

1

 

【算法分析】

      本题是全套试卷的压轴题，算法、时间、空间和编程复杂度上都有一定难度。

 

      退一步思考这个问题，把确定性问题转化为一个可行性的问题：输入的数据是否有解呢？

      这个问题可以使用动态规划解决。我们把给定的派生序列还原为一个模版，这个模版由*和+两种字符构成，其中*匹配减号（至少一个），+匹配一个加号。为了方便起见，我们在A前后加上一个减号，在B还原成的模版前后加上一个*。

 

      状态F(u, v)表示，A的前u个字符和模版的前v个字符是否能够完全匹配，我们有：

若a(u) <> b(v)，那么F(u, v) = false；

若a(u) = b(v) = +，那么F(u, v) = F(u – 1, v – 1)；

若a(u) = -、b(v) = *，那么F(u, v) = F(u – 1, v – 1) or F(u – 1, v)

其中，-+都可以作为？的转移。

 

      这个DP方程的时间和空间复杂度均为O(N²)。

 

      现在我们需要建立的，是F与确定问号之间关系。我们把整个DP看成一个有向无环图。DP的每一个状态都看作一个点，每一个转移看作一条有向边。那么，我们注意到，只有F(0,0)到F(|A|, |B|)的闭经点集中的状态才是可能达到的状态。

      F所引出的图非常特殊：阶段分明。这也就是说，我们可以倒推出所有结点是否在必经点集内：

      F(|A|, |B|)在必经点集内。

F(u, v)在必经点集内，则F(u, v)通过有向边直接相连的状态F(u – 1, v0)也在必经点集内。

 

      固定u，记录F(u, v)中在必经点集中的所有能的v为集合S(u)，如果S(u)只有一种字符构成，那么a(u)是可以确定的，否则a(u)是不能够确定的。这就是我们的中心算法，其时间复杂度和空间复杂度为O(N²)。

 

      为了使问题不能够如此轻易的被解决，我们特意将数据范围加大到20000，这使得空间复杂度成为了一个很大的问题。我们需要使用滚动数组来解决，但是又要考虑到是间复杂度。

      记F(u)表示所有F(u, v)的状态集合。注意到，如果知道了F(u)，那么便可以推出F(u+1)、F(u+2)……

      我们采取了一种分段的方法来解决空间和时间的平衡。

 

      永久性储存的状态是F(xm)，其中m是一个事先确定的常数，xm即为m的整数倍。对于其他所有的F(u)，我们只在其被使用时才计算出来并且采用动态数组储存。这样，当m取为sqrt(n)时，我们的空间复杂度就下降为O(nsqrt(n))，时间复杂度不变。

      此题被解决。