【LG4070】[SDOI2016]生成魔咒
题面
题解
如果我们不用在线输的话,那么答案就是对于所有状态\(i\)
\]
现在我们需要在线询问,那么因为\(SAM\)是在线算法,我们考虑每次的对答案的贡献。
那么产生的贡献就是\(last.len-last.fa.len\)。
与\(yyb\)的对话:
Q:为什么构建自动机时中间过程新加的点不会算到最后答案中呢?
A:不影响答案啊,你在两个len之间断开,对于答案的贡献不变。
代码
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <tr1/unordered_map>
using namespace std;
using namespace std::tr1;
inline int gi() {
register int data = 0, w = 1;
register char ch = 0;
while (!isdigit(ch) && ch != '-') ch = getchar();
if (ch == '-') w = -1, ch = getchar();
while (isdigit(ch)) data = 10 * data + ch - '0', ch = getchar();
return w * data;
}
const int MAX_N = 1e5 + 5;
struct Node {
unordered_map<int, int> ch;
int len, fa;
} t[MAX_N << 1];
int tot = 1, lst = 1;
long long ans = 0;
void extend(int c) {
int New = ++tot;
t[lst].ch[c] = New;
t[New].len = t[lst].len + 1;
int p = t[lst].fa; lst = tot;
while (p && t[p].ch.find(c) == t[p].ch.end()) t[p].ch[c] = New, p = t[p].fa;
if (!p) t[New].fa = 1;
else {
int q = t[p].ch[c];
if (t[q].len == t[p].len + 1) t[New].fa = q;
else {
int _q = ++tot; t[_q] = t[q];
t[New].fa = t[q].fa = _q, t[_q].len = t[p].len + 1;
while (p) {
unordered_map<int, int> :: iterator ite;
ite = t[p].ch.find(c);
if (ite == t[p].ch.end() || ite->second != q) break;
t[p].ch[c] = _q;
p = t[p].fa;
}
}
}
ans += t[New].len - t[t[New].fa].len;
}
int main () {
#ifndef ONLINE_JUDGE
freopen("cpp.in", "r", stdin);
#endif
int N = gi();
for (int i = 1; i <= N; i++) extend(gi()), printf("%lld\n", ans);
return 0;
}
【LG4070】[SDOI2016]生成魔咒的更多相关文章
-
BZOJ4516: [Sdoi2016]生成魔咒 后缀自动机
#include<iostream> #include<cstdio> #include<cstring> #include<queue> #inclu ...
-
BZOJ 4516: [Sdoi2016]生成魔咒 [后缀自动机]
4516: [Sdoi2016]生成魔咒 题意:询问一个字符串每个前缀有多少不同的子串 做了一下SDOI2016R1D2,题好水啊随便AK 强行开map上SAM 每个状态的贡献就是\(Max(s)-M ...
-
BZOJ_4516_[Sdoi2016]生成魔咒_后缀数组+ST表+splay
BZOJ_4516_[Sdoi2016]生成魔咒_后缀数组+ST表+splay Description 魔咒串由许多魔咒字符组成,魔咒字符可以用数字表示.例如可以将魔咒字符 1.2 拼凑起来形成一个魔 ...
-
P4070 [SDOI2016]生成魔咒
题目地址:P4070 [SDOI2016]生成魔咒 相信看到题目之后很多人跟我的思路是一样的-- 肯定要用 SA(P3809 [模板]后缀排序) 肯定要会求本质不同的子串个数(P2408 不同子串个数 ...
-
bzoj4516 / P4070 [SDOI2016]生成魔咒
P4070 [SDOI2016]生成魔咒 后缀自动机 每插入一个字符,对答案的贡献为$len[last]-len[fa[last]]$ 插入字符范围过大,所以使用$map$存储. (去掉第35行就是裸 ...
-
洛谷 P4070 [SDOI2016]生成魔咒 解题报告
P4070 [SDOI2016]生成魔咒 题目描述 魔咒串由许多魔咒字符组成,魔咒字符可以用数字表示.例如可以将魔咒字符 \(1\).\(2\) 拼凑起来形成一个魔咒串 \([1,2]\). 一个魔咒 ...
-
[Sdoi2016]生成魔咒[SAM or SA]
4516: [Sdoi2016]生成魔咒 Time Limit: 10 Sec Memory Limit: 128 MBSubmit: 1017 Solved: 569[Submit][Statu ...
-
4516: [Sdoi2016]生成魔咒
4516: [Sdoi2016]生成魔咒 链接 题意: 求本质不同的子串. 分析: 后缀数组或者SAM都可以. 考虑SAM中每个点的可以表示的子串是一个区间min(S)~max(S),把每个点的这个区 ...
-
[SDOI2016] 生成魔咒 - 后缀数组,平衡树,STL,时间倒流
[SDOI2016] 生成魔咒 Description 初态串为空,每次在末尾追加一个字符,动态维护本质不同的子串数. Solution 考虑时间倒流,并将串反转,则变为每次从开头删掉一个字符,即每次 ...
随机推荐
-
HDU 5652 India and China Origins(经典并查集)
特别经典的一个题,还有一种方法就是二分+bfs 题意:空间内n*m个点,每个点是0或者1,0代表此点可以走,1代表不能走.接着经过q年,每年一个坐标表示此点不能走.问哪年开始图上不能出现最上边不能到达 ...
-
mysql数据库编码问题
http://www.cnblogs.com/sunzn/archive/2013/03/14/2960248.html 修改/etc/my.cnf 添加: [mysql] default-chara ...
-
ES TIPS
1,Testing Analyzers Especially when you are new to Elasticsearch, it is sometimes difficult to under ...
-
[转]linux系统磁盘分区之parted
转自:http://blog.csdn.net/h249059945/article/details/12668793 对于linux的分区通常可以使用fdisk命令工具和parted工具对于分区表通 ...
-
(转)Linux IO模式及 select、poll、epoll详解
本文为转载,并作了部门调整.修改. [原文出处:https://segmentfault.com/a/1190000003063859] 同步IO和异步IO,阻塞IO和非阻塞IO分别是什么,到底有什么 ...
-
HDU4527+BFS
模拟BFS搜索 对于一个将要爆炸的点,可能同时由多个点引起. /* 模拟搜索过程 */ #include<stdio.h> #include<stdlib.h> #includ ...
-
Maven--构建企业级仓库(二)
<Maven--搭建开发环境(一)> <Maven--构建企业级仓库(二)> <Maven—几个需要补充的问题(三)> 看到经历的两家公司 ...
-
ZUFE 1035 字符宽度编码(字符串)
Time Limit: 1 Sec Memory Limit: 128 MB Description 你的任务是编写一个程序实现简单的字符宽度编码方法.规则如下:将任何2~9个相同字符的序列编码成2 ...
-
前言《iOS网络高级编程:iPhone和iPad的企业应用开发》(书籍学习)
本书内容: 在客户端设备与服务器之间执行HTTP请求 管理客户端设备与服务器之间的数据负载 处理HTTP请求的错误 保护网络通信 改进网络通信的性能 执行Socket层的通信 实现推送通知 单个设备上 ...
-
Python全栈之路----常用模块----xml处理模块
xml是实现不同语言或程序之间进行数据交换的协议,跟json差不多,但json使用起来更简单,不过,古时候,在json还没诞生的黑暗年代,大家只能选择用xml呀,至今很多传统公司如金融行业的很多系统的 ...