• 「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,337ST表,后缀数组
  • 「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,877后缀数组
  • 「BZOJ1954」Pku3764 The xor – longest Path

    「BZOJ1954」Pku3764 The xor - longest Path

    Description给定一棵n个点的带权树,求树上最长的异或和路径InputTheinputcontainsseveraltestcases.Thefirstlineofeachtestcasecontainsanintegern(1<=n<=100000),Thefollowingn-1lineseachcontainsthreeintegersu(0<=u<n),v(0<=v<n),w(0<=w<2^31),whichmeansthereisanedgebetweennodeuandvoflengthw.OutputForeachtestcaseoutputthexor-lengthofthexor-longestpath.SampleInput4123234246Samp...

    02014年12月16日2,780贪心,字典树
  • 「BZOJ2882」工艺

    「BZOJ2882」工艺

    Description小敏和小燕是一对好朋友。他们正在玩一种神奇的游戏,叫Minecraft。他们现在要做一个由方块构成的长条工艺品。但是方块现在是乱的,而且由于机器的要求,他们只能做到把这个工艺品最左边的方块放到最右边。他们想,在仅这一个操作下,最漂亮的工艺品能多漂亮。两个工艺品美观的比较方法是,从头开始比较,如果第i个位置上方块不一样那么谁的瑕疵度小,那么谁就更漂亮,如果一样那么继续比较第i+1个方块。如果全都一样...

    02014年12月15日2,266字符串,其它
  • 「BZOJ1355」[Baltic2009] Radio Transmission

    「BZOJ1355」[Baltic2009] Radio Transmission

    Description给你一个字符串,它是由某个字符串不断自我连接形成的。但是这个字符串是不确定的,现在只想知道它的最短长度是多少.Input第一行给出字符串的长度,1<L≤1,000,000.第二行给出一个字符串,全由小写字母组成.Output输出最短的长度SampleInput8cabcabcaSampleOutput3HINT对于样例,我们可以利用"abc"不断自我连接得到"abcabcabc",读入的cabcabca,是它的子串题解kmp。。。答案是n-fail[n],随便画画应该能得到...

    02014年12月14日2,641KMP
  • 「CF494B」Obsessive String

    「CF494B」Obsessive String

    Hamedhasrecentlyfoundastringtandsuddenlybecamequitefondofit.Hespentseveraldaystryingtofindalloccurrencesoftinotherstringshehad.Finallyhebecametiredandstartedthinkingaboutthefollowingproblem.Givenastringshowmanywaysaretheretoextractk ≥ 1non-overlappingsubstringsfromitsuchthateachofthemcontainsstringtasasubstring?Moreformally,youneedtocalculatethenumberofwaystochoosetwosequencesa1, a2, ......

    02014年12月14日1,904递推与动规,KMP
  • 「BZOJ3790」神奇项链

    「BZOJ3790」神奇项链

    Description母亲节就要到了,小H准备送给她一个特殊的项链。这个项链可以看作一个用小写字母组成的字符串,每个小写字母表示一种颜色。为了制作这个项链,小H购买了两个机器。第一个机器可以生成所有形式的回文串,第二个机器可以把两个回文串连接起来,而且第二个机器还有一个特殊的性质:假如一个字符串的后缀和一个字符串的前缀是完全相同的,那么可以将这个重复部分重叠。例如:aba和aca连接起来,可以生成串abaaca或abaca。...

    02014年12月11日3,145树状数组,manacher
  • NOI2011阿狸的打字机

    NOI2011阿狸的打字机

    Description 阿狸喜欢收藏各种稀奇古怪的东西,最近他淘到一台老式的打字机。打字机上只有28个按键,分别印有26个小写英文字母和'B'、'P'两个字母。经阿狸研究发现,这个打字机是这样工作的:l输入小写字母,打字机的一个凹槽中会加入这个字母(这个字母加在凹槽的最后)。l按一下印有'B'的按键,打字机凹槽中最后一个字母会消失。l按一下印有'P'的按键,打字机会在纸上打印出凹槽中现有的所有字母并换行,但凹槽中的字母不会消...

    32014年12月6日7,306dfs序,AC自动机,树状数组
  • 「BZOJ2938」[POI2000] 病毒

    「BZOJ2938」[POI2000] 病毒

    Description二进制病毒审查委员会最近发现了如下的规律:某些确定的二进制串是病毒的代码。如果某段代码中不存在任何一段病毒代码,那么我们就称这段代码是安全的。现在委员会已经找出了所有的病毒代码段,试问,是否存在一个无限长的安全的二进制代码。示例:例如如果{011,11,00000}为病毒代码段,那么一个可能的无限长安全代码就是010101…。如果{01,11,000000}为病毒代码段,那么就不存在一个无限长的安全代码。任务:请写一个...

    02014年12月6日4,512深度搜索,AC自动机
  • 「BZOJ2342」[SHOI2011] 双倍回文

    「BZOJ2342」[SHOI2011] 双倍回文

    Description Input输入分为两行,第一行为一个整数,表示字符串的长度,第二行有个连续的小写的英文字符,表示字符串的内容。Output输出文件只有一行,即:输入数据中字符串的最长双倍回文子串的长度,如果双倍回文子串不存在,则输出0。SampleInput16ggabaabaabaaballSampleOutput12HINTN<=500000题解p[i]表示i和i+1为中心的最长回文子串长度/2(str[i-k]=str[i+1+k])。。。用manacherOn计算p数组题目要求计...

    02014年12月3日4,853manacher
  • 「vijos1382」寻找主人

    「vijos1382」寻找主人

    Description给定两个项链的表示,判断他们是否可能是一条项链。Input输入文件只有两行,每行一个由0至9组成的字符串,描述一个项链的表示(保证项链的长度是相等的)。Output如果两条项链不可能同构,那么输出’No’,否则的话,第一行输出一个’Yes’,第二行输出该项链的字典序最小的表示。设L=项链长度,对于50%的数据L<=100000;对于100%的数据L<=1000000。题解http://wenku.baidu.com/link?url=Jtn398dsc9nSs...

    02014年12月3日1,858字符串,其它
  • 「CFgym100514I」Peace of AmericanPie

    「CFgym100514I」Peace of AmericanPie

    Youaregivenanencryptedstring,encryptedusingacertainalgorithm.Decryptit!InputThefirstandonlylineofinputcontainsastrings,eachcharacterofsiseither0or1.(8 ≤ |s| ≤ 8 × 104)OutputPrinttheoriginalstring.Sampletest(s)input[crayon-5b299099cf52b583828200/]output[crayon-5b299099cf533320918211/]input[crayon-5b299099cf536281867969/]output[crayon-5b299099cf539431677020/]input[crayon-5b299099cf53...

    02014年11月2日1,790密码学