字符串 - Page 2

2015全国互测 1
计算给定n,m对于[1,n]不包含m作为其子串的数k求\(\sum_ke^{k/n}\)kmp预处理后数位dp。。。[crayon-6768293278c3c936399516/]移动小x有n张卡片和n个卡槽，现在第i张卡片在ai卡槽中。小x每次可以把一个在a位置的卡片移动到b位置，消耗的代价为min(|a−b|,n−|a−b|)，每张卡片可以被移动多次。小x想使得每个卡槽有且仅有一张卡片，请你告诉他最少需要的代价是多少。环形分金币参加白书[crayon-6768293278c4d410411848/]分离小x喜欢分...
02015年5月17日3,508KMP,深度搜索,数位动规

「BZOJ3160」万径人踪灭
大爷题解传送门：http://blog.csdn.net/popoqqq/article/details/42193259[crayon-6768293279064072106179/]
02015年5月1日7,719manacher,快速傅里叶变换
「BZOJ3926」[ZJOI2015] 诸神眷顾的幻想乡
陈老师语文水平高超陈老师的博客：http://wjmzbmr.com/archives/zjoi-2015-day-1%E9%A2%98%E8%A7%A3/[crayon-6768293279421021179188/]
02015年5月1日7,275深度搜索,后缀自动机
「BZOJ3676」[Apio2014] 回文串
Description考虑一个只包含小写拉丁字母的字符串s。我们定义s的一个子串t的“出现值”为t在s中的出现次数乘以t的长度。请你求出s的所有回文子串中的最大出现值。Input输入只有一行，为一个只包含小写字母(a-z)的非空字符串s。Output输出一个整数，为逝查回文子串的最大出现值。SampleInput「样例输入l」abacaba「样例输入2]wwwSampleOutput「样例输出l」7「样例输出2]4HINT一个串是回文的，当且仅当它从左到右读和从右到...
182015年4月23日11,200后缀自动机,manacher
「BZOJ3998」[TJOI2015] 弦论
Description对于一个给定长度为N的字符串，求它的第K小子串是什么。Input 第一行是一个仅由小写英文字母构成的字符串S第二行为两个整数T和K，T为0则表示不同位置的相同子串算作一个。T=1则表示不同位置的相同子串算作多个。K的意义如题所述。Output输出仅一行，为一个数字串，为第K小的子串。如果子串数目不足K个，则输出-1SampleInputaabc03SampleOutputaabHINT N<=5*10^5T<2K<=10^9题解日常o...
62015年4月22日7,202后缀自动机
「BZOJ2946」[POI2000] 公共串
Description 给出几个由小写字母构成的单词，求它们最长的公共子串的长度。任务：l 读入单词l 计算最长公共子串的长度l 输出结果Input文件的第一行是整数n，1<=n<=5，表示单词的数量。接下来n行每行一个单词，只由小写字母组成，单词的长度至少为1，最大为2000。Output仅一行，一个整数，最长公共子串的长度。SampleInput3abcbbcaacbcSampleOutput２题解后缀自动机...
12015年4月21日5,381后缀自动机
「POJ1743」Musical Theme
DescriptionAmusicalmelodyisrepresentedasasequenceofN(1<=N<=20000)notesthatareintegersintherange1..88,eachrepresentingakeyonthepiano.Itisunfortunatebuttruethatthisrepresentationofmelodiesignoresthenotionofmusicaltiming;but,thisprogrammingtaskisaboutnotesandnottimings.Manycomposersstructuretheirmusicaroundarepeating&qout;theme&qout;,which,beingasubsequenceofanentiremelody,isasequ...
12015年4月20日6,353后缀数组,后缀自动机
UOJ Easy Round #1
http://vfleaking.blog.uoj.ac/blog/15uoj题解写的太好了。。。「UER#1」猜数[crayon-676829327bb85625825251/]「UER#1」跳蚤OS[crayon-676829327bb8d500583097/]「UER#1」DZYLovesGraph[crayon-676829327bb93414991322/] ...
02015年4月13日6,799并查集,AC自动机
[sdoi2008] Sandy的卡片
时限0.5sSandy和Sue的热衷于收集干脆面中的卡片。然而，Sue收集卡片是因为卡片上漂亮的人物形象，而Sandy则是为了积攒卡片兑换超炫的人物模型。每一张卡片都由一些数字进行标记，第i张卡片的序列长度为Mi，要想兑换人物模型，首先必须要集够N张卡片，对于这N张卡片，如果他们都有一个相同的子串长度为k，则可以兑换一个等级为k的人物模型。相同的定义为：两个子串长度相同且一个串的全部元素加上一个数就会变成另一个串。S...
72015年4月10日5,475KMP,后缀数组
「BZOJ3238」[Ahoi2013] 差异
DescriptionInput一行，一个字符串SOutput一行，一个整数，表示所求值SampleInputcacaoSampleOutput54HINT2<=N<=500000,S由小写英文字母组成题解显然后缀数组不是正确姿势。。。不过还是说说后缀数组的做法吧，bzoj总时限20s是能过的SA+rmq求lcp应该烂大街了，这题还不用rmq。。。首先求出h数组考虑h[i]在哪些区间内会成为最小值，这个用两次单调栈很容易就能解决还要处理一下由于h[i]可能相同造成的重复计数...
62015年4月9日6,194后缀数组,单调栈
「uoj35」后缀排序
这是一道模板题。读入一个长度为n的由小写英文字母组成的字符串，请把这个字符串的所有非空后缀按字典序从小到大排序，然后按顺序输出后缀的第一个字符在原串中的位置。位置编号为1到n。除此之外为了进一步证明你确实有给后缀排序的超能力，请另外输出n−1个整数分别表示排序后相邻后缀的最长公共前缀的长度。输入格式一行一个长度为n的仅包含小写英文字母的字符串。输出格式第一行n个整数，第i个整数表示排名为i的后缀的第一个字符...
22015年4月9日4,482后缀数组
NOI2014动物园
Description近日，园长发现动物园中好吃懒做的动物越来越多了。例如企鹅，只会卖萌向游客要吃的。为了整治动物园的不良风气，让动物们凭自己的真才实学向游客要吃的，园长决定开设算法班，让动物们学习算法。某天，园长给动物们讲解KMP算法。园长：“对于一个字符串S，它的长度为L。我们可以在O(L)的时间内，求出一个名为next的数组。有谁预习了next数组的含义吗？”熊猫：“对于字符串S的前i个字符构成的子串，既是它的后...
112015年2月8日6,375KMP