摘要: 【例题】[SDOI2011]染色(注:数据范围木有交代,应为:点数N<=105,操作数M<=105,所有的颜色C为整数且在[0, 109]之间。一、树的路径剖分当中点权型(点上有权值而边上木有)的处理办法:(1)找重链建线段树的时候,w0中存储tot+1个数,为该重链自上而下的各点的权值(例题中为颜色);(2)除了父边是轻边的叶结点之外,树中的每个结点都属于且仅属于一条重链(根据定义得...  阅读全文

posted @ 2012-01-12 20:44 Mato_No1 阅读(486) | 评论 (0)编辑 收藏

     摘要: 原题地址【有关树的路径剖分的东东在网上介绍的太多了……】常见的路径剖分的方法是轻重边剖分,即把树中的边分为轻重两部分,方法:设SZ[i]为以i为根的子树的大小(结点总数),则若点x不是叶结点,则其子结点中SZ值最大的(注意,有多个SZ值最大的子结点应任选一个,只能选一个,防止出现重链相交,引发歧义)点y,边(x, y)称为重边,其余的边都是轻边。首尾相连的重边称为重链(注意...  阅读全文

posted @ 2012-01-03 16:41 Mato_No1 阅读(1477) | 评论 (2)编辑 收藏

【本沙茶以前曾经搞过矩形的面积并、周长并问题,当时几乎是抄神犇代码的,根本木有理解,现在在看了扫描线以后理解一些了】
“扫描线”严格来说不是算法,而是一种思想,它在解决很多几何问题或者矩阵问题中有大用。所谓“扫描线”,就是用一条假想的直线(一般是水平或者竖直的)沿x轴(或y轴)方向扫过整个平面,在此过程中,每当发现有特殊事件(比如插入、删除事件等),就执行这一事件。一般来说,它需要配合数据结构进行加速,常用的数据结构有线段树、平衡树、树状数组、堆、凸多边形集合等。

【1】矩形的面积并和周长并问题:
这个在以前总结的那一篇里面曾经说明过,这里只是补充一下。

对于面积并,可以假想一条水平直线沿y轴正方向扫过整个平面,每当遇到矩形的上下边界,就插入或删除一条线段(上边界为插入,下边界为删除),在每两个相邻上下边界之间得到覆盖面积为:目前插入(尚未删除)的所有线段覆盖的总长度乘以两边界间的距离。显然,求前者需要用离散化(横坐标)+线段树实现。

这里讲一下离散化的步骤和易疵点:首先将要离散化的数据(设为A数组)存储在一个数组B里,然后对B排序(一般是递增排序)、去重(方法:若B长度为0则不需去重,否则B[0]保留,从B[1]开始,若B[i]>B[i-1]则保留B[i]否则跳过B[i]),得到一个新的数组B0,最后,再对原来的A数组中的每个元素在B0中二分查找,找到其位置即可。显然,对N个数据离散化时间复杂度为O(NlogN),具体实现时,可不设B0,直接存在B里面(见代码)。易疵的地方主要是B的长度为0的情况。
re(i, n0) B[i] = A[i].x;
qsort(B, n0, 
sizeof(B[0]), cmp);
= 1; re2(i, 1, n0) if (B[i] > B[i - 1]) B[n++= B[i];
re(i, n0) A[i].x 
= find_x(A[i].x);
其中n0为数据个数,n为去重后的数据个数(也就是离散化后的编号范围,很重要的!),find_x为二分查找过程。

对于周长并可以这样理解:照样是水平直线沿y轴正方向扫过整个平面,照样是遇到矩形的上下边界就插入或删除,这样,周长的水平部分是很好得到的,只要统计每两个相邻上下边界的线段覆盖总长之差即可,对于竖直部分则需要统计被线段覆盖的端点个数——或者说,需要统计至少作为一条目前插入线段的端点,且木有被任何一条线段部包含的端点个数(因为只有这些点所延伸下来的竖直线段有可能作为周长的竖直部分)。维护方法:给每个结点设立ss、lbd与rbd,分别表示该结点区间内这种点的个数,以及该线段区间的左右端点是不是这种点。lbd=LCH.lbd; rbd=RCH.rbd; ss=LCH.ss+RCH.ss-2*(LCH.rbd || RCH.lbd)(因为我们需要的是线段树而不是点树,因此其中的每个叶结点表示的实际上是一条单位线段,而不是一个点,这样,LCH区间的右端点与RCH区间的左端点其实是同一个点,如果它们都是这种点,则都不能算,因为被包含在内部了)。例外的是,如果某个结点区间完全被某条插入线段包含,则ss为2,lbd、rbd均为1(这个结果可能不正确,因为可能左右端点被包含在内部,因此,整棵树上只有根结点的ss值是绝对正确的ss值,其余结点都需要特判)。这样,根结点的ss值就是这种点的个数,乘以两相邻上下边界的距离就是之间的竖直部分总长度。

代码:
面积并(HDU1542)
周长并(HDU1828)

(此外,周长并还有一种更容易理解的算法:就是先求出水平部分总长后,将所有的矩形旋转90度,再求一次水平部分总长,这就是原来的竖直部分总长了)

【2】应用:
PKU2482

posted @ 2011-12-25 16:10 Mato_No1 阅读(382) | 评论 (0)编辑 收藏

原题地址
这是一道线段树操作的极品题,因为它的4个操作刚好覆盖了线段树操作问题的3种处理思路,可以说是把线段树操作的全部内容都包含进去了。

线段树是一种静态的数据结构,因为一棵线段树一旦建成,其形态就永远不会发生变化,改变的仅仅是结点上记录的各种信息的值。因此,对于线段树操作,核心问题也就是如何维护和处理这些信息。总的来说,对于线段树结点信息的维护和处理,有以下3种基本思路:
(1)左右归中型:
所谓左右归中,就是用左右子结点存储的信息来得到父结点存储的信息的值,这是最常见的线段树维护方法。举一些简单的例子:比如结点的SUM域表示该结点区间上所有元素的和,那么这个域维护的方法就是“父结点SUM=左子结点SUM+右子结点SUM”,再比如结点的MAX/MIN域表示该结点区间上所有元素的最大/小值,那么维护方法就是“父结点MAX/MIN=max/min{左子结点MAX/MIN,右子结点MAX/MIN}”。这种维护方法也比较简单,只要在每次对子结点进行修改之后upd一下就行了(对于那些自顶向下递归,而且涉及到改值的操作,在递归完左右子结点后一定要记得upd一下),在这之中有一个很重要的思想就是“左右连续段”思想:如果题目中要求任意一个区间内的具有某种性质的最长的连续序列(也就是子区间),比如最长连续上升子序列、01值问题中连续的0段或者非0段(在具体问题中就是连续的空闲段或者占用段)等,可以在每个结点上维护三个域:lS、rS和S,分别表示该结点区间左端(从区间的最左端开始的)具有这种性质的最长连续序列的长度,该结点区间右端(到区间的最右端结束的)具有这种性质的最长连续序列的长度和该区间内具有这种性质的最长连续序列的长度(也就是要求的那个东东),则维护方法为“父结点lS=左子结点lS(左子结点lS<左子结点len)或左子结点len+右子结点lS(左子结点lS=左子结点len),父结点rS类似,父结点S=max{左子结点S,右子结点S,左子结点rS+右子结点lS}”,此外,由于要求的这个区间可能被拆成多个连续的结点区间,因此需要按顺序合并这些区间,合并的方法是:设立S0和S1,S0表示不保证能延伸下去的区间长度,S0=上一个区间的S1+本区间的lS;S1表示可以延伸下去的区间长度,S1=上一个区间的S1+本区间len(如果本区间整个都是满足条件的,即S=len)或本区间的rS(本区间不都是满足条件的,即S<len),取过程中所有S0和区间S的最大值即为结果。
在HDU2871中,应用左右归中的方法维护的信息就是“最长连续空闲段”的长度,New操作需要;

(2)调整边界型:
考虑这样一个问题:现在要插入、删除一些[0, 100000)的整数,并且在此过程中不断询问第K小的整数是多少,怎么办?平衡树可以实现,但线段树显然是更好的方法。对每个结点,存储一个K0值表示位于该结点区间内的整数的个数,则查找第K小的时候只需要不断执行以下操作:Kth(A, K),表示在结点A代表的区间内找第K小的,然后,若K<=结点A的左子结点K0值,则执行Kth(A的左子结点, K),否则执行Kth(A的右子结点, K-A左子结点的K0)(这和平衡树神似),直到找到叶结点为止。这种方法称为“调整边界型”,即随着结点深入,不断缩小(自顶向下)或扩大(自底向上)范围,最后找到结果。像找第K小这样的操作属于自顶向下型,而像“找到X所在的具有某种性质的最长的连续区间”就属于自底向上型(注意和本题的Free不一样);

(3)标记辅助型:
这种维护信息的方法,特点是利用标记来维护信息,即对于某些结点(主要是叶结点,因为其标记不再下放),直接使用标记来得到一些数据,比如对于HDU2871这一题,其中对于叶结点位于的插入线段的标号,使用的就是标记。

下面是本题4个操作的具体实现:
<1>线段树结点定义:
本题需要两棵线段树,这是因为New与Free操作对于tot域(插入线段左端点的总个数)会造成不同的影响,具体来说,在New操作中,tot值不会被同时加上(需要另外一个操作加上),然而在Free操作中,tot值会被同时清空,这样就会导致在对某个结点清空(该结点包含在某个Free操作要清空的线段中)并打上0标记之后,如果紧接着又插入一条包含这个结点区间的新线段,则这个结点的0标记就会丧失,这样在紧接着下传的时候,其子结点的tot值就不会被清空(事实上已经被清空了)。所以,将tot域彻底转移到另一棵线段树里。
struct node {
    
int len, mr, lsc, rsc, sc;
} T[MAXN 
<< 2];
struct node0 {
    
int tot;
    
bool mr;
} T0[MAXN 
<< 2];
其中lsc、rsc、sc就是连续空闲段的长度(用左右归中的方法维护),mr是一个整体赋值标记,在T中,mr的值若为-1表示无标记(未被整体赋值),若为0表示被整体清空,若大于0表示整体被一条线段覆盖,mr值就是这条线段的编号(为区分不同线段,这里按照输入顺序对每一条New操作插入的线段以1、2……编号),在T0中,mr=1表示在Reset中被整体清空,mr=0表示无标记。
<2>操作处理:
1)Reset操作:将T、T0的根结点打上清空标记即可;
2)New:涉及到两个操作,分别是找最左的长度为x的连续空闲段,以及插入一条线段。对于前者,可以根据lsc、rsc、sc的值,按照“先左子结点,再跨越两个子结点,最后右子结点”的顺序求得(详见代码);对于后者就不用说了,太容易实现了(注意标记的处理以及upd,另外要插入一个tot);
3)Free:也涉及两个操作,分别是找一个点x所在的线段(插入过的线段)长度以及删除一条线段,对于前者可将New插入过的所有线段的左右端点预存起来,然后找到代表区间[x, x]的结点的mr值(也就是结点x被编号为神马的线段覆盖),再在预存的线段中找到即可。对于后者,直接清空即可(不要在T0中打标记,而要单独删除一个tot);
4)Get:直接利用T0中的tot找到第K小的值即可;

代码

posted @ 2011-12-18 08:58 Mato_No1 阅读(1097) | 评论 (0)编辑 收藏

有一类动态规划(其中也包含递推)问题,要求满足一些限制条件的字符串,这些限制条件是“需要含有某个子串”或“不能含有某个子串”,那么KMP、AC自动机等就有大用了。

【例1】HDU3689
题意:字符集中有一些字符,给出每个字符的出现概率(它们的和保证为1),再给出一个子串B,求:任给一个长度为N的字符串A(只能包含字符集中的字符),使得S是A的子串的概率。

求解这类问题首先要进行补集转化。因为子串可能有重叠(比如"ababa"中就出现了两个"aba"),所以先转化为“求任给一个长度为N的字符串A(只能包含字符集中的字符),使得B不是A的子串的概率”,然后再用1减去这个概率即为结果。
设F[i][j]为“在所有长度为i的不出现B的字符串中,后缀与B的前缀匹配长度为j(即该字符串的后缀与B的前缀的最大匹配长度为j)的概率”,很显然,F是由递推得到了,关键是如何进行状态转移?或者说,在递推过程中,哪些状态可能成为F[i][j]的前趋状态?
假设F[i-1][k]是F[i][j]的前趋状态,也就是说,在字符集中至少存在一个字符c,使得主串的第i位(最后一位)取c时,能够从F[i-1][k]转移到F[i][j]。这就需要求一个值S[k][c],表示当主串的后缀与B的前缀的(最大)匹配长度为k时,在主串后再加上一个字符c,其匹配长度会变成什么。举例:设目前主串A'="abasab",B="asabs",其匹配长度为4,若在A'后加上一个字符's',则匹配长度变为5,所以S[4]['s']=5,而若在A'后加上一个字符'a',则匹配长度会变成1,所以S[4]['a']=1。显然S值和A前面的哪些字符是没有关系的。
那么这个S值如何计算?其实可以发现,S和KMP算法中的nx数组神似,因此完全可以按照计算nx数组的办法来计算S。具体来说,先要对B作KMP自身匹配,求出其nx数组,然后,在求S[k][c]的时候,尝试在B的第k位(由于B的下标从0开始所以B[k-1])后加上字符c,看看会“回退”到哪里即可。代码:
     int j = 0; nx[0= 0;
     re2(i, 
1, m) {
            
while (j && A[i] != A[j]) j = nx[j - 1];
            
if (A[i] == A[j]) j++;
            nx[i] 
= j;
     }
     re(i, m) re(k, SZ) {
           j 
= i;
           
while (j && A[j] != k + 97) j = nx[j - 1];
           
if (A[j] == k + 97) S[i][k] = ++j; else S[i][k] = 0;
     }
这里m是B的长度。注意,当i=m时,S[i][j]是无意义的,因为前面已经说过了不能出现B。
在求出S值后就能求出F值了。对于状态F[i][j],若存在一个字符c使得x=S[i][c](满足0<=x<m),则F[i][j]是F[i+1][x]的前趋状态。当然,由于本题是求概率而不是求总数,且每个字符出现的概率还不一样,所以转移的时候,应是将F[i+1][x]加上F[i][j]*P[c](P[c]是字符c出现的概率),边界:F[0][0]=1,F[0][1..m-1]均为0。
最终结果为1-∑F[N][0..m-1]。

代码

【例2】PKU1625URAL1158
题意:给出一些子串,求长度为N,各个字符都属于给定的字符集的所有字符串中,不包含任何一个给出的子串的字符串个数(需要使用压9位的高精度)。

本题显然是【例1】的多子串形式,而用来解决多个字符串同时匹配的只有AC自动机,那么如何在本题中使用AC自动机求解呢?
观察【例1】中的F[i][j],可以想象一下,一个图中有m个顶点,分别表示匹配长度为0..(m-1),然后不断新加入的字符让这些状态在这些结点间不断转移(状态转移就是图中的边),这样,F[i][j]就表示“阶段i到达结点j上”。而AC自动机是基于Trie(树)的,其中有现成的结点,这就揭示了本题的状
F[i][j]长度为i的合法的字符串(就是满足字符集限制且不包含任何一个给定子串)中,在匹配到最后一位(第i位)后,刚好到达结点j的字符串的个数
同样,S[k][c]表示“目前到达结点k,接下来的一个字符是c的时候,会到达哪个结点。在对所有的子串建立了自动机之后,S值只要类似地搞就能求出来了。然后F的转移也就搞定了。
不过,本题要万分注意AC自动机的一个BUG:在建立了自动机以后,需要把所有本身不危险(如果一个结点代表的字符串刚好是某一个给出的不能出现的子串,则该结点是危险结点),但通过失败指针不断上溯能够到达一个危险结点的结点,也标记为危险结点,比如两个子串是"abcde"和"bc",则代表"abcd"的那个结点由于包含了"bc"所以也是危险的。
此外,本题的输入要注意,字符集的ASCII码范围是-128~127,所以必须用char而不是unsigned char,且由于可能包含空格所以必须用gets()而不是scanf()输入,又因为C/C++中木有负数下标,因此在输入之后还要转化一下(加128)。

代码

【例3】PKU3691
题意:给出一些子串和一个字符串A(其每个字符均属于字符集{'A', 'C', 'G', 'T'}),求至少要改动A的几个字符(不能改成不属于字符集的字符),使得它不包含任何一个给出的子串,若不管怎么改都不行,则结果为-1。

这就是真正的DP了。设F[i][j]为前i位,到达的结点为j,最少改动的字符个数,则转移方程为
F[i][j] = min{F[i-1][x] + (A[i] != c)},c∈{'A', 'C', 'G', 'T'},S[x][c]=j。边界:F[0][root]=0,其余的F[0][]=+∞,A的实际下标从1开始。
求S数组的方法见【例2】

代码

【例4】PKU3208
题意:含有连续的三个数字6的正整数,称为"beastly number",求第P个(1<=P<=50000000)"beastly number"(其位数不会超过15位)。
(这题是本沙茶在PKU上至今为止,自己想出算法的AC人数最少的题)
本题其实是用不着KMP的,因为"666"这样简单的子串……

思路:由于位数不会超过15位(后来发现最多只有10位),所以每个"beastly number"都可以看成一个长度为15,字符集为['0'..'9']的字符串(注意是可以有前导0的,因为位数可能不足15位)A,整个过程也就是从高位(第0位)向低位(第14位)求出A的各位。

预处理:求出F[i][j],表示若A的前i位已经确定(其中不含"666",准确来说是非末尾不含"666"),且前i位的末尾刚好有j个'6'(j的范围是0到3)时,有多少个"beastly number"(注意,前i位既然已经确定,就不可更改了,能够决定的只有第i位的后面)。
显然先要求出F0[i][j]表示有多少个不是"beastly number"。其递推方程不好写,见代码(其实也是很好理解的)。然后F[i][j]=1014-i - F0[i][j]。

然后就是不断调整边界来构造了。准确来说,设前i-1位已经确定,现在要确定第i位,则枚举第i位是0~9中的哪个值,然后求出满足条件的最小的"beastly number"和最大的"beastly number"的名次(注意,名次是从1开始的),看看P在不在其中,这样就能确定了。严重注意:如果已确定的位数中已经出现了"666",接下来的就不用枚举了,直接在后面接上P-L就行了,L为左边界。

但是,为什么要把本题放在KMP的专题里面呢囧?因为如果这个子串不是"666"而是一些结构复杂的东东比如"123131"这样的,只有借助KMP算法了。这时,F[i][j]就表示 A的前i位已经确定(非末尾不含这个子串),且其后缀与这个子串的前缀匹配长度为j,有多少个"beastly number" ,转移方程与前几个例子类似。

代码

总结:
KMP算法和AC自动机的状态转移性质决定了它们在字符串匹配类DP问题中的巨大作用。在实际应用中,要注意灵活使用它们。此外,AC自动机的那个BUG是一定要注意的。

posted @ 2011-10-30 11:22 Mato_No1 阅读(2317) | 评论 (0)编辑 收藏

【后缀数组真难懂啊啊……就20+行的代码搞了几天才理解……不知是不是我太沙茶了】

【1】一些定义:
字符串:广义的字符串是指“元素类型有序,且元素值有一定范围的序列”,其元素不一定非要是字符,可以是数字等,因此整数、二进制数等也是字符串;
字符集:字符串的元素值的范围称为字符集,其大小记为SZ。
字符串的长度:字符串中元素的个数,一般记为N,长度为N的字符串A第一次提到时一般用A[0..N-1]来表示;
前缀:字符串A[0..N-1]的从A[0]开始的若干个连续的字符组成的字符串称为A的前缀,以下“前缀i”或者“编号为i的前缀”指的都是A[0..i];
后缀:字符串A[0..N-1]的到A[N-1]终止的若干个连续的字符组成的字符串称为A的后缀,以下“后缀i”或者“编号为i的后缀”指的都是A[i..N-1];

对于一个长度为N的字符串,将其N个后缀按字典序大小进行排序,得到两个数组sa[i]和rank[i],sa[i]为排在第i位的后缀的编号(也就是一般说的ord[i]),rank[i]为排在后缀i排在的位置(称为后缀i的名次)。sa、rank值的范围均为[0..N-1]。sa和rank互逆,即sa[i]=j等价于rank[j]=i,或者说成sa[rank[i]]=rank[sa[i]]=i。这里,sa称为后缀数组,rank称为名次数组

【2】用倍增算法求后缀数组:
在论文里,后缀数组有两种求法:倍增算法和DC3算法,前者的时间复杂度为O(NlogN),但常数较小,后者的时间复杂度为O(N),但常数较大,在实际应用中,两者的总时间相差不大,且后者比前者难理解得多(本沙茶理解前者都用了几天时间……后者就木敢看了)。这里就总结一下倍增算法吧囧……
首先,贴一下本沙茶的用倍增算法求后缀数组的模板:
void suffix_array()
{
    
int p, v0, v1, v00, v01;
    re(i, SZ) S[i] 
= 0;
    re(i, n) rank[i] 
= A[i];
    re(i, n) S[A[i]]
++;
    re2(i, 
1, SZ) S[i] += S[i - 1];
    rre(i, n) sa[
--S[A[i]]] = i;
    
for (int j=1; j<n; j<<=1) {
        p 
= 0; re2(i, n-j, n) tmp[p++= i;
        re(i, n) 
if (sa[i] >= j) tmp[p++= sa[i] - j;
        re(i, SZ) S[i] 
= 0;
        re(i, n) S[rank[i]]
++;
        re2(i, 
1, SZ) S[i] += S[i - 1];
        rre(i, n) sa[
--S[rank[tmp[i]]]] = tmp[i];
        tmp[sa[
0]] = p = 0;
        re2(i, 
1, n) {
            v0 
= sa[i - 1]; v1 = sa[i];
            
if (v0 + j < n) v00 = rank[v0 + j]; else v00 = -1;
            
if (v1 + j < n) v01 = rank[v1 + j]; else v01 = -1;
            
if (rank[v0] == rank[v1] && v00 == v01) tmp[sa[i]] = p; else tmp[sa[i]] = ++p;
        }
        re(i, n) rank[i] 
= tmp[i];
        SZ 
= ++p;
    }
}
这里A是待求sa和rank的字符串。

<1>倍增算法的思想:
记R[i][j]为A[i..i+2j-1](如果越界,则后面用@填充)在A的所有长度为2j的子串(越界则后面用@填充)中的名次(rank)值。倍增算法就是按阶段求出所有R[i][j]的值,直到2j>N为止。首先,R[i][0]的就是字符A[i]在A[0..N-1]中的名次,是可以直接用计数排序来实现的。然后,若R[0..N-1][j-1]已知,则可以按照以下方法求出R[0..N-1][j]的值:对每个i(0<=i<N),构造一个二元组<Xi, Yi>,其中Xi=R[i][j-1],Yi=R[i+2j][j-1](若i+2j>=N,则Yi=-∞),然后对这N个二元组按照第一关键字为X,第二关键字为Y(若两者都相等则判定为相等)进行排序(可以用基数排序来实现),排序后,<Xi, Yi>的名次就是的R[i][j]的值。

<2>一开始,对A中的各个字符进行计数排序:
re(i, SZ) S[i] = 0;
re(i, n) rank[i] 
= A[i];
re(i, n) S[A[i]]
++;
re2(i, 
1, SZ) S[i] += S[i - 1];
rre(i, n) sa[
--S[A[i]]] = i;
这个木有神马好说的,在搞懂了基数排序之后可以秒掉。唯一不同的是这里加了一句:rank[i]=A[i],这里的rank[i]是初始的i的名次,MS不符合rank[i]的定义和sa与rank间的互逆性。这里就要解释一下了囧。因为在求sa的过程中,rank值可能不符合定义,因为长度为2j的子串可能会有相等的,此时它们的rank值也要相等,而sa值由于有下标的限制所以不可能有相等的。因此,在过程中,rank其实是用来代替A的子串的,这样rank值只需要表示一个“相对顺序”就行了,也就是:rank[i0]>(=, <)rank[i1],当且仅当A[i0..i0+2j-1]>(=, <)A[i1..i1+2j-1]。这样,可以直接将A[i]值作为初始的rank[i]值。

<3>j(代替2j)的值从1开始不断倍增,对二元组进行基数排序求出新阶段的sa值:
for (int j=1; j<n; j<<=1) {
    p 
= 0; re2(i, n-j, n) tmp[p++= i;
    re(i, n) 
if (sa[i] >= j) tmp[p++= sa[i] - j;
    re(i, SZ) S[i] 
= 0;
    re(i, n) S[rank[i]]
++;
    re2(i, 
1, SZ) S[i] += S[i - 1];
    rre(i, n) sa[
--S[rank[tmp[i]]]] = tmp[i];
注意这个基数排序的过程是很特别的。首先,它并不是对A在进行排序,而是对上一阶段求出的rank在进行排序。因为前面已经说过,在求sa的过程中,rank就是用来代替A的对应长度的子串的,由于不能直接对子串进行排序(那样的话时间开销很恐怖的),所以只能对rank进行排序。另外,这里在对二元组<x, y>的第二关键字(y)进行排序的过程中加了优化:这些y其实就是把上一阶段的sa整体左移了j,右边空出的部分全部用@(空串)填充得到的,由于空串的字典序肯定最小,因此将右边的空串按照下标顺序先写入临时sa(代码中用tmp表示的就是临时sa,也就是对第二关键字y排序后的ord结果),然后,上一阶段的sa如果左移后还木有消失的(也就是sa值大于等于j的),再按顺序写入临时sa,就得到了排序结果。剩下的对x的排序结果就是上一阶段的sa,唯一不同的是对于x相同的,按照临时名次递增的顺序。

<4>求出新阶段的rank值:
tmp[sa[0]] = p = 0;
re2(i, 
1, n) {
    v0 
= sa[i - 1]; v1 = sa[i];
    
if (v0 + j < n) v00 = rank[v0 + j]; else v00 = -1;
    
if (v1 + j < n) v01 = rank[v1 + j]; else v01 = -1;
    
if (rank[v0] == rank[v1] && v00 == v01) tmp[sa[i]] = p; else tmp[sa[i]] = ++p;
}
re(i, n) rank[i] 
= tmp[i];
SZ 
= ++p;
由于下一阶段需要使用本阶段的rank值,因此在求出了本阶段的sa值以后,需要求rank值。(代码中的tmp起了临时rank的作用,目的是节省空间)
因为sa值已经求出,因此只要依次扫描sa就可以得到rank值,唯一要做的工作就是找到哪些子串是相等的,它们的rank值应该相等,除此之外,rank值只要依次加1即可。判定相等的方法:只需判定rank[i]和rank[i+j]是否都对应相等即可。若rank[i+j]越界,用-∞(当然任何一个负数都行,代码中用了-1)来表示。
最后还有一个优化:由于本阶段的名次的范围只有[0..p]这么多,下一阶段的“字符集”(其实就是rank集)的大小SZ可以设为p+1,这样可以省一些时间。

这样后缀数组sa和名次数组rank就全部求完了。

以后还有一些更重要的东东就是AC自动机、后缀数组等的应用问题,算了,以后再搞吧囧。

posted @ 2011-10-23 16:51 Mato_No1 阅读(2809) | 评论 (2)编辑 收藏

(神犇看到这个不要鄙视啊啊……饶了本沙茶啊啊……)

刚才本沙茶在看后缀数组(还木有看完)的时候,里面的那个基数排序写法各种看不懂……

后来到网上一看才发现这是一种极其神犇的基数排序算法,它不需要任何链式或类链式结构,也不需要在每次排序后都把所有元素按照本次排序的结果重新换位置(其实这样是相当耗时间的,尤其是字符串排序的时候,因为复制一个字符串的时间复杂度取决于它的长度),只需要存储每个元素在每次排序之后的“相对下标”即可。

【1】先考虑这样一个问题:对一个含N个元素,每个元素值的范围为[0..SZ-1]的整数序列进行计数排序(第一关键字为字符,第二关键字为下标),并且在排序后求出ord[0..N-1]数组:ord[i]表示排在第i位的元素在排序前的下标。要求这个算法中不能使用任何链式或类链式结构(链表、Dancing Links、vector等)。

设立数组S,S[i]表示值为i的元素的个数。求S[i]可在O(N)时间内求出(一般地,还要用O(SZ)的时间进行初始化)。再设立数组S0(在实现的时候,可以直接用S来存储S0的值),S0[i]=∑S[0..i](也就是值不大于i的元素的个数),求S0只需要在S的基础上用O(SZ)时间即可。然后可以得到一个重要的性质:对于任意i(0<=i<SZ),原序列中的所有值为i的元素,按照其下标从小到大,其名次(或者说是序号,排序前下标为i的元素的名次记为rank[i],下同)依次为S0[i-1]..S0[i]-1(i=0时,为0..S0[i]-1,这里认为名次从0开始),这样,只要在求出S0以后用O(N)时间扫描一遍原序列,每扫描到一个值为i的元素,立刻可以从S0中获得其名次,同时将S0[i]的值加1,扫描完后所有的元素以后即得出了rank[0..N-1]。然后,ord与rank其实是互逆的(因为ord[i]=j等价于rank[j]=i),因此求出了rank以后可以在O(N)时间内求出ord(当然,根据ord[rank[i]]=i这一性质,可以在扫描过程中不求rank而直接求ord)。不过,在扫描这一步,更好的方法是倒序扫描,这样在扫描到一个值为i的元素之后,可以不动用S[i-1](这个当i=0时还要特判,比较麻烦),直接调用S[i]的值(当然要先将S[i]减1),就是该元素的名次了。
很明显,该算法的时间复杂度为O(2SZ+2N)(如果不求rank直接求ord的话)=O(N),且唯一用到的辅助空间就是S(前面已经说过了,直接在S上存储S0,不单独设S0),故空间复杂度也是线性的,没有用到链式或类链式结构。

【2】然后来解决基数排序的问题。假设这里是对字符串进行基数排序(注意,各元素的长度可能不相等,此时排序的总位数L应取所有元素长度的最大值,且排序过程中遇到不足位数的元素要特判:对该元素的该位记为@,@是一个比字符集中的所有字符都小的字符,其在字符集中名次为0,所有实际在字符集中的元素的名次为1..SZ,这样总的字符个数就是SZ+1,在写代码的时候要注意),从最后一位(第L-1位)开始一位一位排序,直至第0位,中间每次排序的过程实质上就是像【1】这样的计数排序。

按照本沙茶以前的方法,每进行一位的排序后就要将所有元素重新调换位置(也就是构造一个新的序列代替原来的序列,原序列的下标为i的元素在新序列中下标为rank[i]),但这样的时间开销很大(前面已经说过了)。更好的方法是在整个排序过程中,序列的各个元素的下标都不变,但每位排序后,序列有一个“相对下标”,相对下标为i的元素就是此次排序中排在第i位的元素(即ord[i]),这样在每次排序时,只要操纵各元素的上一位相对下标即可(在求S的时候不用相对下标,因为S的值是由个数决定的,与顺序无关,但是在求本位的ord的时候,倒序扫描序列其实是倒序扫描相对下标的序列,即扫描到下标为i,实际指的是相对下标为i,即ord[i]),注意一开始所有元素的相对下标与下标相等,即ord[i]=i。这样就不需要调换位置了,只需要ord就行了。

最后总时间复杂度显然是O(NL)的。

代码(对于字符串进行基数排序,这里假设字符串只含小写字母,注意这里的SZ是27而不是26,因为有@的存在):
#include <iostream>
#include 
<stdio.h>
#include 
<string.h>
using namespace std;
#define re(i, n) for (int i=0; i<n; i++)
#define re2(i, l, r) for (int i=l; i<r; i++)
#define rre(i, n) for (int i=n-1; i>=0; i--)
const int MAXN = 100000, MAXLEN = 101, SZ = 27;
int n, L0[MAXN], ord[MAXN], tmp[MAXN], S[SZ];
char A[MAXN][MAXLEN];
void init()
{
    scanf(
"%d"&n);
    re(i, n) scanf(
"%s", A[i]);
}
void solve()
{
    
int L = 0;
    re(i, n) {
        L0[i] 
= strlen(A[i]); ord[i] = i;
        
if (L0[i] > L) L = L0[i];
    }
    rre(j, L) {
        re(i, SZ) S[i] 
= 0;
        re(i, n) S[L0[i] 
> j ? A[i][j] - 96 : 0]++;
        re2(i, 
1, SZ) S[i] += S[i - 1];
        rre(i, n) tmp[
--S[L0[ord[i]] > j ? A[ord[i]][j] - 96 : 0]] = ord[i];
        re(i, n) ord[i] 
= tmp[i];
    }
}
void pri()
{
    re(i, n) puts(A[ord[i]]);
}
int main()
{
    init();
    solve();
    pri();
    
return 0;
}
最后,Orz一下这个无比神犇的算法!!!

posted @ 2011-10-19 21:59 Mato_No1 阅读(599) | 评论 (1)编辑 收藏

具体题目见HDU2222,其实就是一个裸的多串匹配的问题(给出一个主串和N个子串,求出几个子串在主串中出现过)。

我真是太沙茶了……这么水的题目调了N久,找了N位神犇帮我看代码,最终才找出来BUG……

易疵点:
(1)本题的子串是可以相同的,此时Trie的每个结点要设一个mul值,表示该结点对应的字符串在所有子串中重复的次数,另外,不要为了省空间把mul定义成char型,有可能所有的字符串全相同,因此需要定义成int(事实证明不会爆空间),这是本沙茶被折磨了这么久的主要原因
(2)Trie采用静态存储,0号结点作为空结点(NULL),因此真正的结点编号从1开始,另外root一般都是1号结点;
(3)注意在建立自动机以及匹配的时候,所有要沿fail上溯的地方,其边界都是0(NULL,注意不是root)或者找到一个有对应子结点的结点。注意到0还没有找到的处理方法:在建立自动机的时候,将T[j]置为root;在匹配的时候,将x置为root;

代码(模板)(那些标了Attention的地方都是易疵的):
#include <iostream>
#include 
<stdio.h>
#include 
<string>
using namespace std;
using std::string;
#define re(i, n) for (int i=0; i<n; i++)
#define root 1
const int MAXN = 500001, MAXLEN = 1000001, SZ = 26, INF = ~0U >> 2;
struct node {
    
int mul, ch[SZ], fail;    //Attention
} T[MAXN];
int N, Q[MAXN], res;
string s0, A;
char tmp[MAXLEN], tmp0[51];
void ins()
{
    
int len = s0.length(), x = root, c;
    re(i, len) {
        c 
= s0[i] - 97;
        
if (!T[x].ch[c]) {T[x].ch[c] = ++N; T[N].mul = 0; re(j, SZ) T[N].ch[j] = 0;}
        x 
= T[x].ch[c];
    }
    T[x].mul
++;
}
void mkf()
{
    Q[
0= root; T[root].fail = 0;
    
int i, j, x;
    
for (int front=0, rear=0; front<=rear; front++) {
        i 
= Q[front];
        re(k, SZ) 
if (j = T[i].ch[k]) {
            x 
= T[i].fail;
            
while (x && !T[x].ch[k]) x = T[x].fail;        //Attention
            if (x) T[j].fail = T[x].ch[k]; else T[j].fail = root;    //Attention
            Q[++rear] = j;
        }
    }
}
void solve()
{
    
int len = A.length(), x = root, y, c; res = 0;
    re(i, len) {
        c 
= A[i] - 97;
        
while (x && !T[x].ch[c]) x = T[x].fail;    //Attention
        if (!x) x = root; else x = T[x].ch[c];    //Attention
        y = x;
        
while (y) {res += T[y].mul; T[y].mul = 0; y = T[y].fail;}      //Attention
    }
}
int main()
{
    
int tests, n;
    scanf(
"%d"&tests);
    re(testno, tests) {
        N 
= 1; T[root].mul = 0; re(i, SZ) T[root].ch[i] = 0;
        scanf(
"%d"&n); getchar();
        re(i, n) {
            gets(tmp0);
            s0 
= tmp0;
            ins();
        }
        gets(tmp);
        A 
= tmp;
        mkf();
        solve();
        printf(
"%d\n", res);
    }
    
return 0;
}

【2011年10月19日】今天发现了匹配过程中的一个可优化的地方:对于一个点x以及它的所有返回结点(这里把所有沿着x的失败指针不断上溯直到root路径上的结点都称为返回结点),由于不可重复计数,可以将它们的mul值置为原来mul值的相反数(-mul),而不是0,表示该结点已经统计过。这样在下一次y的上溯过程中一旦发现一个mul值为负的点就不用继续上溯了,因为上面的点一定也已经统计过了。
当然,这仅限于单主串,如果是多主串则需要在每次匹配之前把Trie树中所有结点的mul值(如果是负数的的话)全部重新取反。为了节省时间,可以在匹配过程中把所有统计过的(mul值改为负数的)结点全部放进一个辅助的队列里,然后取反时只要处理队列中的结点就行了。

加入该优化后的代码(solve部分):
void solve()
{
    
int len = A.length(), x = root, y, c; res = 0;
    re(i, len) {
        c 
= A[i] - 97;
        
while (x && !T[x].ch[c]) x = T[x].fail;
        
if (!x) x = root; else x = T[x].ch[c];
        y 
= x;
        
while (y && T[y].mul >= 0) {res += T[y].mul; T[y].mul = -T[y].mul; y = T[y].fail;}
    }
}

下面是优化的实测结果(第一个为优化后的,第二个为优化前的),可以看出,该优化的力度很大。

posted @ 2011-10-19 19:47 Mato_No1 阅读(936) | 评论 (0)编辑 收藏

AC自动机就是在Trie树上加入一些失败指针(fail,类似KMP中的next),使得它在某个结点失配的时候能够转移到该结点失败指针指向的结点继续匹配,从而实现多串匹配(单主串多子串)。

【1】Trie树的结构:
首先是结点类型:
struct node {
    
int mul, ch[SZ], fail;
} T[MAXN];
其中SZ是字符集的大小,比如小写字母集SZ=26,数字集SZ=10等。
另外这个mul表示的是该结点的重复次数(和平衡树中的比较像),就是这个结点所对应的字符串(从根到该结点路径上的所有边上的字符组成的字符串)出现了几次。
(不过这种表示法MS不是很好……如果有卡空间的,比如结点总数和SZ之积达到了100M以上,而真正的边又很少的时候……就囧掉了……而如果用指针的话在Linux下面又会CE掉……各位神犇来说一下怎么解决啊囧……)
然后,Trie树的0号结点(T[0])是空结点(用来代替指针中的NULL),因此真正结点下标从1开始。1号结点(T[1])一般都作为根结点,所以下面直接写#define root 1。
还有(这句话是除草用的……)Trie树的字符全部都在边上而不在点上,因此T[x].ch[c]其实指的是“结点x引出的字符为c的边所指向的结点”,简称结点x的c子结点。

【2】自动机的建立:
首先要建立Trie树(也就是在空的Trie树上插入所有要匹配的子串)。这个随便搞一下就傻掉了,因此直接上代码:
void ins()
{
    
int len = s0.length(), x = root, c;
    re(i, len) {
        c 
= s0[i] - 97;
        
if (!T[x].ch[c]) {T[x].ch[c] = ++N; T[N].mul = 0; re(j, SZ) T[N].ch[j] = 0;}
        x 
= T[x].ch[c];
    }
    T[x].mul
++;
}
这里string s0是待插入的字符串,定义成全局变量,因为在参数中出现string有可能爆掉。

然后就是建立自动机了。
这一过程其实是用BFS遍历来实现的。首先,T[root].fail=0(root也是整棵树中唯一的fail为0的结点)并将root入队。下面按照BFS的顺序依次取出队所有的点,对于结点i,若它存在k子结点j(也就是j=T[i].ch[k],且j≠0),则结点j入队,并计算j的失败指针fail,方法:从T[i].fail(不是i)开始不断上溯,直到找到一个存在k子结点的结点或者到root都木有找到(结点下标为0,即NULL)。若找到了一个存在k子结点的结点x,则将T[j].fail置为T[x].ch[k],否则(直到root都木有找到),T[j].fail=root。

到这里失败指针的用处就显现了:如果匹配到结点x的时候失配(即接下来的一个字符是c而T[x].ch[c]=0),可以立刻转到T[x].fail进行匹配,因为T[x].fail有以下三个特征:
<1>其深度严格小于x的深度;
<2>其代表的字符串一定是x代表的字符串的后缀;
<3>该结点一定是满足条件<1><2>的所有结点中深度最小的结点;

代码:
void mkf()
{
    Q[
0= root; T[root].fail = 0;
    
int i, j, x;
    
for (int front=0, rear=0; front<=rear; front++) {
        i 
= Q[front];
        re(k, SZ) 
if (j = T[i].ch[k]) {
            x 
= T[i].fail;
            
while (x && !T[x].ch[k]) x = T[x].fail;
            
if (x) T[j].fail = T[x].ch[k]; else T[j].fail = root;
            Q[
++rear] = j;
        }
    }
}

【3】匹配过程:
在有了失败指针时,其匹配过程就和KMP差不多了。
设主串为A(代码中同),依次扫描A[0..A.length()-1]进行匹配。设目前匹配到了第i位,A[i]=c,当前结点为x。匹配过程中将进行以下操作:
<1>成功匹配(T[x]有c子结点),则进入T[x]的c子结点;
<2>失配(T[x]无c子结点),则从T[x].fail开始,沿着失败指针上溯,直到找到一个有c子结点的结点为止。如果到了root都木有找到这样的结点,则停止在root处;
<3>设立结点y,从当前的结点x开始不断上溯到root(注意root也要算,因为子串中可能有空串),将中间所有结点的mul值累加进最终结果(表示这些字符串在主串中出现了,统计次数),如果题目中要求统计不重复的子串个数(如HDU2222),则在累加之后将它们全部置为0,防止下次再次累加。这一步操作实质上就是统计A中所有以A[i]为右端点的子串个数。

这样,整个过程就傻掉了。

代码:
void solve()
{
    
int len = A.length(), x = root, y, c; res = 0;
    re(i, len) {
        c 
= A[i] - 97;
        
while (x && !T[x].ch[c]) x = T[x].fail;
        
if (!x) x = root; else x = T[x].ch[c];
        y 
= x;
        
while (y) {res += T[y].mul; T[y].mul = 0; y = T[y].fail;}
    }
}

有关例题:
【1】HDU2222
裸的多串匹配问题,模板题;
有关该题的详细资料(包括易疵点)见这里
【2】HDU2896
比2222稍难一些,但还是模板题。注意这题的子串木有重复的,因此mul可以设为bool。
【3】HDU3065
统计每个子串出现的次数(可以重复),也是模板题。
以上三题均不卡空间。

posted @ 2011-10-19 19:03 Mato_No1 阅读(558) | 评论 (0)编辑 收藏

【1】BZOJ1571
DP题,写起来比较繁琐……
首先转移方程是不难想的囧……F[i][j],表示i时间后能力为j,
然后要设一些辅助数组,G[i]表示F[i][1..MAXJ]的最大值,H2[i]表示能力不超过i的一次滑雪的最小时间(这个还要用一个H1[i]表示能力刚好为i的来辅助求出)……
剩下的也就傻掉了,
当然,WJMZBMR神犇用记忆化搜索……省去了一些计算量……有效缩短时间……Orz啊……
(其实,如果大多数状态都是无效状态或者根本导不出最优解的状态,可以用记忆化的……)
代码

【2】BZOJ1572
任务调度问题(贪心模型)的加强版,用堆优化囧……
先把所有的任务按照结束时间递减排序,然后扫描,对于当前任务A[i],结束时间为T[i],上一个任务A[i-1]的结束时间为T[i-1],设D=T[i-1]-T[i],则在堆中取出收益最大的D个任务(显然该堆是以收益为关键字的大顶堆),用它们填上[T[i]+1, T[i-1]]这个时间段(原因很简单,A[i]及以后的任务在T[i]时刻以前就结束了,不能插入到此段内,因此此段内只能插入A[i-1]及其以前的,也就是在堆中的任务),若堆中的任务数<D,则全部取出,进行完这一步后,再将A[i]插入到堆中即可。
总时间复杂度:O(NlogN);
代码

【3】BZOJ1574
很容易想到最小点割(怎么看怎么像囧),但它和最小点割又不一样,因为本题是求T部分点数最少的点割……
正解仍然是贪心。对于每个报告点,由于它没坏且到1没有只经过未坏点的路径,所以与它相邻的所有的点要么是坏点,要么到1也没有路径,因此可以认为它们都是坏点(在最优方案中一定是这样),这样标记出所有的坏点以后,从1开始做一次遍历(只经过未坏点的),最终结果就是遍历到的点数;
代码

【4】BZOJ1575
裸的DP题啊啊……关键是本沙茶WA了N次还用暴搜代码来对拍啊啊……被折磨死了啊啊……
简单讲一下易疵点:
<1>不可把两边都加上一个0来简化,因为前两条(处理两边的)规则和加上0之后的并不等价;
<2>注意边界点(i=0或j=1时)的情况;
<3>注意最终结果,要在F[0..N-1]中找最小的合法的j而不是只在F[N-1]中找;
代码

posted @ 2011-10-05 09:42 Mato_No1 阅读(1584) | 评论 (0)编辑 收藏

仅列出标题
共12页: First 3 4 5 6 7 8 9 10 11 Last