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

 

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,既可以完成初始化,也可以无效化所有无效状态。

代码

 

LA2678 Subsequence

题意

给出一个由n个整数组成的数列,要你求长度最短的连续序列,使得序列中所有元素的和大于等于S。

思路

单调性优化,或者说是尺取法。

暴力O(n^3)显然无法接受,套用前缀和优化再枚举O(n^2),还是无法接受。

在套用前缀和的基础上,可以枚举终点,二分查找起点,这样是O(nlogn),可以过了。

然而还有更好的办法,设两个指针,表示连续区间的左端点和右端点,一开始不断右移右端点,直到序列大于等于S,记录长度。然后右移左端点,再开始不断尝试右移右端点,直到条件再次满足,停下纪录,右移一下左端点。。。如此往复,直到右端点无法右移,且左端点无论怎么移动也无法满足条件。

这就是尺取法(名字来源于挑战程序设计竞赛),CF上面也叫Double Pointers,是一种基于单调性的优化手段。

代码

前缀和+尺取

前缀和+二分

 

LA3905 Meteor

题意

请参考LRJ白书第一章例题20

思路

扫描线。

这个题分为两部分,首先是要求出每一颗流星划过取景框的时间区间,这一步反而是这个题最复杂的地方,因为要讨论许多种情况,具体的讨论策略可以参考下面的代码。

求出来所有的区间之后,问题转化为选出一条线,使得这条线穿过的区间最多,这里就是扫描线算法派上用场的时候了。其实实现很简单,就是对于每个区间的两个端点,分别创建一个表示起始的事件和一个表示结束的事件,然后把所有事件按照出现的时间排序,接下来从小往大检查,遇到开始事件的时候计数器+1,遇到结束事件的时候计数器-1.

这里有一个问题,如果开始事件和结束事件恰好位于同一时点,怎么办?注意到我们的区间都是开的,这样我们只要优先处理结束事件,就不会导致解偏大了(这里面的逻辑需要自己试着理解一下)。

代码

 

UVA 11549 Calculator Conundrum

题意

给出一个数,你要对他反复平方,平方完之后总是取运算结果的前n个十进制位(如果结果大于n位)作为答案,然后对这个答案继续进行刚才的操作。

这是一个循环的过程,你要找出在这个循环节中最大的数。

思路

首先是循环节这一点,意识到形成循环节并不难。从理论上来证明:我们可以设定一个运算#表示相乘取前n位这一操作,初始值为a,a#1=a,1为单位元,N为所有k及k位以下整数组成的集合,两个数做运算得到的结果必然属于N,则<N,#>构成一个有限群,<a^x>必然构成循环群。

取前n位这一操作可以用字符串流,但是那样常数非常大,所以还是考虑利用数学运算来实现,这样会提高速度。

找出循环节的方法有两种,一种是开一个set,算一次insert一次,如果碰到算过的就停下。还有一种是Floyd判圈法,也就是同时维护两个数A和B,每一次令A=A^2,B=B^3,也就是B总是会比A多走一步,这样如果有环,A和B一定会相遇,在相遇时停下。

代码

Floyd判圈法,数学方法求前n位。

 

UVa 11078 Open Credit System

题意

给出一个整数组成的序列,求两个整数A和B,其中A在数列的位置在B前面,令A-B最大,输出这个最大值。

思路

利用问题的单调性优化的典型例子。

暴力是O(n^2)的,显然无法通过。注意到A始终在B的前面,而且一定是A-B,也就是说对于每一个B,只要找到在它前面最大的A就可以了,不妨考虑随着B逐渐后移的同时,维护前面A的最大值,这样做的复杂度是O(n)的,很完美地解决了这个问题。

这种思想经常会被用在其他问题中作为一个需要优化的环节。

代码

 

 

Scroll to top