树状数组(BIT)实现

在这里只提供模板。

一维情形

提供区间和功能,支援单点delta更新。sum得到的是[1,pos]的值的和。

二维情形

提供矩阵和功能,支援单点更新,sum得到的是从(1,1)拉到(posi,posj)的矩阵中数的总和。

 

SPOJ LCS Longest Common Substring

[等待填坑]

 

SPOJ LCS2 Longest Common Substring II

[详细题解等待填坑]

SPOJ真是业界奇葩

 

HDU 4313 Matrix

题意

给你一颗树,上面有黑点(母体机器人所在位置),有白点(没有潜伏母体机器人的安全节点),并且给了你每一条边的边权(删边(炸毁道路)需要的时间代价)。现在要你以最小代价删掉一些边,使得没有两个黑点同时可以互相连通。输出这个时间花费即可。

思路

树形DP。这个题和Codeforces 461B Appleman and Tree是一个路子的题,都是在一棵树上不允许同时出现两个联通的特定类别的节点。这种问题我们在思考的时候,方向是将当前的大问题分解成同样的小问题,不断分解到最后,然后考虑怎么样根据一些小问题解得出大问题的解,这是DP的思路所在。

这次,我们设状态表示为dp[a][0/1],其中dp[a][0]表示要想让以a为根节点的子树满足题目的要求,而且a所在的联通块里面不可以有黑点,需要的最小代价是多少;dp[a][1]表示要想让以a为根节点的子树满足题目要求,且a所在的联通块里面有且只有一个黑点,需要的最小代价是多少。

设好了状态,我们开始想DP方程:

  • 我们当前检查的点标号是a,我们去逐一检查他的孩子节点,标号是b_{i},如果a是一个黑点:
    • dp[a][1] = \sum\min \left\{\begin{matrix}dp[b_{i}][0]\\ dp[b_{i}][0]+cost(a \rightarrow b_{i})\\ dp[b_{i}][1]+cost(a \rightarrow b_{i})\end{matrix}\right.
      因为当前节点是黑点,我们有三种操作可以选:

      • 当前讨论的孩子部分,如果他没有与任何黑点连着,我们可以把这个部分连入当前讨论的根部分,这就是dp[b_{i}][0],即孩子的代价就是根的代价,因为没有切断就没有增加代价。
      • 把根部分和当前讨论的孩子部分中间的边切断,这样的话无论孩子部分到底有没有和黑点连接,都没有关系,只要把孩子的代价加上切断代价就是这样做的代价了,也就是 dp[b_{i}][0]+cost(a \rightarrow b_{i})(孩子部分没有和黑点相连的情况下切断)和dp[b_{i}][1]+cost(a \rightarrow b_{i})(孩子部分有和黑点相连的情况下切断)。
      • 比较这三种选择,取最优就是局部最优解了。
    • dp[a][0]=\inf
      黑点不可能不和黑点相连,所以这里用inf屏蔽掉这种选择。
  • 如果a是一个白点:
    • dp[a][1] = \min \left\{\begin{matrix}dp[a][0]+dp[b_{i}][1]\\ dp[a][1]+dp[b_{i}][0]\\ dp[a][1]+dp[b_{i}][1]+cost(a\rightarrow b_{i})\\ dp[a][1]+dp[b_{i}][0]+cost(a\rightarrow b_{i})\end{matrix}\right.
      因为当前节点是白色,我们想要让他变成连着黑色的情况,这样的话有四种操作可以选:

      • 假如截止目前和根部连接的所有孩子都不包含黑点,我们可以让现在的这个孩子部分以含有黑点的形态和根部连接,使根部变成有黑点的情况。这就是dp[a][0]+dp[b_{i}][1]
      • 假如当前的根部已经连有黑点,为了满足要求,新联入的部分不可以再包含黑点,这就是dp[a][1]+dp[b_{i}][0].
      • 假如孩子部分被切断,这样的话就无所谓孩子长成啥样了,只要算一下代价就可以了,也就是 dp[b_{i}][0]+cost(a \rightarrow b_{i})(孩子部分没有和黑点相连的情况下切断)和dp[b_{i}][1]+cost(a \rightarrow b_{i})(孩子部分有和黑点相连的情况下切断)。
      • 这四种选择里面选最优的就好了。
    • dp[a][0] = \sum\min \left\{\begin{matrix}dp[b_{i}][0]\\ dp[b_{i}][0]+cost(a \rightarrow b_{i})\\ dp[b_{i}][1]+cost(a \rightarrow b_{i})\end{matrix}\right.
      当前节点是白色,我们想要让她不要根任何黑色连上,这样的话有3种选择:

      • 当前讨论的孩子部分没有和黑色连着,我们可以放心的把这部分连到根部,这就是dp[b_{i}][0]
      • 切断了和孩子部分之间的连接,也就是 dp[b_{i}][0]+cost(a \rightarrow b_{i})(孩子部分没有和黑点相连的情况下切断)和dp[b_{i}][1]+cost(a \rightarrow b_{i})(孩子部分有和黑点相连的情况下切断)。(其实我已经复制了这一段两遍。。。)
    • 注意这两个dp[a][0]dp[a][1]要同时处理,因为这里面有一个从“刚才”dp[a][0]到“现在”dp[a][1]的转移。

方程想好之后,DFS深入叶子部分,在返回的时候处理好dp数组就可以了,最后我们要在dp[0][0]dp[0][1]之间取个最小的,因为你所制定的根在最优解的时候连不连黑点并不知道。

代码

 

一份仅用于学习的伸展树C实现

这份代码来自于以前的Wikipedia,遇到这份代码也许是缘分吧,虽然实现上十分的冗长(好多好多的废话),但是也正因为如此这份代码展示了伸展树操作的每一个细节,尽管没什么实用价值,但是拿来理解splay是很好的。我自己抄了一遍同时加上了注释。

 

Scroll to top