「BZOJ2754」[SCOI2012] 喵星球上的点名
Description
a180285幸运地被选做了地球到喵星球的留学生。他发现喵星人在上课前的点名现象非常有趣。 假设课堂上有N个喵星人，每个喵星人的名字由姓和名构成。喵星球上的老师会选择M个串来点名，每次读出一个串的时候，如果这个串是一个喵星人的姓或名的子串，那么这个喵星人就必须答到。 然而，由于喵星人的字码过于古怪，以至于不能用ASCII码来表示。为了方便描述，a180285决定用数串来表示喵星人的名字。
现在你能帮助a180285统计每次点名的时候有多少喵星人答到，以及M次点名结束后每个喵星人答到多少次吗？
Input
现在定义喵星球上的字符串给定方法：
先给出一个正整数L，表示字符串的长度，接下来L个整数表示字符串的每个字符。
输入的第一行是两个整数N和M。
接下来有N行，每行包含第i 个喵星人的姓和名两个串。姓和名都是标准的喵星球上的
字符串。
接下来有M行，每行包含一个喵星球上的字符串，表示老师点名的串。
Output
对于每个老师点名的串输出有多少个喵星人应该答到。
然后在最后一行输出每个喵星人被点到多少次。
Sample Input
2 3
6 8 25 0 24 14 8 6 18 0 10 20 24 0
7 14 17 8 7 0 17 0 5 8 25 0 24 0
4 8 25 0 24
4 7 0 17 0
4 17 0 8 25
6 8 25 0 24 14 8 6 18 0 10 20 24 0
7 14 17 8 7 0 17 0 5 8 25 0 24 0
4 8 25 0 24
4 7 0 17 0
4 17 0 8 25
Sample Output
2
1
0
1 2
「提示」
事实上样例给出的数据如果翻译成地球上的语言可以这样来看
2 3
izayoi sakuya
orihara izaya
izay
hara
raiz
HINT
「数据范围」
对于30%的数据，保证：
1<=N,M<=1000，喵星人的名字总长不超过4000，点名串的总长不超过2000。
对于100%的数据，保证：
1<=N<=20000，1<=M<=50000，喵星人的名字总长和点名串的总长分别不超过100000，保证喵星人的字符串中作为字符存在的数不超过10000。
题解
用AC自动机暴力水过
字符集很大只要在自动机每个结点放map即可
把点名串建树，每个名字在树上匹配，对于匹配的每个结点，沿fail指针对能到达的结点暴力统计答案
靠谱的做法似乎要用后缀数组+主席树T T
但是由于字符总长度的限制似乎不好卡掉
反正出题人也没这么无聊卡各种算法
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 |
#include<iostream> #include<set> #include<map> #include<cstdio> #include<cstring> #include<cstdlib> #include<ctime> #include<vector> #include<queue> #include<algorithm> #include<cmath> #define inf 1000000000 #define pa pair<int,int> #define ll long long using namespace std; 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 n,m; int ans1[100005],ans2[100005]; vector<int> a[20005],st[100005],V,M; map<int,int> to[100005]; bool vis[100005],mark[50005]; struct data{ int cnt,ans; int fail[100005],q[100005]; data(){ cnt=1; for(int i=-1;i<=10000;i++) to[0][i]=1; fail[1]=0; } void insert(int id){ int L=read(),x; int now=1; for(int i=1;i<=L;i++) { x=read(); if(!to[now][x])to[now][x]=++cnt; now=to[now][x]; } st[now].push_back(id); } void buildfail(){ int head=0,tail=1; q[0]=1; while(head!=tail) { int now=q[head];head++; for(map<int,int>::iterator i=to[now].begin();i!=to[now].end();i++) { int t=i->first,k=fail[now]; while(!to[k][t])k=fail[k]; fail[i->second]=to[k][t]; q[tail++]=i->second; } } } void get(int id,int x){ for(int i=x;i;i=fail[i]) if(!vis[i]) { vis[i]=1;V.push_back(i); for(int j=0;j<st[i].size();j++) if(!mark[st[i][j]]) { mark[st[i][j]]=1;M.push_back(st[i][j]); ans1[st[i][j]]++; ans2[id]++; } } else break; } void solve(int x){ int now=1; for(int i=0;i<a[x].size();i++) { int t=a[x][i]; while(!to[now][t])now=fail[now]; now=to[now][t];get(x,now); } for(int i=0;i<V.size();i++)vis[V[i]]=0; for(int i=0;i<M.size();i++)mark[M[i]]=0; V.clear();M.clear(); } }trie; int main() { n=read();m=read(); int L,x; for(int i=1;i<=n;i++) { L=read(); while(L--)x=read(),a[i].push_back(x); a[i].push_back(-1); L=read(); while(L--)x=read(),a[i].push_back(x); } for(int i=1;i<=m;i++) trie.insert(i); trie.buildfail(); for(int i=1;i<=n;i++) trie.solve(i); for(int i=1;i<=m;i++)printf("%d\n",ans1[i]); for(int i=1;i<=n;i++) { printf("%d",ans2[i]); if(i!=n)printf(" "); } return 0; } |
计数器 9854505
OI 课件=>
OI 课件=>
map好评
后缀数组+主席树是shenmegui,求教
我问zhonghaoxi有没有啥kmp好题……他给我说这一道……
每个串都是一些a不就卡了吗？
2333 无所谓啦。。。