• 2014PKU计算概论入学测试

    2014PKU计算概论入学测试

    poj1961Periodkmp求出fail数组后,前i个的重复子串就是i-fail(i)[crayon-5b519a03288ca846441930/]poj1276 CashMachine用f(i,j)表示前i种面值,达到j的面值和,所需要的第i种钞票的最少数量[crayon-5b519a03288d8444830058/]poj1702 Eva'sBalance先把n转为3进制,若p位为2,就在左盘放3^p,进位若p位为1,就在右盘放3^p[crayon-5b519a03288e1963350895/]poj1273 DrainageDitches大名鼎鼎的草地排水,网络流模板[crayon-5...

  • 「BZOJ3230」相似子串

    「BZOJ3230」相似子串

    DescriptionInput输入第1行,包含3个整数N,Q。Q代表询问组数。第2行是字符串S。接下来Q行,每行两个整数i和j。(1≤i≤j)。Output输出共Q行,每行一个数表示每组询问的答案。如果不存在第i个子串或第j个子串,则输出-1。SampleInput53ababa3559810SampleOutput1816-1HINT样例解释第1组询问:两个子串是“aba”,“ababa”。f=32+32=18。第2组询问:两个子串是“ababa”,“baba”。f=02+42=16。第3组询问:不存在...

    12015年7月9日3,420后缀数组
  • 「POJ1743」Musical Theme

    「POJ1743」Musical Theme

    DescriptionAmusicalmelodyisrepresentedasasequenceofN(1<=N<=20000)notesthatareintegersintherange1..88,eachrepresentingakeyonthepiano.Itisunfortunatebuttruethatthisrepresentationofmelodiesignoresthenotionofmusicaltiming;but,thisprogrammingtaskisaboutnotesandnottimings.Manycomposersstructuretheirmusicaroundarepeating&qout;theme&qout;,which,beingasubsequenceofanentiremelody,isasequ...

    12015年4月20日4,198后缀数组,后缀自动机
  • [sdoi2008] Sandy的卡片

    [sdoi2008] Sandy的卡片

    时限0.5sSandy和Sue的热衷于收集干脆面中的卡片。然而,Sue收集卡片是因为卡片上漂亮的人物形象,而Sandy则是为了积攒卡片兑换超炫的人物模型。每一张卡片都由一些数字进行标记,第i张卡片的序列长度为Mi,要想兑换人物模型,首先必须要集够N张卡片,对于这N张卡片,如果他们都有一个相同的子串长度为k,则可以兑换一个等级为k的人物模型。相同的定义为:两个子串长度相同且一个串的全部元素加上一个数就会变成另一个串。S...

    72015年4月10日3,345KMP,后缀数组
  • 「BZOJ3238」[Ahoi2013] 差异

    「BZOJ3238」[Ahoi2013] 差异

    DescriptionInput一行,一个字符串SOutput一行,一个整数,表示所求值SampleInputcacaoSampleOutput54HINT2<=N<=500000,S由小写英文字母组成题解显然后缀数组不是正确姿势。。。不过还是说说后缀数组的做法吧,bzoj总时限20s是能过的SA+rmq求lcp应该烂大街了,这题还不用rmq。。。首先求出h数组考虑h[i]在哪些区间内会成为最小值,这个用两次单调栈很容易就能解决还要处理一下由于h[i]可能相同造成的重复计数...

    62015年4月9日4,455后缀数组,单调栈
  • 「uoj35」后缀排序

    「uoj35」后缀排序

    这是一道模板题。读入一个长度为n的由小写英文字母组成的字符串,请把这个字符串的所有非空后缀按字典序从小到大排序,然后按顺序输出后缀的第一个字符在原串中的位置。位置编号为1到n。除此之外为了进一步证明你确实有给后缀排序的超能力,请另外输出n−1个整数分别表示排序后相邻后缀的最长公共前缀的长度。输入格式一行一个长度为n的仅包含小写英文字母的字符串。输出格式第一行n个整数,第i个整数表示排名为i的后缀的第一个字符...

    22015年4月9日2,461后缀数组
  • 「CODEVS3160」最长公共子串

    「CODEVS3160」最长公共子串

    题目描述Description给出两个由小写字母组成的字符串,求它们的最长公共子串的长度。输入描述InputDescription读入两个字符串输出描述OutputDescription输出最长公共子串的长度样例输入SampleInput[crayon-5b519a032c710753782119/]样例输出SampleOutput27数据范围及提示DataSize&Hint单个字符串的长度不超过100000题解算法1:后缀数组同poj2774bzoj挂了没事干。。。2014.9.21*12015.2.6*1[crayon-5b519a032c71891...

    72015年2月6日4,053后缀数组,后缀自动机
  • 「POJ3693」Maximum repetition substring

    「POJ3693」Maximum repetition substring

    DescriptionTherepetitionnumberofastringisdefinedasthemaximumnumberRsuchthatthestringcanbepartitionedintoRsameconsecutivesubstrings.Forexample,therepetitionnumberof"ababab"is3and"ababa"is1.Givenastringcontaininglowercaseletters,youaretofindasubstringofitwithmaximumrepetitionnumber.InputTheinputconsistsofmultipletestcases.Eachtestcasecontainsexactlyoneline,whichgivesanon-emptystringconsisti...

    22015年1月14日3,428ST表,后缀数组
  • 「hdu3518」Boring counting

    「hdu3518」Boring counting

    ProblemDescription035nowfacedatoughproblem,hisenglishteachergiveshimastring,whichconsistswithnlowercaseletter,hemustfigureouthowmanysubstringsappearatleasttwice,moreover,suchapearancescannotoverlapeachother.Takeaaaaasanexample.”a”apearsfourtimes,”aa”apearstwotimeswithoutoverlaping.however,aaacan’tapearmorethanonetimewithoutoverlaping.sincewecanget“aaa”from[0-2](Thepositionofstringbegins...

    02015年1月13日1,909后缀数组
  • 「POJ2774」Long Long Message

    「POJ2774」Long Long Message

    DescriptionThelittlecatismajoringinphysicsinthecapitalofByterland.Apieceofsadnewscomestohimthesedays:hismotherisgettingill.Beingworriedaboutspendingsomuchonrailwaytickets(Byterlandissuchabigcountry,andhehastospend16shoursontraintohishometown),hedecidedonlytosendSMSwithhismother.Thelittlecatlivesinanunrichfamily,sohefrequentlycomestothemobileservicecenter,tocheckhowmuchmoneyhehasspentonS...

    02014年9月15日2,505后缀数组
  • 「BZOJ2251」[2010BJ Wc] 外星联络

    「BZOJ2251」[2010BJ Wc] 外星联络

    Description小P在看过电影《超时空接触》(Contact)之后被深深的打动,决心致力于寻找外星人的事业。于是,他每天晚上都爬在屋顶上试图用自己的收音机收听外星人发来的信息。虽然他收听到的仅仅是一些噪声,但是他还是按照这些噪声的高低电平将接收到的信号改写为由0和1构成的串,并坚信外星人的信息就隐藏在其中。他认为,外星人发来的信息一定会在他接受到的01串中重复出现,所以他希望找到他接受到的01串中所有重复出现次数大...

    32014年9月4日3,139后缀数组
  • 「JoyOI1860」后缀数组

    「JoyOI1860」后缀数组

    描述Description我们定义一个字符串的后缀suffix(i)表示从s[i]到s[length(s)]这段子串。后缀数组(Suffix array)SA[i]中存放着一个排列,满足suffix(sa[i])<suffix(sa[i+1]) 按照字典序方式比较定义height[i]表示suffix(sa[i])与suffix(sa[i-1])之间的最长公共前缀长度,其中height[1]=0你的任务就是求出SA和height这两个数组。字符串长度<=200000输入格式InputFormat一行,为描述中的字符串(仅会出现小写字母)...

    62014年9月4日2,933后缀数组
1 / 2 1 2 下一页 »