2018年5月3日
hihoCoder #1457 : 后缀自动机四·重复旋律7（后缀自动机 + 拓扑排序)
摘要： http://hihocoder.com/problemset/problem/1457 val[i] 表示状态i所表示的所有字符串的十进制之和 ans= ∑ val[i]在后缀自动机上，从起始状态走任意一条路径到达任意一个状态，这条路径上的字符就是到达的状态的字符串之一 所以利用拓扑排序，记录从起 阅读全文
posted @ 2018-05-03 20:56 TRTTG 阅读(463) 评论(0) 推荐(0)
hihoCoder #1445 : 后缀自动机二·重复旋律5
摘要： http://hihocoder.com/problemset/problem/1445 求不同的子串个数 阅读全文
posted @ 2018-05-03 19:30 TRTTG 阅读(384) 评论(0) 推荐(0)
bzoj4939: [Ynoi2016]掉进兔子洞（莫队 + bitset）
摘要： https://www.lydsy.com/JudgeOnline/problem.php?id=4939 ans= r1-l1+1 + r2-l2+1 +r3-l3+1 - ∑ min(cnt1[i],cnt2[i],cnt3[i])*3 计算cnt可以用莫队 关键在与如何对3个区间取小 用bit 阅读全文
posted @ 2018-05-03 19:07 TRTTG 阅读(530) 评论(0) 推荐(0)
bzoj2865: 字符串识别（后缀自动机 + 线段树）
摘要： https://www.lydsy.com/JudgeOnline/problem.php?id=2865 同上一篇博客 就是卡卡空间，数组改成map #include<map> #include<cstdio> #include<cstring> #include<algorithm> #defi 阅读全文
posted @ 2018-05-03 17:12 TRTTG 阅读(539) 评论(0) 推荐(0)
bzoj1396: 识别子串（后缀自动机 + 线段树）
摘要： https://www.lydsy.com/JudgeOnline/problem.php?id=1396 后缀自动机的parent树上，如果不是叶子节点，那么至少有两个子节点 而一个状态所代表子串的出现次数就是子树中叶子节点的个数 所以只有叶子节点 即 |Right|=1的状态 代表的子串 出现了 阅读全文
posted @ 2018-05-03 16:52 TRTTG 阅读(320) 评论(0) 推荐(0)