URAL – 1960 Palindromes and Super Abilities 回文自动机
Palindromes and Super Abilities 回文自动机 Source URAL - 1960 My Solution 题意：逐个字符的添加一个字符串，问每添加一个字符显存的字符串的总不同的回文子串的个数。 回文树自动机 首先推荐篇比较好的讲回文…
HDU – 4622 Reincarnation 后缀自动机
Reincarnation 后缀自动机 Source HDU - 4622 My Solution 题意：给出一个长度<=2000的字符串，然后给出q<=10000个询问，为s[l,r]内有多少个不同的子串。 后缀自动机 首先n <= 2000，故可以用O(n^2)的算…
SPOJ – LCS Longest Common Substring 后缀自动机
Longest Common Substring 后缀自动机 Source SPOJ - LCS My Solution 题意：求两个字符串的最长公共子串。 后缀自动机 看了很久 WJMZBMR 讲后缀自动机的ppt才大致把后缀自动机搞懂^_^, 此外附上两个比较好的…
Codeforces Round #402 (Div. 2) D. String Game 二分+优先队列+字符串匹配
D. String Game 二分+优先队列+字符串匹配 My Solution 题意：给出文本串和目标串，然后给出一个文本串删除字符的序列，从a1~an，要求删除s[a1 ~ ak]时剩下的字符串依然可以匹配，求尽可能大的k。 二分+优…
Codeforces Round #401 (Div. 2) D. Cloud of Hashtags 贪心、字符串处理
D. Cloud of Hashtags 贪心、字符串处理 My Solution 题意：给出n个字符串，要求删除尽可能短的后缀，是这n个字符串的字典序是非递减的。 贪心、字符串处理 可知，可以且需要从倒数第二个字符串开始考虑删…
Codeforces Round #401 (Div. 2) C. Alyona and Spreadsheet last数组、预处理、优化
C. Alyona and Spreadsheet last数组、预处理、优化 My Solution 题意：给出n*m个树，询问第i行到第j行是否至少有一列是非递减序列。 预处理、last数组、优化 用 vector f[maxn]，其中f[i]表示第i列的数据…
CSU – 1632 Repeated Substrings 后缀数组、distinct substring
Repeated Substrings 后缀数组、distinct substring Source CSU - 1632 My Solution 题意：给出一个字符串，找出出现2次及以上的子串的种数。 后缀数组 跑出sa数组和height数组，然后从i = 2 ~ n遍历，每次 ans +=…
POJ – 3882 Stammering Aliens 后缀数组、二分、二叉堆、ST表
Stammering Aliens 后缀数组、二分、二叉堆、ST表 Source POJ - 3882 2009 South Western European Regional Contest My Solution 题意：给出一个字符串，要求找出至少出现m次的最长子串长度。 后缀数组、二分、二…
HDU – 2457 DNA repair AC自动机+dp
D - DNA repair AC自动机+dp Source HDU 2457 My Solution 题意：给出n个模式串，给出一个主串，要求在主创上改动尽可能少的字符，使任一模式串不在主串中出现。 AC自动机+dp 按照一般的 AC自动机+dp转移 的模式(…
POJ – 3415 Common Substrings 后缀数组+单调栈+前缀和
Common Substrings 后缀数组+单调栈+前缀和 Source POJ - 3415 My Solution 题意：给出两个字符串，求出它们的相同的长度至少为k的子串的个数。 后缀数组+单调栈+前缀和 把a、b这两个字符串用'#'连起来，然后求出…
HDU – 4763 Theme Section KMP
C - Theme Section KMP Source HDU - 4763 My Solution 题意：给出一个字符串，找出一个尽可能长的子串，要求其在字符串的开头结尾中间都出现且不能有重叠。 KMP 先对主串跑出next数组，然后对于ptr = n，从nxt[n]…
UESTC 1040 Great Inversion 逆序数、构造
Great Inversion 逆序数、构造 Source The 13th UESTC Programming Contest Preliminary The question is from here. My Solution 本来是用贪心法，如果填一个个数就够那么填上去然后返回，如果不够则把m填…
Codeforces Round #397 (Div. 1 + Div. 2 combined) D. Artsem and Saunders 映射+构造
D. Artsem and Saunders 映射+构造 My Solution 题意：给出一个函数f(x) 属于[1,x]，然后要求确定一个数m，使x属于[1,n]，g[x]属于[1,m], x输入[1,m] h[x]属于[1,n], 当存在m时，求m最小时的gx和hx。 映射…
Codeforces Round #394 (Div. 2) D. Dasha and Very Difficult Problem 贪心
D. Dasha and Very Difficult Problem 贪心 My Solution 题意：数组a、b，由bi - ai 得到ci，要求每个ci都不相同，给定a和p(p为c的压缩之后的保持大小顺序不变的序列)，求b。 贪心 可以令 ci = pi + k，因…
Codeforces Round #394 (Div. 2) C. Dasha and Password 贪心+预处理+枚举
C. Dasha and Password 贪心+预处理+枚举 My Solution 题意：长度为n的密码必须包含至少一个字母一个数字一个非字母非数字的字符，给出n个长度为m的字符串，每个串取一个字符，要求移动最少的步数使所成的密码为…
Gym – 100507G G. The Debut Album 数位dp+内存优化
G - The Debut Album 数位dp+内存优化 Source Gym - 100507G ACM ICPC 2014-2015. NEERC. Eastern Subregional Contest Yekaterinburg, October 11, 2014 My Solution 题意：最多连续a个1，最多连续b个2，…
Gym – 101147H H. Commandos DAG
H - 记忆里在微甜 DAG Source Gym - 101147H My Solution 题意：即普通的DAG加了一维。 DAG上的dp 三维的有向无环图上dp， dp[k][i][j] = max(dp[k][i][j], dp[k][i+1][j] + mp[k][i][j]); dp[k][i][j] = max(dp[k…
HDU – 5384 Danganronpa AC自动机、简单题
Danganronpa AC自动机、简单题 Source HDU - 5384 My Solution 题意：给出n个主串、m个模式串，求每个主串Ai中这m个模式串出现的次数和。 AC自动机、简单题 把n个模版串丢到一个队列里，然后读取m个模式串建立AC自…
UVALive – 4294 Shuffle 映射+取反+最大区间覆盖
Shuffle 映射+取反+最大区间覆盖 Source UVALive - 4294 My Solution 题意：歌曲种数为s，记录的数量为n，然后给出这个n个记录，每s个歌会随机播放一遍，然后开始重新随机播放这s首歌，为未来可能在几个点进…
URAL – 2102 Michael and Cryptography 分解质因数+优化
C - Michael and Cryptography 分解质因数+优化 Source URAL - 2102 MySolution 题意：每一个数都可以表示为 ai^bi + ai+1^bi+1 + ...... an^bn，判断 sigma bi 是否等于 20 分解质因数+优化 用O(sqrt(n))的分解…
