P4070 [SDOI2016]生成魔咒

た入场券 2021-09-30 00:08 421阅读 0赞

## 题目 ##

[P4070 \[SDOI2016\]生成魔咒][P4070 _SDOI2016]

有点水

## 做法 ##

每次把加上\\(np\\)这个点新生产的串，直接加上\\(np.longest-np.fail.longest\\)

## My complete code ##

#include<map> #include<iostream> #include<algorithm> #include<cstdio> #include<cstring> #include<string> using namespace std; typedef long long LL; const LL maxn=1000000; inline LL Read(){ LL x(0),f(1);char c=getchar(); while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+c-'0',c=getchar(); return x*f; } LL n,nod=1,lst=1,sum; LL a[maxn]; struct SAM{ LL fail,len; map<LL,LL> son; }S[maxn]; inline void Insert(LL c){ LL np=++nod,p=lst; lst=nod; S[np].len=S[p].len+1; while(p&&S[p].son[c]==0){ S[p].son[c]=np; p=S[p].fail; } if(!p) S[np].fail=1; else{ LL q=S[p].son[c]; if(S[q].len==S[p].len+1) S[np].fail=q; else{ LL nq=++nod; S[nq].len=S[p].len+1; S[nq].son=S[q].son; S[nq].fail=S[q].fail; //sum+=S[nq].len-S[S[nq].fail].len; S[q].fail=S[np].fail=nq; while(p&&S[p].son[c]==q){ S[p].son[c]=nq; p=S[p].fail; } } } } int main(){ n=Read(); for(LL i=1;i<=n;++i){ a[i]=Read(); Insert(a[i]); sum+=S[lst].len-S[S[lst].fail].len; printf("%lld\n",sum); } return 0; }

转载于:https://www.cnblogs.com/y2823774827y/p/10317910.html

[P4070 _SDOI2016]: https://www.luogu.org/problemnew/show/P4070

发表评论取消回复

表情：

评论列表（有 0 条评论，421人围观）

还没有评论，来说两句吧...

相关阅读

相关程序员逃不过“打工人”魔咒？

在编程语言社区 TIOBE 最新发布的 2020 年度最受欢迎的编程语言中，Python 再一次获得殊荣。这把“火”在编程语言界已经持续燃烧了很久，甚至越烧越旺，主要得益于 P

深碍√TFBOYSˉ_/ 2023年01月07日 07:14/ 0 赞/ 258 阅读

相关【程序设计训练】魔咒词典

【问题描述】哈利波特在魔法学校的必修课之一就是学习魔咒。据说魔法世界有100000种不同的魔咒，哈利很难全部记住，但是为了对抗强敌，他必须在危急时刻能够调用任何一个需要

桃扇骨/ 2022年11月25日 10:10/ 0 赞/ 314 阅读

相关魔咒词典——个人c++解

Problem Description 哈利波特在魔法学校的必修课之一就是学习魔咒。据说魔法世界有100000种不同的魔咒，哈利很难全部记住，但是为了对抗强敌，他必须在危

刺骨的言语ヽ痛彻心扉/ 2022年06月16日 05:18/ 0 赞/ 319 阅读

相关问题 : 魔咒词典

题目描述哈利波特在魔法学校的必修课之一就是学习魔咒。据说魔法世界有100000种不同的魔咒，哈利很难全部记住，但是为了对抗强敌，他必须在危急时刻能够调用任何一个需要的魔咒

小鱼儿/ 2022年06月10日 06:26/ 0 赞/ 304 阅读

相关【HDU 1880】魔咒词典（字符串操作）

题目：[点击打开题目链接][Link 1] Problem Description：哈利波特在魔法学校的必修课之一就是学习魔咒。据说魔法世界有100000种不同的魔咒，哈

拼搏现实的明天。/ 2022年05月03日 18:58/ 0 赞/ 320 阅读

相关魔咒词典

【问题描述】哈利波特在魔法学校的必修课之一就是学习魔咒。据说魔法世界有100000种不同的魔咒，哈利很难全部记住，但是为了对抗强敌，他必须在危急时刻能够调用任何一个需要的魔

待我称王封你为后i/ 2022年04月24日 11:36/ 0 赞/ 528 阅读

相关洛谷 P4071 [SDOI2016]排列计数

![1596060-20190612191650302-584562041.png][] ![1596060-20190612191710278-1020740109.png

Bertha 。/ 2022年01月12日 13:33/ 0 赞/ 296 阅读

相关 P4071 [SDOI2016]排列计数题解

分析：线性求逆元：[https://blog.csdn.net/qq\_34564984/article/details/52292502][https_blog.cs

以你之姓@/ 2021年10月24日 07:00/ 0 赞/ 362 阅读

相关 P4070 [SDOI2016]生成魔咒

题目 [P4070 \[SDOI2016\]生成魔咒][P4070 _SDOI2016] 有点水做法每次把加上\\(np\\)这个点新生产的串，直接加上\\

た入场券/ 2021年09月30日 00:08/ 0 赞/ 422 阅读

相关程序员如何打破“35岁魔咒”？

如何才能持续成长，是所有程序员绕不开的话题。编程前期，你可能想寻找不断培养自己编程思维与能力的方法；成长期，又想了解自己应该具备哪些综合素质，瓶颈期，又要面临着如何做出正确

Bertha 。/ 2021年08月31日 04:13/ 0 赞/ 695 阅读