2018年5月2日
2016vijos 1-1 兔子的字符串（后缀数组 + 二分 + 哈希）
摘要： 题意： 给出一个字符串，至多将其划分为n部分，每一部分取出字典序最大的子串ci，最小化 最大的ci 先看一个简化版的问题： 给一个串s，再给一个s的子串t，问能否通过将串划分为k个部分，使t成为划分后的s的字典序最大子串 对于这个问题，从串s的最后面开始，一个字符一个字符的向前推 如果当前[l,r] 阅读全文
posted @ 2018-05-02 18:12 TRTTG 阅读(740) 评论(0) 推荐(0)
bzoj4650: [Noi2016]优秀的拆分（后缀数组+差分+st表）
摘要： https://www.lydsy.com/JudgeOnline/problem.php?id=4650 如果能够预处理出 suf[i] 以i结尾的形式为AA的子串个数 pre[i] 以i开头的形式为AA的子串个数 ans= ∑ suf[i]*pre[i+1] 这两个数组的求法，类似bzoj 21 阅读全文
posted @ 2018-05-02 15:03 TRTTG 阅读(283) 评论(0) 推荐(0)
bzoj3173: [Tjoi2013]最长上升子序列（二分+树状数组）
摘要： https://www.lydsy.com/JudgeOnline/problem.php?id=3173 插入的数是以递增的顺序插入的 这说明如果倒过来考虑，那么从最后一个插入的开始删除，不会对以某个数结尾的最长上升子序列产生影响 所以 先原序列求出来，输出即可 还原原序列的方法： 可以用平衡树， 阅读全文
posted @ 2018-05-02 06:53 TRTTG 阅读(413) 评论(0) 推荐(0)