4516: [Sdoi2016]生成魔咒

时间:2022-09-07 22:04:52

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]生成魔咒的更多相关文章

  1. BZOJ 4516&colon; &lbrack;Sdoi2016&rsqb;生成魔咒 &lbrack;后缀自动机&rsqb;

    4516: [Sdoi2016]生成魔咒 题意:询问一个字符串每个前缀有多少不同的子串 做了一下SDOI2016R1D2,题好水啊随便AK 强行开map上SAM 每个状态的贡献就是\(Max(s)-M ...

  2. BZOJ 4516&period; &lbrack;Sdoi2016&rsqb;生成魔咒【SAM 动态维护不同子串数量】

    [Sdoi2016]生成魔咒 动态维护不同子串的数量 想想如果只要查询一次要怎么做,那就是计算各个点的\(len[u]-len[link[u]]\)然后求和即可,现在要求动态更新,我们可以保存一个答案 ...

  3. 【刷题】BZOJ 4516 &lbrack;Sdoi2016&rsqb;生成魔咒

    Description 魔咒串由许多魔咒字符组成,魔咒字符可以用数字表示.例如可以将魔咒字符 1.2 拼凑起来形成一个魔咒串 [1,2]. 一个魔咒串 S 的非空字串被称为魔咒串 S 的生成魔咒. 例 ...

  4. BZOJ 4516&colon; &lbrack;Sdoi2016&rsqb;生成魔咒

    Description 给出一串数字,求每次插入一个数字后本质不同的子串. Sol SAM. 在 SAM 上添加节点的时候统计一下 \(val[np]-val[par[np]]\) 就可以了... 用 ...

  5. ●BZOJ 4516 &lbrack;Sdoi2016&rsqb;生成魔咒

    题链: http://www.lydsy.com/JudgeOnline/problem.php?id=4516 题解: 把串反过来后,问题变为求每个后缀的互不相同的子串个数.首先用倍增算法求出 sa ...

  6. BZOJ 4516&colon; &lbrack;Sdoi2016&rsqb;生成魔咒 后缀自动机 性质

    http://www.lydsy.com/JudgeOnline/problem.php?id=4516 http://blog.csdn.net/doyouseeman/article/detail ...

  7. BZOJ 4516&colon; &lbrack;Sdoi2016&rsqb;生成魔咒——后缀数组、并查集

    传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4516 题意 一开始串为空,每次往串后面加一个字符,求本质不同的子串的个数,可以离线.即长度为 ...

  8. BZOJ&period;4516&period;&lbrack;SDOI2016&rsqb;生成魔咒&lpar;后缀数组 RMQ&rpar;

    题目链接 后缀自动机做法见这(超好写啊). 后缀数组是可以做的: 本质不同的字符串的个数为 \(子串个数-\sum_{ht[i]}\),即 \(\frac{n(n+1)}{2}-\sum_{ht[i] ...

  9. BZOJ&period;4516&period;&lbrack;SDOI2016&rsqb;生成魔咒&lpar;后缀自动机 map&rpar;

    题目链接 后缀数组做法见这. 直接SAM+map.对于每个节点其产生的不同子串数为len[i]-len[fa[i]]. //15932kb 676ms #include <map> #in ...

随机推荐

  1. class Solution&lpar;object&rpar;&colon; def fizzBuzz&lpar;self&comma; n&rpar;&colon; a &equals; &lbrack;&rsqb; i &equals; 1 while&lpar;i &lt&semi;&equals; n&rpar;&colon; if&lpar;i&percnt;15 &equals;&equals; 0&rpar;&colon; a&period;append&lpar;&quot&semi;FizzBuzz&quot&semi;&rpar; elifleetcode day&lowbar;01

    412. Fizz Buzz Write a program that outputs the string representation of numbers from 1 to n. But fo ...

  2. python os&period;path

    os.path 提供了一些处理文件路径的函数. os.path.abspath(path) 返回绝对路径, 在大多数平台上, os.path.abspath(path) == os.path.norm ...

  3. Mysql 大小写问题

    今天发布程序的时候,日志报错找不到表,但是系统中已经存在表,最后发现是sql大小写的问题,mysql默认设置导致这些执行失败. 1.用ROOT登录,修改/etc/my.cnf 2.在[mysqld]下 ...

  4. GCD与block

    GCD技术多线程编程的三个技术  NSThread NSOperation GCD1.GCD(Grand central Dispatch:宏大的*调度)        1) 是用纯C语言实现的.提 ...

  5. 【BZOJ】3850&colon; ZCC Loves Codefires(300T就这样献给了水题TAT)

    http://www.lydsy.com/JudgeOnline/problem.php?id=3850 题意:类似国王游戏....无意义.. #include <cstdio> #inc ...

  6. &lbrack;HDU 4417&rsqb; Super Mario &lpar;树状数组&rpar;

    题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=4417 题目大意:给你n个数,下标为0到n-1,m个查询,问查询区间[l,r]之间小于等于x的数有多少个 ...

  7. HDU 2852 KiKi&&num;39&semi;s K-Number 树状数组 &plus; 二分

    一共最多才100000个数,并且数值范围0~100000. 树状数组 C[i] 记录数值为 i 的数有多少个. 删除时如果Query( a ) - Query( a - 1 ) == 0 则该数不存在 ...

  8. Android 再按一次退出程序

    实现代码: private long exitTime = 0; /** * 捕捉返回事件按钮 * * 因为此 Activity 继承 TabActivity 用 onKeyDown 无响应,所以改用 ...

  9. Redis&colon; OOM command not allowed when used memory &gt&semi; &OpenCurlyQuote;maxmemory

    Redis: OOM command not allowed when used memory > ‘maxmemory’ 解决方式: $ vim /etc/redis/6903.conf ma ...

  10. mysql 5&period;6&period;20的安装、配置服务、设置编码格式

    一.安装 安装环境        系统:Window 32        版本:Mysql 5.6.20 1. 首先从官网上http://dev.mysql.com/downloads/mysql/ ...