树上的选择性DP…… 不是很懂其他人的做法，偶然间看到有人用ruby A了，我也就用ruby敲了一蛤 速度有点玄…… 题意： 给你一棵树，每个节点都有权值，要你求每个节点到根节点所形成的树链 gcd。 其中每条树链都可以选择一个节点使得权值变为 0 。 思路： 感觉这就是裸题…… 只不过就是把数组改成树上了而已。 用一个栈或者队列去遍历这棵树，对于每个节点是否变0都考虑一下就好了…… AC Code #!/usr/bin/env ruby # encoding: utf-8 n = gets.to_i a = gets.split.map(&:to_i) g = Array.new(n) {[]} (n-1).times do u, v = gets.split.map(&:to_i)…
后缀数组之重复次数最多的连续重复子串 这道题真的是做的我脑壳疼…… 口误，根本不能算是做，死嗑论文怎么也嗑不出来…… 好难，这应该是我现在做过的后缀数组里最难的一题了…… 这里放上我理解之后的思路： 首先枚举长度 l ，如果存在两个长度为 l 的连续重复子串，那么在 ( str[ 0 ] , str[ l ] , str[ l \times 2 ] ) …… 中必然会存在两个相邻的位置他们值相同（加上这个优化，速度可以大幅度提升），我们对这两个位置的后缀求最长公共前缀 lcp ，那么显然，由这两个位置得出的子串重复次数为 ( lcp \div l + 1 )。 但是这个答案并不一定是正确的，因为我们只能确保 ( str[ 0 ] , str [ l ] , str[ l \times 2 ] ) …… 中会出现重复值，但是这几个是边界。 由kuangbin大佬给出一个想法是考虑 ( lcp % l ) 的含义。( lcp…
后缀数组之可重叠 k 次最长重复子串。
数据好水……他的 “ 字符 ” 范围为 ( [ 0 , 1e6 ] )
按我最开始的想法，求后缀数组的时候，在字符最大值超过 char 我就打算用 sort 代替基数排序了。
然而……直接取最大值用基数排序居然过了，还是 63 ms ……
下面是可重叠 k 次最长重复子串的求法：
解法与不可重叠最长重复子串的做法基本一致。
二分答案，将排序后的后缀按照二分值分成若干组，如果某一组的数量大于等于 k ，那么这个二分值是可行值。
题意：
可重叠 k 次最长重复子串。
思路：
见上。
AC Code
#include
后缀数组之最长公共前缀的不定查询。 因为查询很多，所以要结合RMQ算法。这个也是很简单的，一般不会有什么变化，只要套一下木板就好了。 但是这个有一个非常困扰我的地方，就是题目给定的查询不是后缀之间的最长公共前缀查询，而是子串之间的查询，这可难倒我了，我也不知道该如何解决。 看了题解后，发现其实解决方法很简单，只要将求得的 LCP 与两个子串长度互相比较，三个长度取最小就是我们要得答案。 题意： 给你一个字符串，再给你很多子串，要你将所有给定的子串进行压缩。 压缩方式为将两个字符串的最长公共前缀在第二个字符串用数字表示。 输出未压缩的长度和压缩后的长度，要记空格和换行。 思路： 不断求 LCP 即可。 在求的过程中有几个注意的地方。 * 注意后缀相同的情况。 * 得到两个后缀的 rank 后不能直接使用 RMQ ，一方面有不确定的大小关系，另一方面，我们是对height 数组求 RMQ ，做区间应为 较小的 rank + 1 。 * 注意将RMQ数组开大…… 这道题使用的代码已经能成为我求 LCP 的模板了 除了改成DC3 AC Code…
一道不知所以然的题目……
没什么好废话的，直接上题解。
题意：
要你求一个字符串的所有前缀在自己本身的所有出现次数。
思路：
这道题如果用KMP的话是十分简单的，但是我一开始没想到用KMP，想了一些时间，看了kuangbin的博客说可以用KMP求解，略想了一下，果真如此。
KMP思路：
直接next数组跳几下就可以了。
后缀数组思路：
后缀数组的思路让我有点蒙逼……只要将所有后缀与最长的后缀，也就是原串的最长公共前缀相加再加上原串长度就是答案。
而看过论文的都应该知道，这个是可以( O( n ) )直接求出来的。
但是还是有点似董非董。
#include
后缀数组论文题，也是后缀数组的入门题——最长公共子串。
另外这题是双倍经验 HDU 1403 Longest Common Substring不过HDU的数据更水一点。
题意：
给你两个字符串，求最长公共子串。
思路：
因为是论文题，我不可能讲的比论文还详细的啦……这不是显然的吗
看了论文后基本就是套板子，因为它已经吧最关键的地方给证明了，然后有一个小地方，为什么可以直接拿 sa 数组与第一个字符串长度 key 比较呢？
那是因为，sa数组本身就是记录后缀排名第 idx 位的是哪一个后缀，而后缀和第一个字符串 key ，都是从左往右正向计数的。故可以直接拿来比较。
AC Code
#include
淦啊……我之前自以为入门的最大团DP优化板子是错的，我说怎么和极大团计数差别这么多，那个原先的根本就是一个被谁自创的dfs+dp优化算法，速度平均慢一倍！！！
说句别的，终于刷完这套……给出链接
最大团与稳定婚姻专题
题意：
要你找出一个数量不小于 k 的最大团，使得最大团中的最短距离最大。
思路：
二分距离+最大团判定
老实说我一开始没想到，但看到这个思路之后就是豁然开朗，感觉二分的思路都是这样的……
然后疯狂TLE……不知道为什么，查了一下，最大团板子太慢了……原来学得是民间算法！！
AC Code
#include
前言 前排提示！！！ 这里的正则表达式只用来竞赛！！！！ 只谈论正则函数的使用方法，不涉及正则表达式的基础使用方法。 尽管 C++ 的 正则表达式一直为人所诟病，一般人都会推荐你去使用boost的正则，但是ACM竞赛里显然是不能使用boost库的…… 据说 C 的正则比 boost 的正则都要快，然而我不会……自然得觉得 C++ 会好用点吧。关于 C 的以后学。 正则表达式类 regex , 头文件即 regex。 三个核心函数 C++ 的正则库有三个常用函数，也是核心函数，分别是regex_match,regex_replace,regex_search 具体见下。我在这里只介绍在ACM里常用的一两个用法，具体了解还请点开各自的官方文档链接，上面有实例代码，非常好懂。 regex_match regex_match 用来将正则表达式与整个字符串进行匹配，返回一个布尔值，如果匹配成功，返回true，…