首页 > 代码库 > [Sdoi2016]生成魔咒[SAM or SA]
[Sdoi2016]生成魔咒[SAM or SA]
4516: [Sdoi2016]生成魔咒
Time Limit: 10 Sec Memory Limit: 128 MBSubmit: 1017 Solved: 569
[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 次操作加入的魔咒字符。
1≤n≤100000。,用来表示魔咒字符的数字 x 满足 1≤x≤10^9
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
Source
鸣谢Menci上传
#include<map>#include<cstdio>using namespace std;typedef long long ll;template <typename T>inline void read(T &x){ register char ch=getchar();x=0; while(ch<‘0‘||ch>‘9‘) ch=getchar(); while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}}const int N=2e5+5;int n,p,q,np,nq;ll ans;int last,cnt;int fa[N],l[N];map<int,int>a[N];inline void extend(int c){ p=last;np=last=++cnt;l[np]=l[p]+1; while(!a[p][c]&&p) a[p][c]=np,p=fa[p]; if(!p) fa[np]=1; else{ q=a[p][c]; if(l[p]+1==l[q]) fa[np]=q; else{ nq=++cnt;l[nq]=l[p]+1; a[nq]=a[q]; fa[nq]=fa[q]; fa[np]=fa[q]=nq; while(a[p][c]==q) a[p][c]=nq,p=fa[p]; } } ans+=l[np]-l[fa[np]]; printf("%lld\n",ans);}int main(){ read(n);last=++cnt; for(int i=1,x;i<=n;i++) read(x),extend(x); return 0;}
SA+双向链表：见这里
[Sdoi2016]生成魔咒[SAM or SA]
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。