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}),符合题目限制。

至此本题圆满解决。

实现

 

BZOJ 2780 / SPOJ JZPGYZ Sevenk Love Oimaster

题意

给出一系列的字符串,我们把这些串叫母串,然后给你若干字符串,对于每一个字符串,你要求出在多少个母串中可以找到和给出的字符串相同的母串的字串。

思路

子串问题,要借助后缀系列解决,这个题使用了后缀自动机。但是通常意义的后缀自动机都是针对一个母串建立的,现在我们手里有一堆母串,这时候就需要我们进行活用,来创建“广义后缀自动机”,这个自动机将可以接受母串集合里所有的字串。

广义后缀自动机的建立方法其实是在一般的自动机创建基础之上,增加了一些东西。构造后缀自动机的方法是增量法,构造广义后缀自动机的方法也是一样的,但是我们从第个二串开始,一位一位增量的时候,我们有可能会用到构造到一半的自动机的某些节点或者某些转移边。对于当前将要加入的mxn(最长可接受字串长度)值,和当前追加节点时的last,如果last有一条转移边可以用,而且即将加入的新节点的mxn值正好等于last的mxn+1,这说明既存的节点和我们将要加入的节点是等价的,这一轮的追加到这里就可以结束了。如果存在转移边,但是转移边连着的节点mxn值并不是last的mxn+1,这个时候就需要我们使用在平常构造后缀自动机中使用的“拆点”方法。复制既存的节点作为符合我们mxn要求的节点,调整parent关系和所有自动机上父亲节点的转移关系,就像我们在平常构造自动机时为了防止mxn异常缩短采用的“拆点”方法一样。如果last节点不存在可用的转移边,这时候按照普通的增量法处理就可以。(如果觉得费解,不妨直接参考我的MultiSAM_Append()方法)。

创建完广义后缀自动机,这还只是个开始。接下来我们要提取出自动机中的所有的parent关系,创建parent树。我们注意到,在parent树中,一个节点的子树代表的是以这个节点为后缀的全部字串。举个例子就是,对于“banana”的”ana”代表节点(mxn值3),他的子树就代表了”ana“,”nana“,”bana“,”anana“,”banana“,这一系列字串。这一特性有什么用呢?

注意到题意,我们要找到给出的串在多少个串中匹配,如果我们按照正常的方法在广义后缀自动机上完整地匹配这个串(如果匹配有中断,那就说明这个串不存在于母串集合的字串当中),这个时候转移到的最终状态对应节点的parent树的子树,就是在母串集合中所有的以给出的串为后缀的字串。如果我们给parent树上的每一个节点挂一个列表,标记这个节点都被哪些字符串利用了,这样只要我们逐一统计子树中的每一个节点,就可以知道当前给出的串在几个母串中存在,问题就可以解决了。

但是对于每一棵子树都统计一次,复杂度很大,显然需要再优化。优化的方法就是“DFS序把树压平”然后“离线处理”。首先遍历parent树,纪录每一个节点进入时的DFN和出去时的DFN,从进去到出去这两个DFN之间的所有节点(包括出入两个节点)显然就是parent的子树了。现在我们的问题就转变为了在某个数组上一段给定的区间求有多少个不同的数字,而且还是离线处理,这种问题可以使用一种O(n)的处理方法,详情可以参考BZOJ 1878 HH的项链

问题到了这里,终于是完美地解决了。

 

代码

 

SPOJ SUBLEX Lexicographical Substring Search

题意

把一个字符串所有的不同的字串全拿出来,按字典序排序,第k小的字符串是什么样子的呢?

思路

字串问题当然是后缀自动机了。对于给出的字符串,建立一个后缀自动机,然后对后缀自动机对应的状态图进行一次拓扑排序,每个节点的深度就是节点上携带的mxn(当前状态对应的字串最长为多少位)。接下来我们从深度最大的节点开始往根部处理每一个节点,我们要求出的就是对于每个能走的边,所有接下来的以这条边对应的字母开头的字串数目,而节点上面存的是节点出边的边权之和。这样我们就得到了一个处理好的图,我们只要在这个图上面搜索,逼近k值就可以了。

因为SPOJ卡常数特别严重,所以拓扑排序要使用计数排序的方法,而且要开额外的数组纪录每一个节点所有的孩子来加快之后的搜索速度。

代码

 

SPOJ LCS Longest Common Substring

[等待填坑]

 

SPOJ LCS2 Longest Common Substring II

[详细题解等待填坑]

SPOJ真是业界奇葩

 

FZU 2159 WuYou

Proceed big numbers A and B,A and B have same digits(Both A and B have no prelude zeros),A contains uncertain digits marking ‘?’.Find a largest A to make A < B.

策略是先从前往后扫描一遍已知的数位,如果相等的话,放过当前位,如果当前位a>b这时停止扫描,纪录扫到的位置i,记录状态为1,如果当前位a<b这时停止扫描记录扫描到位置i,状态为2.

对与状态1,如果我们不能在i之前找到一个‘?’使这一位正好比b少1,那么无解,找到了的话,就记录这个新位置为i,跳到状态2。

对于状态2,只要令i左边的数位和B一样,右边的数位都是9就可以了。

都完成之后,做一下最终检查,注意只有一位数时首位可以为0,A!=B就可以了。

CodeForces 126B Password

整个比赛都在搞这个题,还不知道哪里不对。

其实这个题如果用kmp做主要卡在这么几个地方:
首先要读懂题,aaaaaa的对应答案是aaaa,四个a,也就是说prefix是在不包括最后一个字符的范围内检索,suffix是在不包括第一个字符的区域检索,中间那个则是在既不包括第一个字符也不包括最后一个字符的范围内检索。
然后Next数组要机智地用好,就是说当前模版串失配之后,机智的方法是利用当前模版串的next数组,直接构造出下一个可能的模版串,而不是一次只删掉末尾的一个字符,再重新扫描这种暴力方法。

其实这个题上面两点我都没想到,更要命的是我的next数组构造方式就存在问题。

在这里重申一下正确的next数组构造方式,首先next[0] = 0,next[1]  = 0(next[0]=-1也是可以的),这个没什么好说的,然后要注意,在进行到中间的时候,首先检查next[当前位]对应的字符是不是和现在的字符相等,相等就在当前next的基础上+1,赋值给下一位的next,如果没有匹配上这个时候不是简单的归零,而是要把当前的比较位置更新成当前比较位置对应的next值的对应位置,也就是一定要迭代回去。(我就是因为没有迭代,next数组整个就是错误的)

UVa 11488 Hyper Prefix Sets

Trie树,静态方式的话(用数组保存节点),可以比较简单的实现遍历,动态方式(new+指针)还要写搜索。。。

POJ 2503 Babelfish

这个是拿map水过去的版本,其实应该自己手写一个的。。。

HDU 1062 Text Reverse

请替我问候出题人全家。。。

这个题绝对是良/心/题;为啥你会黄呢?给你个样例吧:
—-watashi-wa-saiko–desu!—-
—-ihsataw-aw-okias–!used—-

上面的-都是空格嗯。。。

Scroll to top