2018年5月1日
bzoj3172: [Tjoi2013]单词（AC自动机）
摘要： https://www.lydsy.com/JudgeOnline/problem.php?id=3172 构建AC自动机 在fail树上，点i的子树大小 表示trie树上根节点到i构成的单词 是 多少个(子)串的子串 #include<queue> #include<cstdio> #includ 阅读全文
posted @ 2018-05-01 22:10 TRTTG 阅读(279) 评论(0) 推荐(1)
bzoj3238: [Ahoi2013]差异（后缀数组+st表+单调栈）
摘要： https://www.lydsy.com/JudgeOnline/problem.php?id=3238 跟 bzoj3879 差不多 #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using n 阅读全文
posted @ 2018-05-01 21:16 TRTTG 阅读(226) 评论(0) 推荐(0)
bzoj3879: SvT（后缀数组+st表+单调栈）
摘要： https://www.lydsy.com/JudgeOnline/problem.php?id=3879 把所有的后缀取出，按rank排序 求出相邻两个后缀的lcp 每个后缀对答案的贡献就是 与在它之前的后缀的lcp之和 维护一个单调递增的栈，记录栈中元素的lcp之和 即可 #include<cs 阅读全文
posted @ 2018-05-01 21:00 TRTTG 阅读(338) 评论(0) 推荐(0)
bzoj2119: 股市的预测（后缀数组+st表）
摘要： https://www.lydsy.com/JudgeOnline/problem.php?id=2119 题意：将给定数组差分后，求ABA形式的字串个数，要求|B|=m，|A|>0 1、后缀数组求出 差分序列 和 翻转差分序列后的序列 的sa，rk，height 2、枚举len=|A|，对差分序列 阅读全文
posted @ 2018-05-01 18:04 TRTTG 阅读(324) 评论(0) 推荐(0)