4516: [Sdoi2016]生成魔咒
题意:
求本质不同的子串。
分析:
后缀数组或者SAM都可以。
考虑SAM中每个点的可以表示的子串是一个区间min(S)~max(S),把每个点的这个区间加起来即可。
字符集有点大,可以用map。
代码:
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<cmath>
#include<cctype>
#include<set>
#include<queue>
#include<vector>
#include<map>
using namespace std;
typedef long long LL; inline int read() {
int x=,f=;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-;
for(;isdigit(ch);ch=getchar())x=x*+ch-'';return x*f;
} const int N = ;
map<int,int> ch[N];
int fa[N], len[N], Index = , Last = ;
LL Ans; void extend(int c) {
int np = ++Index, p = Last;
len[np] = len[p] + ;
for (; p && ch[p].find(c) == ch[p].end(); p = fa[p]) ch[p][c] = np;
if (!p) fa[np] = ;
else {
int Q = ch[p][c];
if (len[Q] == len[p] + ) fa[np] = Q;
else {
int NQ = ++Index;
fa[NQ] = fa[Q];
ch[NQ] = ch[Q];
len[NQ] = len[p] + ;
fa[Q] = fa[np] = NQ;
for (; p && ch[p].find(c) != ch[p].end() && ch[p][c] == Q; p = fa[p]) ch[p][c] = NQ;
}
}
Last = np;
Ans += len[np] - len[fa[np]]; // max(np)=len[np], min(np)=len[fa[p]] + 1
printf("%lld\n", Ans);
}
int main() {
int n = read();
for (int i = ; i <= n; ++i) {
int x = read();
extend(x);
}
return ;
}
4516: [Sdoi2016]生成魔咒的更多相关文章
-
BZOJ 4516: [Sdoi2016]生成魔咒 [后缀自动机]
4516: [Sdoi2016]生成魔咒 题意:询问一个字符串每个前缀有多少不同的子串 做了一下SDOI2016R1D2,题好水啊随便AK 强行开map上SAM 每个状态的贡献就是\(Max(s)-M ...
-
BZOJ 4516. [Sdoi2016]生成魔咒【SAM 动态维护不同子串数量】
[Sdoi2016]生成魔咒 动态维护不同子串的数量 想想如果只要查询一次要怎么做,那就是计算各个点的\(len[u]-len[link[u]]\)然后求和即可,现在要求动态更新,我们可以保存一个答案 ...
-
【刷题】BZOJ 4516 [Sdoi2016]生成魔咒
Description 魔咒串由许多魔咒字符组成,魔咒字符可以用数字表示.例如可以将魔咒字符 1.2 拼凑起来形成一个魔咒串 [1,2]. 一个魔咒串 S 的非空字串被称为魔咒串 S 的生成魔咒. 例 ...
-
BZOJ 4516: [Sdoi2016]生成魔咒
Description 给出一串数字,求每次插入一个数字后本质不同的子串. Sol SAM. 在 SAM 上添加节点的时候统计一下 \(val[np]-val[par[np]]\) 就可以了... 用 ...
-
●BZOJ 4516 [Sdoi2016]生成魔咒
题链: http://www.lydsy.com/JudgeOnline/problem.php?id=4516 题解: 把串反过来后,问题变为求每个后缀的互不相同的子串个数.首先用倍增算法求出 sa ...
-
BZOJ 4516: [Sdoi2016]生成魔咒 后缀自动机 性质
http://www.lydsy.com/JudgeOnline/problem.php?id=4516 http://blog.csdn.net/doyouseeman/article/detail ...
-
BZOJ 4516: [Sdoi2016]生成魔咒——后缀数组、并查集
传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4516 题意 一开始串为空,每次往串后面加一个字符,求本质不同的子串的个数,可以离线.即长度为 ...
-
BZOJ.4516.[SDOI2016]生成魔咒(后缀数组 RMQ)
题目链接 后缀自动机做法见这(超好写啊). 后缀数组是可以做的: 本质不同的字符串的个数为 \(子串个数-\sum_{ht[i]}\),即 \(\frac{n(n+1)}{2}-\sum_{ht[i] ...
-
BZOJ.4516.[SDOI2016]生成魔咒(后缀自动机 map)
题目链接 后缀数组做法见这. 直接SAM+map.对于每个节点其产生的不同子串数为len[i]-len[fa[i]]. //15932kb 676ms #include <map> #in ...
随机推荐
-
class Solution(object): def fizzBuzz(self, n): a = [] i = 1 while(i <;= n): if(i%15 == 0): a.append(";FizzBuzz";) elifleetcode day_01
412. Fizz Buzz Write a program that outputs the string representation of numbers from 1 to n. But fo ...
-
python os.path
os.path 提供了一些处理文件路径的函数. os.path.abspath(path) 返回绝对路径, 在大多数平台上, os.path.abspath(path) == os.path.norm ...
-
Mysql 大小写问题
今天发布程序的时候,日志报错找不到表,但是系统中已经存在表,最后发现是sql大小写的问题,mysql默认设置导致这些执行失败. 1.用ROOT登录,修改/etc/my.cnf 2.在[mysqld]下 ...
-
GCD与block
GCD技术多线程编程的三个技术 NSThread NSOperation GCD1.GCD(Grand central Dispatch:宏大的*调度) 1) 是用纯C语言实现的.提 ...
-
【BZOJ】3850: ZCC Loves Codefires(300T就这样献给了水题TAT)
http://www.lydsy.com/JudgeOnline/problem.php?id=3850 题意:类似国王游戏....无意义.. #include <cstdio> #inc ...
-
[HDU 4417] Super Mario (树状数组)
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=4417 题目大意:给你n个数,下标为0到n-1,m个查询,问查询区间[l,r]之间小于等于x的数有多少个 ...
-
HDU 2852 KiKi&#39;s K-Number 树状数组 + 二分
一共最多才100000个数,并且数值范围0~100000. 树状数组 C[i] 记录数值为 i 的数有多少个. 删除时如果Query( a ) - Query( a - 1 ) == 0 则该数不存在 ...
-
Android 再按一次退出程序
实现代码: private long exitTime = 0; /** * 捕捉返回事件按钮 * * 因为此 Activity 继承 TabActivity 用 onKeyDown 无响应,所以改用 ...
-
Redis: OOM command not allowed when used memory >; ‘maxmemory
Redis: OOM command not allowed when used memory > ‘maxmemory’ 解决方式: $ vim /etc/redis/6903.conf ma ...
-
mysql 5.6.20的安装、配置服务、设置编码格式
一.安装 安装环境 系统:Window 32 版本:Mysql 5.6.20 1. 首先从官网上http://dev.mysql.com/downloads/mysql/ ...