首页 > 代码库 > 【BZOJ4516】【SDOI2016】生成魔咒 [SAM]
【BZOJ4516】【SDOI2016】生成魔咒 [SAM]
生成魔咒
Time Limit: 10 Sec Memory Limit: 128 MB[Submit][Status][Discuss]
Description
魔咒串由许多魔咒字符组成，魔咒字符可以用数字表示。例如可以将魔咒字符 1、2 拼凑起来形成一个魔咒串 [1,2]。
一个魔咒串 S 的非空字串被称为魔咒串 S 的生成魔咒。
例如 S=[1,2,1] 时，它的生成魔咒有 [1]、[2]、[1,2]、[2,1]、[1,2,1] 五种。
S=[1,1,1] 时，它的生成魔咒有 [1]、[1,1]、[1,1,1] 三种。
最初 S 为空串。共进行 n 次操作，每次操作是在 S 的结尾加入一个魔咒字符。
每次操作后都需要求出，当前的魔咒串 S 共有多少种生成魔咒。
Input
第一行一个整数 n。
第二行 n 个数，第 i 个数表示第 i 次操作加入的魔咒字符。
Output
输出 n 行，每行一个数。第 i 行的数表示第 i 次操作后 S 的生成魔咒数量
Sample Input
7
1 2 3 3 3 1 2
1 2 3 3 3 1 2
Sample Output
1
3
6
9
12
17
22
3
6
9
12
17
22
HINT
1≤n≤100000
Main idea
询问在加入每一个字符后当前有多少个本质不同的子串。
Solution
直接用SAM，根据SAM的性质，每次增多的子串个数就是len[New] - len[fa[New]]。
Code
1 #include<iostream> 2 #include<string> 3 #include<algorithm> 4 #include<cstdio> 5 #include<cstring> 6 #include<cstdlib> 7 #include<cmath> 8 #include<map> 9 using namespace std; 10 typedef long long s64;11 12 const int ONE = 400005;13 const int INF = 2147483640;14 15 int n,x;16 s64 Ans;17 18 int get()19 { 20 int res=1,Q=1;char c; 21 while( (c=getchar())<48 || c>57 ) 22 if(c==‘-‘)Q=-1; 23 res=c-48; 24 while( (c=getchar())>=48 && c<=57 ) 25 res=res*10+c-48; 26 return res*Q;27 }28 29 struct SAM30 {31 map <int, int> a[ONE];32 int len[ONE], fa[ONE];33 int last, cnt;34 SAM() {last = cnt = 1;}35 void Add(int c)36 {37 int x = last, New = last = ++cnt;38 len[New] = len[x] + 1;39 while(x && !a[x][c]) a[x][c] = New, x = fa[x];40 if(!x) {fa[New] = 1; Ans += len[New] - len[fa[New]]; return;}41 42 int q = a[x][c];43 if(len[x] + 1 == len[q]) fa[New] = q;44 else45 {46 int Nq = ++cnt; len[Nq] = len[x] + 1;47 a[Nq] = a[q];48 fa[Nq] = fa[q];49 fa[New] = fa[q] = Nq;50 while(a[x][c] == q) a[x][c] = Nq, x = fa[x];51 }52 Ans += len[New] - len[fa[New]];53 }54 }S;55 56 int main()57 {58 n = get();59 while(n--)60 {61 x = get();62 S.Add(x);63 printf("%lld\n", Ans);64 }65 66 }
【BZOJ4516】【SDOI2016】生成魔咒 [SAM]
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。