Codeforces 666C Codewords

题意

已知一个字符串 s ,有 m 个询问需要你回答。

对于每个询问,有两种可能性:

  • 1型:给你另外一个字符串 s' ,然后令s = s'。(即用新串更新当前的s
  • 2型: 给你一个整数n,你要回答:可以构造多少种不同的长度为n的字符串p,使得字符串 s 是字符串 p 的一个子序列,只考虑英文小写字母.

进一步解释:

  • 子序列:假如有一个字符串a,我们去掉其中的一些字母(只能“去掉”,而不能交换字母的位置),得到另外一个串b,我们把b称为a的子序列。
  • 举个例子: "hhhl"可以是"hahaschool"的子序列,"sik"可以是"suika"的子序列。

思路

首先,你需要注意到其实字符串s的内容并不重要,影响答案的是字符串s的长度。

我们来考虑这样的一种思路:

假设我们构造的串是psp的子序列,我们设定:sp中的出现位置必须是字典序最小的。直白一点的说法:sp删除一些字母得到的,我们强制删除字母的时候,在连续相同的一段字母中,必须从右往左删。

举两个例子方便理解这种想法:

s = "hahl" p = "hahaschool""hahl""hahaschool"中的对应位置必须是1、2、3、10(下标从1开始)。

s = "abad" p = "aaabbbaaaddd""abad""aaabbbaaaddd"中的对应位置必须是1、4、7、10(下标从1开始)。

有了这种想法我们就可以把s在固定的p中的对应位置关系唯一地确定下来。同时我们得到了这样的结论:

假设s的每一位在p中对应的位置为p_i,字符串s的内容是s_i,那么s_{k+1}一定不会出现在p的第p_k位到p_{k+1}-1位,因为如果不这样的话,sp中的出现位置就不是“字典序最小”的了。

有了这个结论,我们就有了初步的想法,我们首先选择sp中的出现位置,这个很简单,就是\binom{n}{|s|}(其中n是要构造的p的长度,|s|是s的长度),接下来,对于每种s在p中出现位置的分布,在第p_{|s|}位之前的未填充空位,都可以填入25种字母(参见我们刚才得到的结论),在之后的空位,都可以任意填入26种字母。

这样,如果我们枚举s在p中出现的最后位置p_{|s|}(下面用k表示),我们就可以算出答案,使用下面这个式子:

ans=\sum_{k=|s|}^{n}\binom{k-1}{|s|-1}25^{k-|s|}26^{n-k}

很显然如果直接拿这个式子出答案是O(n^2)的,不满足时间限制,我们要想些办法。

观察一下上面的式子我们可以发现,可以提出26^n这一项,这样对于相同的|s|,不同的n的询问,我们只需要做一次O(n)的计算就可以全数回答。这提醒我们离线处理询问:把所有询问按照|s|为第一基准,n 为第二基准进行排序,依序处理,再按出现顺序排序,依序输出。

这样做是可行的,因为|s|最多有\sqrt{n}种(考虑极端情况:{|s|}_1 = 1,{|s|}_2 = 2,{|s|}_3 = 3,…,根据等差数列求和公式,项数最多只能到\sqrt{100000}),对于每种不同的|s|都要做一个O(n)的处理,所以总复杂度为O(n\sqrt{n}),符合题目限制。

至此本题圆满解决。

实现

 

Codeforces 295D Greg and Caves

题意

你有一个n*m大小的棋盘,n行,m列,行号列号都从1开始,行从上到下数到n,列从左到右数到m,棋盘的每一个格子可以是黑色或者白色。

当满足全部下述条件的时候,认为棋盘上出现了一个”Cave“:

  • 存在一个线段[l,r] (1 <= l <= r <= n),使得l,l+1,l+2,...,r这些行都有且仅有两个黑色格子,其他行不存在黑色格子。
  • 存在一个行号t (l <= t <= r),使得:
    • 对于任意存在黑色格子的行r,把这行的黑色格子对应的列号和黑色格子之间的列号加入一个集合, 称之为S(r)
    • 任取t及t之上的两个有黑色格子的行,令上方的行为u,下方的行d,则S(u)S(d)的子集。
    • 任取tt之下的两个有黑色格子的行,令上方的行为u,下方的行为d,则S(d)S(u)的子集。

你要输出有多少染色的方案,使得棋盘出现一个“Cave”,答案模1000000007

思路

翻译一下题意,就是让我们找一种染色方案,让棋盘上出现下面这样的图案(下图中n = m = 5 ,l = 3, r = 15, t = 8)。

295D

可以发现,这个图案可以以t行为界分拆为上下两个部分,不妨令hf[h][w]表示得到高度为h的,底部两个黑块宽度必须为w的,每一行都有黑块的,半个图案的染色方案数。

我们可以很容易发现如下的递推关系:

hf[h][w] = {hf[h-1][w] + 2\times hf[h-1][w-1] + 3\times hf[h-1][w-2] +4\times hf[h-1][w-3] + ... + w\times hf[h-1][1]}

即:

hf[h][w] = \sum_{k=1}^{w} k\cdot  hf[h-1][w+1-k]

考虑同一高度的相邻两项之差:

hf[h][w] - hf[h][w-1] = \sum_{k=1}^{w} hf[h-1][k]

这样,我们一行行地计算hf的值,一边维护每一行的前缀和,一边算下一项,这样可以用O(n^2)的时间完成预处理。

接下来我们考虑如何把两个一半的图案合成一个,我们令al[h][w]表示得到高度为h,最宽处宽度为w,每一行都有黑块的图案的染色方案数,我们有:

 al[h][w] =\sum \left\{\begin{matrix} {hf[1][w] \cdot (2\times hf[h-1][w-1] + 3\times hf[h-1][w-2] + 4\times hf[h-1][w-3] + ... + w\times hf[h-1][1])} \\ {hf[2][w] \cdot (2\times hf[h-2][w-1] + 3\times hf[h-2][w-2] + 4\times hf[h-2][w-3] + ... + w\times hf[h-2][1])} \\ {hf[3][w] \cdot (2\times hf[h-3][w-1] + 3\times hf[h-3][w-2] + 4\times hf[h-3][w-3] + ... + w\times hf[h-3][1])} \\ ... \\ {hf[h][w] \cdot (2\times hf[0][w-1] + 3\times hf[0][w-2] + 4\times hf[0][w-3] + ... + w\times hf[0][1])} \end{matrix}\right.

即:

 al[h][w] = \sum \left\{\begin{matrix} hf[1][w]\times \sum_{k=1}^{w-1} (k+1)\cdot hf[h-1][w-k] \\ hf[2][w]\times \sum_{k=1}^{w-1} (k+1)\cdot hf[h-2][w-k] \\ hf[3][w]\times \sum_{k=1}^{w-1} (k+1)\cdot hf[h-3][w-k] \\ ... \\ hf[h][w]\times \sum_{k=1}^{w-1} (k+1)\cdot hf[0][w-k] \end{matrix}\right.

为了让式子更简洁,我们令rc[h][w] = \sum_{k=1}^{w-1} (k+1)\cdot hf[h][w-k],这样的话,我们就有:

al[h][w] = \sum_{k=1}^{h} hf[k][w]\cdot rc[h-k][w]

很明显这个式子是一个卷积,如果我们可以预处理出rc的值,就可以使用FFT进行快速运算。我们发现rc的递推关系和hf的递推关系非常相似,我们依然考虑同行相邻两项的差值:

rc[h][w] - rc[h][w-1] = hf[h][w-1] + \sum_{k=1}^{w-1} hf[h][w-k]

这样我们依然采用一边计算一边维护前缀和的方法,可以在O(n^2)的时间完成rc的预处理。

预处理好rc之后,就是计算卷积了,因为题目要求模1000000007,我们需要采用NTT+CRT的方式实现任意模空间下的卷积(具体实现原理不是我们的讨论范围),这样的话,在最恶劣情况,我们需要做18000次4096点NTT,单次NTT耗时几毫秒,超时无法避免,我们只能考虑进一步优化。

我们继续考虑,令dw[w]表示最宽处宽度为w,高度范围在1 \sim N的图案,有多少方案可以作成,那么我们有:

 dw[w] = \sum \left\{\begin{matrix} N\cdot al[1][w] \\ (N-1)\cdot al[2][w] \\ (N-2)\cdot al[3][w] \\ ... \\ 1 \cdot al[N][w]  \end{matrix}\right.

al打开,就有:

 dw[w] = \sum \left\{\begin{matrix} N\times hf[1][w]\cdot rc[0][w] \\ (N-1)\times (hf[1][w]\cdot rc[1][w] + hf[2][w]\cdot rc[0][w]) \\ (N-2)\times (hf[1][w]\cdot rc[2][w] + hf[2][w]\cdot rc[1][w] + hf[3][w]\cdot rc[0][w]) \\ ... \\ 1\times (hf[1][w]\cdot rc[N-1][w] + hf[2][w]\cdot rc[N-2][w] + ... + hf[N][w]\cdot rc[0][w]) \end{matrix}\right.

我们把dw[w]重新整理一下:

 dw[w] = \sum \left\{\begin{matrix} hf[1][w]\times (N\cdot rc[0][w] + (N-1)\cdot rc[1][w] + (N-2)\cdot rc[2][w] + ... + 1\cdot rc[N-1][w]) \\ hf[2][w]\times ((N-1)\cdot rc[0][w] + (N-2)\cdot rc[1][w] + (N-3)\cdot rc[2][w] + ... + 1\cdot rc[N-2][w]) \\ hf[3][w]\times ((N-2)\cdot rc[0][w] + (N-3)\cdot rc[1][w] + (N-4)\cdot rc[2][w] + ... + 1\cdot rc[N-3][w]) \\ ... \\ hf[N][w] \times 1 \cdot rc[0][w] \end{matrix}\right.

如果比较敏感的话应该已经发现突破口了,我们再整理一下:

dw[w] = \sum_{i=1}^{N}hf[i][w]\sum_{j=0}^{N-i}((N-i-j+1)\cdot rc[j][w])

还没看出来?再令tr[i][w] = \sum_{j=0}^{N-i}((N-i-j+1)\cdot rc[j][w]),这样:

dw[w] = \sum_{i=1}^{N}hf[i][w]\cdot tr[i][w]

而且我们还可以发现hf, rc, tr它们的递推关系都是差不多的,也就是说对于tr我们继续采用考虑相邻两项差的策略:

tr[i][w] - tr[i-1][w] = \sum_{k=0}^{N-i} rc[k][w]

这样我们可以用O(n^2)的时间把tr搞定,这样的话,计算全部的dw的值也是O(n^2)时间了。

计算好表示定宽度不定高度的图案数的dw之后,接下来我们放宽到不定宽度不定高度的图案数,也就是答案,我们有:

ans = \sum_{w=2}^{M}(M-w+1)\cdot dw[w]

这样我们绕了一大圈终于把答案算出来了,总复杂度O(n^2),本题至此解决。

实现

NTT+CRT做法

注意这份代码因为常数过大无法通过,但是答案是正确的。

正解

参考

  1. kmjpさん(日本語注意):
    http://kmjp.hatenablog.jp/entry/2014/09/22/0900
  2. Zeyu_king:
    http://blog.csdn.net/zeyu_king/article/details/44040749

 

给中级者的动态规划教程

认识更多模型

区间DP

POJ 2955 Brackets:最简单的区间DP,括号序列

LA4394 String Painter:两层区间DP,难度较大

概率DP

POJ 3744 Scout YYF I:概率型递推配合矩阵快速幂加速

POJ 2096 Collecting Bugs:优惠券问题的二维情形

状态压缩DP

UVA 10911 Forming Quiz Teams:最优配对问题

LA3725 Hie with the Pie:TSP问题

树DP

POJ 1655 Balancing Act:求树的重心

Codeforces 461B Appleman and Tree:最大独立集问题的变种

 

 

LA4394 String Painter

题意

给定两个长度相等,只有小写字母构成的字符串s和t,每步可以把s的一个连续子串“刷”成同一个字母,问至少多少步才能把s变成t。

思路

两层区间DP。

首先忽略原始串s,只去看目标串t,设dp1[i][j]表示从什么都没有的情况下利用刷子规则构造出目标串t的i到j这一段所需要的最小操作次数。这里着眼于“最后一次操作”进行阶段的划分。

dp1的状态转移:

  • dp[i][j] = dp[i+1][j ] + 1
    先默认最后一次操作是只刷出最新那个字符。
  • 令k是i和j中间的某个位置,t是目标串,如果t[i] == t[k]
    尝试用dp[i+1][k] + dp[k+1][j]更新dp[i][j]
    因为i处字符等于k处字符,在构造i+1到k这个区段的时候,可以在刷k处字符的同时“顺便”把i位置也给刷了。
    注意这里不可以写成dp[i+1][k-1] + 1 + dp[k+1][j],考虑反例” /e(i对应)/ee/e(k对应)/… “,在这里dp[i+1][k-1]是1,用这种错误的算法dp[i][k]部分会变成2,但实际上应该是1。

接下来引入原始串s,令dp2[i]表示把原始串1到i构造成目标串1到i的部分所需要的最小的操作次数。这里有状态转移:

  • 默认dp2 = dp1[1][i]
  • 如果s[i] == t[i]
    尝试dp2[i] = dp2[i-1]
    否则尝试dp2[i] = dp2[i-1] + 1

    这里的意思是如果在第i位两个串对应字符相等,可以选择无需对这一位进行操作

  • 令k是1到i之间的位置
    尝试dp2[i] = dp2[k-1] + dp1[k][j]

    这里的意思是假设最后k位使用不考虑原始状态的构造方法,前面继承最优解。为什么要这样做?考虑fabcf这样的区间,一种较好的策略是先都刷成f,然后分别刷好abc,如果你选择这么做了,相当于已经无视了原来串的样子,因为第一步已经将全部中间字符都刷成f了。

代码

 

LA3725 Hie with the Pie

题意

经典问题:TSP。

给出了n个城市,求一条最短的路径,使得经过每个城市一次且仅一次,最后回到起点。

思路

状态压缩DP。分析问题可知道是一个多阶段决策过程,每个阶段“状态”包括了可以用已经走了哪些点,和当前站在哪个点,决策就是接下来走哪个点。

状态表示:dp[二进制位,表示目前已经走过那些点][最后走的点的序号] = 从起点出发走过的最短路程

答案:min{dp[走过全部点的状态][枚举各个可能的最后走的点i] + dis(i,起点)}

边界:dp[0][起点] = 0,其它都是INF

状态转移:用dp[S][i] + dis(i,j) 去尝试更新dp[S|j][j]

代码

 

UVA 10911 Forming Quiz Teams

题意

经典模型“最优配对问题”,给出了平面上若干个点,你要把牠们两两配对,使得每一对中两点距离之和最小。

思路

分析问题:我们发现,本问题可以着眼于“最后一次配对”,是一个多阶段决策。不妨考虑当最后一次选择拿i号点去和j号点去配对,得到了某种状态时可以得到的最优解。

状态表示:dp[当前状态下各个点是否已经配对][最后一次配对的点i][最后一次配对的点j]

我们发现这个状态设的太繁了,假如我们要配对a和b这两个点,那么在所有的配对状态里面都要算入a和b的距离,在所有没配对状态里都不可以算入a和b的距离,后两个维度强行决定了一组点的配对情况,然而并没有什么意义,因为后两个维度的信息已经包括进了第一个维度里,我们只要想办法让第一个维度可以表达出决策的“分阶段”特性,能够识别出最后一步是什么就可以。

于是我们重设状态:dp[当前状态下各个点是否已经配对]并且规定在每个状态中,最低位为1对应的那个点是我们最后一次操作的点。

这样有状态转移:dp[S] = min{dis(i,j) + dp[S^i^j]} 在这里S是二进制表示的状态,i,j是假定的最后一次配对的点对,其中规定i一定是S中最低位的那个点,dis表示求距离,S^i^j表示将二进制表示的状态中i,j对应的位设成零之后得到的二进制状态

代码

 

POJ 2955 Brackets

题意

给出一个由小括号喝中括号组成的括号序列,定义正规括号序列为(),[],(s),[s],其中s也是正规括号序列。求最长正规括号序列的长度。

思路

考虑区间DP,设计状态时着眼于“最后一次加括号”。

状态表示:dp[i][j] = 从 i 到 j 的(包含i,j)最长的括号序列长度。

状态转移:

  • dp[i][j] = dp[i][j-1] 继承上一个区间的结果
  • 令k为i,j之间的一个位置,str是给出的括号串(令下标从1开始)
  • 如果str[k]与str[j]正好是一对匹配的括号,可以考虑在最后一步放这个括号,用dp[i][k] + 2 + dp[k+1][j-1]尝试更新dp[i][j]

答案:dp[1][len]

初始化:直接令整个dp数组都为0,既可以完成初始化,也可以无效化所有无效状态。

代码

 

POJ 2114 Boatherds

题意

给出一棵树,树边带有边权,问你能不能找出一条路径使得路径边权之和正好等于给出的k值。

思路

和这个题非常像,只不过题意从计算有多少点对之间距离小于k换成了判断有没有一条路径等于k。但实际上可以用一套思路解决。

代码

 

POJ 1987 Distance Statistics

题意

给出一棵树,和树上两点之间的边权大小,要你快速回答出树上有多少不同的点对使的这对点之间的距离至多为k。

思路

典型的点分治问题。

当考虑一棵有根树中有多少点对的距离小于等于k时,可以求出所有节点到根部的距离,然后使用二分,或者尺取的方法得到有多少对点之间的距离小于等于k。但是在上面的计算过程中我们想要求的是经过根部的符合要求的点对数量,但实际上多算入了一些并不符合要求的点,同时也漏掉了不经过根部的符合条件的点对。

所以我们可以这样看:一棵树的符合条件点对数=上面所述方法找出的点对数-各个子树中两点间距小于等于(k-2e)的点对数目(e是根部到孩子的树边的边权)+各个子树符合条件的点对数

上面的式子是递归的,这是一个树分治(点分治)策略。

在实现树分治的时候,一定要注意只有配合了重心的点分治才能达到O(nlogn)的复杂度,否则会面临特殊情况(比如链)退化到O(n^2).

代码

 

 

POJ 3107 Godfather

题意

变相考察树的重心。

思路

请参考这个题和/或这个题

代码

 

Scroll to top