http://www.spoj.com/problems/SUBLEX/en/ 题意： 给一个字符串，每次询问字典序第k大的不重复子串。 思路： 先做个拓扑dp，求出SAM上，一个状态到种态的路径数。 拓扑dp其实就是按照拓扑序的dp啦... 然后从SAM的初始态开始，每次字典序从小到大得贪心寻找。思想类似可持久化线段树求区间第k大。 /* *********************************************** Author :111qqz Created Time :2017年11月08日 星期三 18时50分18秒 File Name :sublex.cpp …

http://www.spoj.com/problems/NSUBSTR/en/ 题意： f[i]指长度为i的串出现次数的最大值。这里的不同出现指，可以有重复串，只要起始位置不同就视为不同的出现。 求f[1]..f[lenth]。 思路： 我们知道，SAM上的节点是right集合的等价类。 一个子串的right集合是指在一个母串中，某个子串所有出现位置的右端点的集合。 如果两个子串的right集合完全相同，那么就可以归结为同一个节点，也就是说这两个子串对于SAM是等价的。 因为在SAM上，这两个子串后，添加若干字符得到的后缀都是一样的。 所以一个SAM节点的个数，就是right集合等价类的个数（如果不考虑初始状态） 对于SAM某一个 …

http://poj.org/problem?id=1949 题意： 有n个任务，第i个任务需要时间xi来完成，并且第i个任务必须在它 “前面的” 某些任务完成之后才能开始。 给你任务信息，问你最短需要多少时间来完成任务。 思路： 拓扑排序+dp 拓扑排序的过程中做个dp，可以保证dp的顺序... 对于这道题，找出每条依赖链，然后做dp即可。 /* *********************************************** Author :111qqz Created Time :2017年11月07日 星期二 13时52分27秒 File Name :3249.cpp …

https://vjudge.net/problem/47450/origin 题意： 有一个含有n个数的序列，m个询问。问 [l, r] 区间内与所有数都互质的数有几个？ 思路： 想到了预处理每个数最左最右的，最远的互质的数的范围。。 之后对于询问区间[l,r]，我们要知道 对于 i>=L && i <= R 并且 a[i].l<=L，a[i].r>=R的i的个数... 没有想到怎么维护,gg 转载一段题解： 先算出每个数的有效范围，l[i]，r[i]代表与第i个数一直互质到的最左端和最右端。这个处理方法是，预处理出一张因子表。然后对每个输入的数，判断其因子出现的最接近它的位置。从左到右扫一 …

http://poj.org/problem?id=3249 题意： 给一个DAG,现要从一条入度为0的点到一个出度为0的点，问最大点权和。 思路： 其实比较容易想到搜...不过复杂度会炸？ 由于到一个点的最大点权和，需要更新完所有到达它的路线之后才能确定。 容易联想到拓扑排序，我们可以在拓扑排序的同时做dp dp[v] = max(dp[v],dp[u]+a[v])，初始化对于入度为0的点，dp[i] = val[i]. 其实拓扑+dp是一种比较一般化的套路...？ 因为拓扑保证了更新顺序 /* *********************************************** Author :111qqz …

http://acm.hdu.edu.cn/showproblem.php?pid=6048 题意： 有 n * m - 1 个数，每次选择第 1,p + 1,p * 2 + 1….. 的顺序选择数，先按左到右，再按从上到下的顺序填入n * m 的格子，空格子可以和相邻的数字交换位置，问最后能否在格子中形成 1~ n * m - 1的数按从左到右，从上到下的顺序。 思路： 傻逼结论题。 根据九宫格问题的结论：将矩阵中的数按先从左到下右再从上到下排成一列，其逆序对如果为偶数则一定有解，否则一定无解 根据九宫格问题的结论：将矩阵中的数按先从左到下右再从上到下排成一列，其逆序对如果为偶数则一定有解，否则一定无解 根据九宫格问题的结论：将矩 …

http://acm.hdu.edu.cn/showproblem.php?pid=4782 题意： 将格式混乱的html代码输出成标准格式。 思路： 模拟。 说下细节： * 遇到open tag,先打印，后dep++ * 遇到close tag,先dep--,再打印 * 遇到空标签，直接在当前深度打印 * 遇到空白字符时，只有当前面出现了text以及后面也出现了text的时候才打印。**也就是说第一个string和最后一个string都是紧邻标签的。** 最坑的一点是...虽然题目给了数据组数，但是在所在行的同一行，可能出现下一组的开始 最坑的一点是...虽然题目给了数据组数，但是在所在行的同一行，可能出现下一组的开始 最坑的 …

***在学习后缀自动机之前需要熟练掌握WA自动机、RE自动机与TLE自动机*** 怕是老年人的最后一篇算法学习笔记了 心情不好，此文无限期tj 概述 主要讲解在我学习的过程中比较难理解的地方..并不保证全面 首先，后缀自动机是一个能且只能接受一个字符串的所有后缀的确定性有限状态自动机，也就是DFA SAM同时具有自动机和树的性质。 节点（状态） SAM中的节点，也叫状态。 明确一个说法：“一个节点所表示的字符串”。 由于一个字符串的子串一定是某个后缀的前缀。 因此一个字符串的子串一定可以在SAM上运行。 因此“一个节点Q所表示的字符串”的含义是说，从初始状态开始，运行该字符串后，到达的状态是Q. 一个节点所表示的字符串长度属于范 …

题意： 给定一个循环字符串，问字典序最小的串的开始位置。 思路： 之前用poj 1509 解题报告-字符串的最小表示法 A过 字符串的最小表示法的复杂度是O(n)，代码也不是很难写，不过由于最近在学SAM,所以用SAM写了一下。 参照张天扬的论文： 把原串复制一遍到后面，然后构建后缀自动机。 从初始状态开始，每次走字典序最小的转移，走|S|之后得到的就是最小循环表示。 如果求的是最小后缀，就在原串后加入一个比字符集中所有字符的字典序都小的字符作为终止后，再添加一遍原串。 /* *********************************************** Author :111qqz Created Time …

http://acm.hdu.edu.cn/showproblem.php?pid=4622 题意： 给一个字符串，给出若干询问，每组询问给一个区间[l,r]，问区间中本质不同的字符串的个数。 思路： 观察发现，有10000组查询，字符串的长度最多才2000，所以可以预处理一波。 我们先考虑如何处理整个区间中，本质不同的子串数量。 考虑SAM，由于后缀自动机中每一条从初始状态出发的路径都对应的一个子串，同时后缀自动机是最简的，所以问题也就变成了从初始状态开始不同路径的数量。 每个节点 u 表示的子串长度在 [min[u],max[u]]范围内. 又由于max(u.fail) = min(u)-1 因此u表示的子串的长度就是变成 …