【GDOI2013模拟4】贴瓷砖
2024-09-06 06:55:15
题目
A镇的主街是由N个小写字母构成,镇长准备在上面贴瓷砖,瓷砖一共有M种,第i种上面有Li个小写字母,瓷砖不能旋转也不能被分割开来,瓷砖只能贴在跟它身上的字母完全一样的地方,允许瓷砖重叠,并且同一种瓷砖的数量是无穷的。
问街道有多少字母(地方)不能被瓷砖覆盖。
分析
AC自动机模板题,
优化:用up[x]表示x沿fail链上的第一个有值的点,这样就省去循环了 。
线段覆盖求答案。
#include <cmath>
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <queue>
const int maxlongint=2147483647;
const int mo=1000000007;
const int N=300001;
using namespace std;
struct ddx
{
int c[26],fail,deep,w,sum,up;
}trie[4008000];
char s[N],s1[N];
int n,m,tot,ans,sum[N],d[N*14];
void put()
{
int root=1;
for(int i=1;i<=strlen(s1+1);i++)
{
if(trie[root].c[s1[i]-'a'])
{
root=trie[root].c[s1[i]-'a'];
trie[root].sum++;
if(i==strlen(s1+1))
{
trie[root].w++;
}
}
else
{
trie[root].c[s1[i]-'a']=++tot;
trie[tot].sum++;
trie[tot].deep=trie[root].deep+1;
root=tot;
if(i==strlen(s1+1))
{
trie[tot].w++;
}
}
}
}
void makefail()
{
int head=0,tail=1,root=1;
d[1]=1;
trie[1].fail=0;
while(head<tail)
{
int k=d[++head],p=0;
for(int i=0;i<26;i++)
{
if(!trie[k].c[i]) continue;
p=trie[k].c[i];
int z=trie[k].fail;
while(z && !trie[z].c[i])
z=trie[z].fail;
trie[p].fail=trie[z].c[i];
d[++tail]=p;
trie[p].fail=trie[p].fail?trie[p].fail:1;
trie[p].up=p;
if(trie[p].up!=1 && !trie[trie[p].up].w) trie[p].up=trie[trie[p].fail].up;
}
}
}
int find()
{
int j=1;
for(int i=1;i<=n;i++)
{
int index=s[i]-'a';
while(j!=1 && !trie[j].c[index]) j=trie[j].fail;
j=trie[j].c[index];
j=j?j:1;
int p=j;
sum[i+1]--,sum[i-trie[trie[p].up].deep+1]++;
}
}
int main()
{
scanf("%d",&n);
scanf("%s",s+1);
scanf("%d",&m);
tot++;
for(int i=1;i<=m;i++)
{
scanf("%s",s1+1);
put();
}
makefail();
find();
int k=0;
for(int i=1;i<=n;i++)
{
k+=sum[i];
if(k)
ans++;
}
printf("%d",n-ans);
}
最新文章
- ReactJS入门(四)—— 组件API
- javaweb常见问题解决
- .NET JSON对象序列化和反序列化
- 深入理解Java多态机制
- FLASH CC 2015 CANVAS (一) 与AS3的写法区别
- QT显示输出及其桌面
- proxy 出现乱码问题解决 lua
- 基于visual Studio2013解决C语言竞赛题之0707月份输出
- xxx==null和xxx.equals(null)的区别
- gunicorn geventworker 解析
- JavaScript夯实基础系列(五):类
- Golang基础语法1
- Faster-RCNN 自己的数据训练
- Trident Topology开发Demo
- 七牛云存储上传自有证书开启https访问
- 在server 2003中搭建域服务(Http NTLM 代理)
- Spark计算模型RDD
- Qtcreator中常用快捷键总结
- executeQuery、executeUpdate 和 execute
- 循环神经网络RNN原理
热门文章
- 【神经网络与深度学习】【CUDA开发】【VS开发】Microsoft官方移植了Caffe配置过程说明
- Shell 变量详解教程之位置变量与预定义变量
- 定时任务crontab命令
- [转帖]预警 | Linux 爆“SACK Panic”远程DoS漏洞,大量主机受影响
- C中的异常处理
- springBoot2.0使用@ImportResource引入spring配置文件.xml
- Linux命令基础#1
- python中常见的一些错误异常类型
- 【优质blog、网址】置顶
- 用SQL存储过程生成唯一单据号