【XSY2968】线性代数
2024-08-30 23:26:45
题目来源: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 ;
}
最新文章
- mysql交互协议解析——mysql包基础数据、mysql包基本格式
- 专业上的常用的工具和类库集 By 老衣
- IKONS – 赞!264 款手工打造的免费矢量图标
- ios应用数据存储方式
- oracle11g 数据文件误删恢复(无备份)
- tuning 02 Diagnostic and Tuning Tools
- OSG中的示例程序简介(转)
- Asp.net mvc中Controller的返回值
- winform控件跨线程委托
- java系列--重载和覆盖小结
- Tomcat结构、启动过程、关键组件简单分析
- python基础----1. globals和locals
- 《SpringMVC从入门到放肆》十四、SpringMVC分组数据校验
- Arrays和String单元测试-20175218
- laravel5.8笔记十:Redis操作
- 14-03 java BigInteger类,BigDecimal类,Date类,DateFormat类,Calendar类
- Mysql 批量更新update的表与表之间操作
- Scala_继承
- Window10 Linux子系统挂载磁盘
- .net Core 中将原MVC中的 MvcHtmlString转换
热门文章
- 自我介绍About me
- 关于linux系统的sendmail使用中的问题与解决
- ubuntu的安装
- 【ACM-ICPC 2018 南京赛区网络预赛 L】Magical Girl Haze
- Java基础学习总结(63)——Java集合总结
- JavaScript原生值与JSON的转换
- C#中的IEnumerable<;T>;知识点
- [SharePoint]2013装过WindowsServerAppFabricSetup_x64_6.1导致安装不能继续
- Android測试APP工具(一)
- 兔子-RadioButton和RadioGroup的关系