• 【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日1,503贪心,字典树
  • 【bzoj2882】工艺

    【bzoj2882】工艺

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

    02014年12月15日1,240字符串,其它
  • 【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日1,401KMP
  • 【cf494B】Obsessive String

    【cf494B】Obsessive String

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

    02014年12月14日1,113递推与动规,KMP
  • 【bzoj3790】神奇项链

    【bzoj3790】神奇项链

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

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

    NOI2011阿狸的打字机

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

    32014年12月6日3,346dfs序,AC自动机,树状数组
  • 【bzoj2938】[Poi2000]病毒

    【bzoj2938】[Poi2000]病毒

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

    02014年12月6日2,294深度搜索,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日2,643manacher
  • 【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,167字符串,其它
  • 【cfgym100514I】Peace of AmericanPie

    【cfgym100514I】Peace of AmericanPie

    Youaregivenanencryptedstring,encryptedusingacertainalgorithm.Decryptit!InputThefirstandonlylineofinputcontainsastrings,eachcharacterofsiseither0or1.(8 ≤ |s| ≤ 8 × 104)OutputPrinttheoriginalstring.Sampletest(s)input[crayon-58d5b1e10f72a803766219/]output[crayon-58d5b1e10f732000740340/]input[crayon-58d5b1e10f735505493871/]output[crayon-58d5b1e10f739203656649/]input[crayon-58d5b1e10f73...

    02014年11月2日1,152密码学
  • 【cfgym100514R】6227020800

    【cfgym100514R】6227020800

    Youaregivenanencryptedstring,encryptedusingacertainalgorithm.Decryptit!InputThefirstandsinglelineofinputcontainsastrings,whicheachofit'scharactersisalowercaseEnglishletter.(1 ≤ |s| ≤ 105)OutputPrinttheoriginalstring.Sampletest(s)input[crayon-58d5b1e10fb65500725995/]output[crayon-58d5b1e10fb6d341324957/]input[crayon-58d5b1e10fb71942105425/]output[crayon-58d5b1e10fb73972636965/]input[c...

    02014年11月2日814密码学
  • 【bzoj2145】悄悄话

    【bzoj2145】悄悄话

    试题来源  2011中国国家集训队命题答辩问题描述  在这个有话不直说的年代,密码学越来越被广泛接受。我们引用经典的“凯撒密码”。在英文中,凯撒加密只对26个字母生效(分大小写)我们按照a到z来排字母。凯撒加密的原理就是把原文的每一个字母都按顺序往后移K位。这个K将被作为密钥。(’a’往后移变成’b’,’z’往后移会变成’a’)(0≤K≤25)现在给出一系列用凯撒加密的英文句子,请你编写程序逐句翻译。也就是说,请...

    92014年10月23日1,714密码学
  • 【cf471D】MUH and Cube Walls

    【cf471D】MUH and Cube Walls

    PolarbearsMenshykovandUsladafromthezooofSt.PetersburgandelephantHoracefromthezooofKievgotholdoflotsofwoodencubessomewhere.Theystartedmakingcubetowersbyplacingthecubesoneontopoftheother.Theydefinedmultipletowersstandinginalineasawall.Awallcanconsistoftowersofdifferentheights.Horacewasthefirsttofinishmakinghiswall.Hecalledhiswallanelephant.Thewallconsistsofwtowers.Thebearsalsofinishedm...

    02014年9月27日1,173KMP