频道栏目
首页 > 考试 > 其他 > 正文

字符串计数 (后缀自动机+二分答案+矩阵快速幂)

2018-03-10 10:00:02      个评论    来源:KsCla  
收藏   我要投稿

字符串计数 (后缀自动机+二分答案+矩阵快速幂)。


题目分析:别人眼中的好题,然而我觉得就是把SAM强套上另一个算法的题

后缀自动机的特点使其能够很好地解决本题,因为它能够识别原串的所有子串。如果从Root开始匹配模式串,而走到的当前状态并不拥有模式串下一位的转移,那么原串便没有这个子串。

接下来从静态的问题开始考虑:假设已经给定了一个模式串,如何求出题目中最少的操作次数?做法是将模式串在SAM上贪心地向后匹配,出现空转移时返回Root的对应儿子继续匹配,并令操作数+1。为什么这样最优呢?我们将模式串用XYZW表示,其中X,XY,ZW,YZW都是原串的子串。按照贪心的策略,应该从XY,ZW处断开,变成两个子串。而如果从X,YZW处断开,最后一个子串就变长了。YZW存在的转移ZW必然存在,而ZW却有可能继续向后匹配而YZW不能。所以贪心正确。

然后变为动态的问题。假设当前节点P不存在c这个转移,为了方便我们将P转移到根节点的c儿子,并令这条边的代价为1,代表操作数+1,其余边代价为0。现在问题变成了:从Root出发,走N步,求最大的代价。

然而直接解决这个问题比较困难。我们发现这个新图中权值为0的边很多,所以可以把一些无用的点删掉,合并两条边,最后发现有用的点只有Root的A,B,C,D四个儿子。从A到C的边长度为新图中从A向下走,走到某个拥有空转移’C’的状态的最短步数。然后这就浓缩成了一个4个点的完全图。现在我们要走长度之和不超过N的边,使得经过的边数尽可能多。直接做依旧不好搞,可以二分答案mid,看走mid步经过的最小长度是多少。这可以用类似floyd的矩阵快速幂加速判断。由于这题的时间主要来自SAM,所以时间为O(|T|)" role="presentation">O(|T|)

其实如果这题字符集再大一些的话,二分+矩乘的时间复杂度就会比较高。然而如果字符集比较大的话,似乎会很难出数据。可能这就是T中只有A,B,C,D的原因吧。

我本来以为这题能1A,结果我还是太naive了。一开始BFS的队列没有开|T|的两倍,RE了一次(SAM节点数为串长的2倍);后来发现判断mid的边界没有处理好;再后来我实在想不出有什么问题,又检查了一遍代码,发现我的SAM居然建错了?!总之4A,代码还是写得很快的。QAQ


CODE:

#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;

const int maxn=100100;
const int maxc=4;
const long long oo=2e18;
typedef long long LL;

struct Tnode
{
    int val;
    bool vis;
    Tnode *parent,*son[maxc];
} tree[maxn<<1];
Tnode *Root,*last;
int cur=-1;

struct mat
{
    LL num[maxc][maxc];
} e;
int id;

Tnode *que[maxn<<1]; //!!!
int dep[maxn<<1]; //!!!
int tail;

char s[maxn];
int len;
LL n;

Tnode *New_node(int v)
{
    cur++;
    tree[cur].val=v;
    tree[cur].parent=NULL;
    for (int i=0; ison[to] ) P->son[to]=NP,P=P->parent;
        if (!P)
        {
            NP->parent=Root;
            continue;
        }
        Tnode *Q=P->son[to];
        if (P->val+1==Q->val) NP->parent=Q;
        else
        {
            Tnode *NQ=New_node(P->val+1);
            for (int i=0; ison[i]=Q->son[i];
            NQ->parent=Q->parent;
            Q->parent=NP->parent=NQ;
            while ( P && P->son[to]==Q ) P->son[to]=NQ,P=P->parent; //!!!
        }
    }
}

void Bfs()
{
    tail=1;
    que[1]=Root->son[id];
    que[1]->vis=true;
    dep[1]=1;
    for (int i=1; i<=tail; i++)
    {
        Tnode *P=que[i];
        for (int j=0; json[j] && !P->son[j]->vis )
                P->son[j]->vis=true,que[++tail]=P->son[j],dep[tail]=dep[i]+1;
            else e.num[id][j]=min(e.num[id][j],(long long)dep[i]);
    }
}

mat Times(mat x,mat y)
{
    mat z;
    for (int i=0; i>1);
    temp=Times(temp,temp);
    if (x&1) temp=Times(temp,e);
    return temp;
}

bool Judge(LL mid)
{
    //mid--;
    mat temp=Fast_power(mid);
    LL min_len=oo;
    for (int i=0; i>1;
        if ( Judge(mid) ) L=mid;
        else R=mid;
    }
    return L+1LL;
}

int main()
{
    freopen("4180.in","r",stdin);
    freopen("4180.out","w",stdout);

    scanf("%lld",&n);
    scanf("%s",s);
    len=strlen(s);

    Build();
    for (id=0; id
                                
            
        
        
上一篇:(Basic Level) Practise (中文)1006. 换个格式输出整数
下一篇:程序开发练习题解析
相关文章
图文推荐

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站