BZOJ3670(NOI2014)动物园题解

题目传送门
一道水题,据说有O(n)做法,我竟然没想到也没看懂。我的做法是KMP后用next数组搞棵树,然后在树上找一个节点前面最后一个符合条件的节点,一种方法是发现这玩意有单调性,然后用一个point数组记录下其父亲的决策点,再拿个ST表倍增或者Tarjan+二分,也可以利用轻重链搞一搞就可以了。这里用了轻重链。这种方法我只能证明有O(n^2lgn)的上界,但平均效率很高。

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int MAX_N=1000005;
const int MOD=1000000007;
struct Node{ int top; int heavy_node; int size; }node[MAX_N];
int next[MAX_N],point[MAX_N];
long long num[MAX_N];
void get_next(char* s){
    int len=strlen(s+1);
    next[0]=-1;
    for(int i=1;i<=len;++i){
        int j=next[i-1];
        while(j!=-1&&s[j+1]!=s[i]) j=next[j];
        next[i]=j+1;
    }
} 
int jump(int x,int y){ //y是x的祖先 
    while(1){
        if(node[x].top==node[y].top) return node[y].heavy_node;
        if(next[x]==y) return x;
        x=(x==node[next[x]].heavy_node)?node[x].top:next[x]; 
    }
}
char s[MAX_N];
void get_num(char* s){
    int len=strlen(s+1);
    for(int i=1;i<=len;++i){
        if(next[i]==0) num[i]=0,point[i]=i;
        else{
            num[i]=num[next[i]],point[i]=point[next[i]];
            while(point[i]<=(i>>1)) point[i]=jump(i,point[i]),++num[i];
        }
    }
}
void initialize(){
    scanf("%s",s+1); strlen(s);
    int n=strlen(s+1); get_next(s);
    for(int i=n;i>=0;--i) node[i].size=1,node[i].heavy_node=-1;
    for(int i=n;i>=1;--i){
        node[next[i]].size+=node[i].size;
        if(node[next[i]].heavy_node==-1||node[node[next[i]].heavy_node].size<node[i].size) 
             node[next[i]].heavy_node=i;
    }
    for(int i=1;i<=n;++i) node[i].top=(node[next[i]].heavy_node==i)?node[next[i]].top:i;
    get_num(s);
    //for(int i=1;i<=n;++i) printf("%d ",num[i]);
}
int main(){
    int t; scanf("%d",&t);
    while(t--){
        initialize();
        long long ans=1;
        int n=strlen(s+1);
        for(int i=1;i<=n;++i) ans=(ans*(num[i]+1))%MOD;
        printf("%d\n",ans);
    }
    return 0;
}

还有一种方法是直接倍增,这种方法是严格O(nlgn)的,但平均情况下,时间和空间的开销都比上一种方法要高很多。

#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#define MAX_N 1000005
#define MOD 1000000007
using namespace std;
int n,next[MAX_N],cnt[MAX_N],st[23][MAX_N],level;
    inline void get_next(char* s){
        next[0]=-1,s[0]='\0',cnt[0]=0;
        for(int i=1;i<=n;++i){
            int j=next[i-1];
            while(j!=-1&&s[j+1]!=s[i]) j=next[j];
            next[i]=j+1,cnt[i]=cnt[j+1]+1; 
        }
    }
    inline int lg(const int& x){
        int i=0;
        while((1<<i)<=x) ++i;
        return i-1;
    }
    inline void st_initialize(){
        for(int i=0;i<=n;++i) st[0][i]=next[i];
        for(int i=1;i<=level;++i)
            for(int j=0;j<=n;++j)
                st[i][j]=(st[i-1][j]==-1)?-1:st[i-1][st[i-1][j]];
    }
char s[MAX_N];
inline int jump(int x){
    int mid=(x>>1),ret=cnt[x];
    for(int i=level;i>=0;--i)
        if(st[i][x]>mid) x=st[i][x],ret-=(1<<i);
    return ret-1;
}
inline void opera(){
    scanf("%s",s+1),n=strlen(s+1),level=lg(n+1);
    get_next(s),st_initialize();
    long long ans=1;
    for(int i=1;i<=n;++i) ans=(ans*(jump(i)+1))%MOD;
    printf("%lld\n",ans);
}
int main(){
    int t; scanf("%d",&t);
    while(t--) opera();
    return 0; 
}

Leave a Comment

电子邮件地址不会被公开。 必填项已用*标注