首页 > 代码库 > BZOJ 2754: [SCOI2012]喵星球上的点名 [后缀数组+暴力]

BZOJ 2754: [SCOI2012]喵星球上的点名 [后缀数组+暴力]

2754: [SCOI2012]喵星球上的点名

Time Limit: 20 Sec  Memory Limit: 128 MB
Submit: 1906  Solved: 839
[Submit][Status][Discuss]

Description

a180285幸运地被选做了地球到喵星球的留学生。他发现喵星人在上课前的点名现象非常有趣。   假设课堂上有N个喵星人,每个喵星人的名字由姓和名构成。喵星球上的老师会选择M个串来点名,每次读出一个串的时候,如果这个串是一个喵星人的姓或名的子串,那么这个喵星人就必须答到。 然而,由于喵星人的字码过于古怪,以至于不能用ASCII码来表示。为了方便描述,a180285决定用数串来表示喵星人的名字。
现在你能帮助a180285统计每次点名的时候有多少喵星人答到,以及M次点名结束后每个喵星人答到多少次吗?  

Input

现在定义喵星球上的字符串给定方法:
先给出一个正整数L,表示字符串的长度,接下来L个整数表示字符串的每个字符。
输入的第一行是两个整数N和M。
接下来有N行,每行包含第i 个喵星人的姓和名两个串。姓和名都是标准的喵星球上的
字符串。
接下来有M行,每行包含一个喵星球上的字符串,表示老师点名的串。

Output

对于每个老师点名的串输出有多少个喵星人应该答到。
然后在最后一行输出每个喵星人被点到多少次。

HINT


【数据范围】 

 对于30%的数据,保证: 

1<=N,M<=1000,喵星人的名字总长不超过4000,点名串的总长不超过2000。

对于100%的数据,保证:

1<=N<=20000,1<=M<=50000,喵星人的名字总长和点名串的总长分别不超过100000,保证喵星人的字符串中作为字符存在的数不超过10000。


于是这道题的正解已经被抛弃,成为了花式暴力练习题 上一篇用AC自动机,这一篇用后缀数组


把所有串用不同的东西隔开连起来建后缀数组

枚举每个点名串,含有他的串就是他的名次左右height>=他的长度的 这里面喵的个数统计一下就好了

 

1600ms (洛谷上反而是这种做法更快...)

#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>using namespace std;const int N=3e5+5,M=3e5+5,INF=1e9;inline int read(){    char c=getchar();int x=0,f=1;    while(c<0||c>9){if(c==-)f=-1; c=getchar();}    while(c>=0&&c<=9){x=x*10+c-0; c=getchar();}    return x*f;}int _=10000;int n,m,k;struct String{    int p,l;}a[N];int cat[N];int s[M],ns;int c[N],t1[N],t2[N];struct SuffixArray{    int n,m;    int sa[N],rnk[N],height[N];    inline bool cmp(int *r,int a,int b,int j){        return a+j<=n&&b+j<=n&&r[a]==r[b]&&r[a+j]==r[b+j];    }    void getSA(){        m=_;        int *r=t1,*k=t2;        for(int i=0;i<=m;i++) c[i]=0;        for(int i=1;i<=n;i++) c[r[i]=s[i]]++;        for(int i=1;i<=m;i++) c[i]+=c[i-1];        for(int i=n;i>=1;i--) sa[c[r[i]]--]=i;        for(int j=1;j<=n;j<<=1){            int p=0;            for(int i=n-j+1;i<=n;i++) k[++p]=i;            for(int i=1;i<=n;i++) if(sa[i]>j) k[++p]=sa[i]-j;            for(int i=0;i<=m;i++) c[i]=0;            for(int i=1;i<=n;i++) c[r[k[i]]]++;            for(int i=1;i<=m;i++) c[i]+=c[i-1];            for(int i=n;i>=1;i--) sa[c[r[k[i]]]--]=k[i];            swap(r,k);p=0;r[sa[1]]=++p;            for(int i=2;i<=n;i++) r[sa[i]]=cmp(k,sa[i],sa[i-1],j)?p:++p;            if(p>=n) break;m=p;        }    }    void getHeight(){        for(int i=1;i<=n;i++) rnk[sa[i]]=i;        int k=0;        for(int i=1;i<=n;i++){            if(k) k--;            if(rnk[i]==1) continue;            int j=sa[rnk[i]-1];            while(i+k<=n&&j+k<=n&&s[i+k]==s[j+k]) k++;            height[rnk[i]]=k;        }    }    void test(){        puts("test");        for(int i=1;i<=n;i++) printf("%d ",rnk[i]);puts("");        for(int i=1;i<=n;i++) printf("%d ",height[i]);puts("");        puts("end");    }}t;int a2[N];int vis[20005];void solve(){    t.n=ns;    t.getSA();    t.getHeight();    for(int i=1;i<=m;i++){        int a1=0;        int p=t.rnk[a[i].p],len=a[i].l;//printf("hi %d %d %d  %d %d\n",i,a[i].p,a[i].l,p,t.height[p]);        for(int j=p;j>1&&t.height[j]>=len;j--){            int q=t.sa[j-1];            if(cat[q]&&vis[cat[q]]!=i) a1++,a2[cat[q]]++,vis[cat[q]]=i;        }        for(int j=p+1;j<=ns&&t.height[j]>=len;j++){            int q=t.sa[j];            if(cat[q]&&vis[cat[q]]!=i) a1++,a2[cat[q]]++,vis[cat[q]]=i;        }        //memset(vis,0,sizeof(vis));        printf("%d\n",a1);    }    for(int i=1;i<=n;i++){printf("%d",a2[i]);if(i!=n) putchar( );}}int main(){    freopen("in","r",stdin);    n=read();m=read();    for(int i=1;i<=n;i++){        k=read();        while(k--) s[++ns]=read(),cat[ns]=i;        s[++ns]=++_;        k=read();        while(k--) s[++ns]=read(),cat[ns]=i;        s[++ns]=++_;    }    for(int i=1;i<=m;i++){        a[i].p=ns+1;        a[i].l=k=read();        while(k--) s[++ns]=read();        if(i!=m) s[++ns]=++_;    }    solve();}

 

扯一下正解:

从大到小枚举height合并建二叉树 第一问用dfs序然后套HH的项链的做法 第二问用树剖或者维护个什么东西?

 

 

 

BZOJ 2754: [SCOI2012]喵星球上的点名 [后缀数组+暴力]