BZOJ2754 [SCOI2012]喵星球上的点名

2014.12.09 15:43 Tue| 4 visits oi_2015| 2015_刷题日常| Text

Solution

仍然是后缀数组,将字符转化成数字,其他的方面基本没有变化。

首先将所有读入的数串都以10001为分隔符保存到一起,记录每一个点名数串的开始位置,求后缀数组。之后直接枚举每一个点名,利用set记录每一只喵星人在这一次点名中是否被点过 /*STL大法好*/,防止同时点到这只喵星人好多次。总体思想和代码实现上都和 [TJOI2013] 单词 有相似之处。

其实记录是否被点到名字可以直接用数组标记,时间快了三倍QAQ。。果然是我太弱了。。

话说set只慢了三倍,难道传说中 $O_2$ 优化过的set时间复杂度 $\mathcal O(1)$ 是真的?

Code

#include <bits/stdc++.h>
using namespace std;
#define N 300000

int s,t,n,len[N],cnt[N],cat[N],pos[N],_s[N];
int str[N],x[N],y[N],c[N],sa[N],rank[N],height[N];

inline bool same(int a,int b,int k)
{
    return y[a]==y[b] && ((a+k>=n&&b+k>=n)||(a+k<n&&b+k<n&&y[a+k]==y[b+k]));
}

void get_sa(int m=256)
{
    for(int i=0;i<n;i++) c[x[i]=str[i]]++;
    for(int i=1;i<m;i++) c[i]+=c[i-1];
    for(int i=n-1;i>=0;i--) sa[--c[x[i]]]=i;
    for(int k=1;k<n;k<<=1)
    {
        int p=0;
        for(int i=n-k;i<n;i++) y[p++]=i;
        for(int i=0;i<n;i++) if(sa[i]>=k) y[p++]=sa[i]-k;
        memset(c,0,m*sizeof(int));
        for(int i=0;i<n;i++) c[x[y[i]]]++;
        for(int i=1;i<m;i++) c[i]+=c[i-1];
        for(int i=n-1;i>=0;i--) sa[--c[x[y[i]]]]=y[i];
        for(int i=0;i<n;i++) y[i]=x[i];
        m=0; x[sa[0]]=0;
        for(int i=1;i<n;i++)
            x[sa[i]]=same(sa[i-1],sa[i],k)?m:++m;
        if(++m==n) break;
    }
}

void get_height()
{
    for(int i=0;i<n;i++) rank[sa[i]]=i;
    for(int i=0,j,k=0;i<n;height[rank[i++]]=k)
        if(rank[i]) for(k?k--:0,j=sa[rank[i]-1];str[i+k]==str[j+k];k++);
}

inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}

int main()
{
    cin>>s>>t;
    for(int i=1,x;i<=s;i++)
    {
        x=read();
        for(int j=1;j<=x;j++)
            cat[n]=i,str[n++]=read();
        str[n++]=10001;
        x=read();
        for(int j=1;j<=x;j++)
            cat[n]=i,str[n++]=read();
        str[n++]=10001;
    }
    for(int i=1;i<=t;i++)
    {
        len[i]=read(); pos[i]=n;
        for(int j=1;j<=len[i];j++)
            str[n++]=read();
        str[n++]=10001;
    }
    get_sa(10005);
    get_height();
    for(int i=1;i<=t;i++)
    {
        int now=rank[pos[i]],ans=0;
        while(now&&height[now]>=len[i])
            if(cat[sa[--now]]&&_s[cat[sa[now]]]!=i)
                ans++,cnt[cat[sa[now]]]++,_s[cat[sa[now]]]=i;
        now=rank[pos[i]];
        while(++now<n&&height[now]>=len[i])
            if(cat[sa[now]]&&_s[cat[sa[now]]]!=i)
                ans++,cnt[cat[sa[now]]]++,_s[cat[sa[now]]]=i;
        printf("%d\n",ans);
    }
    for(int i=1;i<=s;i++)
        printf("%d%c",cnt[i],i==s?'\n':' ');
}