题目来源:noi2018模拟测试赛(二十二)

毒瘤板题+提答场……真tm爽

提答求最大团,各路神仙退火神仙随机化八仙过海

题意:

题解:

支持双端插入的回文自动机板题

代码:

 #include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<queue>
#define inf 2147483647
#define eps 1e-9
using namespace std;
typedef long long ll;
typedef double db;
int q,cnt=,anss,top[],last[],son[][],len[],fail[],dep[],st[];
ll ans=;
char op[],x[];
int newn(int l){
len[cnt]=l;
return cnt++;
}
void init(){
memset(son,,sizeof(son));
memset(st,-,sizeof(st));
newn();
newn(-);
top[]=q+;
top[]=q+;
last[]=last[]=;
fail[]=;
}
int getfail(int u,int op){
while(st[top[op]]!=st[top[op]+(op?-:)*(len[u]+)])u=fail[u];
return u;
}
void extend(int ch,int op){
if(op)st[++top[op]]=ch;
else st[--top[op]]=ch;
int nw=getfail(last[op],op);
if(!son[nw][ch]){
int nn=newn(len[nw]+);
fail[nn]=son[getfail(fail[nw],op)][ch];
dep[nn]=dep[fail[nn]]+;
if(len[nn]==top[]-top[]+)last[op^]=nn;
son[nw][ch]=nn;
}
last[op]=son[nw][ch];
ans+=dep[last[op]];
}
int main(){
scanf("%d",&q);
init();
while(q--){
scanf("%s%s",op,x);
extend(x[]-'a',op[]=='r');
printf("%lld %d\n",ans,cnt-);
}
return ;
}

最新文章

  1. mysql交互协议解析——mysql包基础数据、mysql包基本格式
  2. 专业上的常用的工具和类库集 By 老衣
  3. IKONS – 赞!264 款手工打造的免费矢量图标
  4. ios应用数据存储方式
  5. oracle11g 数据文件误删恢复(无备份)
  6. tuning 02 Diagnostic and Tuning Tools
  7. OSG中的示例程序简介(转)
  8. Asp.net mvc中Controller的返回值
  9. winform控件跨线程委托
  10. java系列--重载和覆盖小结
  11. Tomcat结构、启动过程、关键组件简单分析
  12. python基础----1. globals和locals
  13. 《SpringMVC从入门到放肆》十四、SpringMVC分组数据校验
  14. Arrays和String单元测试-20175218
  15. laravel5.8笔记十:Redis操作
  16. 14-03 java BigInteger类,BigDecimal类,Date类,DateFormat类,Calendar类
  17. Mysql 批量更新update的表与表之间操作
  18. Scala_继承
  19. Window10 Linux子系统挂载磁盘
  20. .net Core 中将原MVC中的 MvcHtmlString转换

热门文章

  1. 自我介绍About me
  2. 关于linux系统的sendmail使用中的问题与解决
  3. ubuntu的安装
  4. 【ACM-ICPC 2018 南京赛区网络预赛 L】Magical Girl Haze
  5. Java基础学习总结(63)——Java集合总结
  6. JavaScript原生值与JSON的转换
  7. C#中的IEnumerable&lt;T&gt;知识点
  8. [SharePoint]2013装过WindowsServerAppFabricSetup_x64_6.1导致安装不能继续
  9. Android測试APP工具(一)
  10. 兔子-RadioButton和RadioGroup的关系