• 关于回文树的理解 by yyb

    关于回文树的理解 by yyb

    前言这段时间搞字符串上了瘾?看起来是的那就继续搞吧Part1一些名词回文串不想解释什么意思回文子串一个串的子串,它是回文串,那么它就是回文子串最长回文后缀对于一个长度小于自己的后缀,如果它是回文串,并且不存在比它更长的回文后缀,那么它就是最长回文后缀最长回文前缀基本和上面一样Part2回文树的形态长成啥样啊?我们很容易知道,回文串有两种,一种长度是奇数,一种长度是偶数而在回文树上走,我们肯定不是一次只在后...

    02018年2月22日3研究总结
  • [HDU5977]Garden of Eden(点分治,高维前缀和)

    [HDU5977]Garden of Eden(点分治,高维前缀和)

    DescriptionWhenGodmadethefirstman,heputhimonabeautifulgarden,theGardenofEden.HereAdamlivedwithallanimals.GodgaveAdameternallife.ButAdamwaslonelyinthegarden,soGodmadeEve.WhenAdamwasasleeponenight,GodtookaribfromhimandmadeEvebesidehim.Godsaidtothem,“hereintheGarden,youcandoeverything,butyoucannoteatapplesfromthetreeofknowledge.”Oneday,Satancametothegarden.Hechangedintoasnakea...

  • [SPOJ TLE]Time Limit Exceeded(数位DP,计数DP,高维前缀和)

    [SPOJ TLE]Time Limit Exceeded(数位DP,计数DP,高维前缀和)

    DescriptionGivenintegersN(1≤N≤50)andM(1≤M≤15),computethenumberofsequencesa1,...,aNsuchthat:0≤ai<2Maiisnotdivisiblebyci(0<ci≤2M)ai&ai+1=0(thatis,aiandai+1havenocommonbitsintheirbinaryrepresentation)HttpSPOJTag动态规划,高维前缀和题目大意给出一列数,要求求出满足条件的数列的方案数。解决思路由数据范围容易想到,设\(F[i][j]\)表示前\(i\)个数,第\(i\...

  • [BZOJ2152/Luogu2634]聪聪可可(点分治)

    [BZOJ2152/Luogu2634]聪聪可可(点分治)

    Description聪聪和可可是兄弟俩,他们俩经常为了一些琐事打起来,例如家中只剩下最后一根冰棍而两人都想吃、两个人都想玩儿电脑(可是他们家只有一台电脑)……遇到这种问题,一般情况下石头剪刀布就好了,可是他们已经玩儿腻了这种低智商的游戏。他们的爸爸快被他们的争吵烦死了,所以他发明了一个新游戏:由爸爸在纸上画n个“点”,并用n-1条“边”把这n个“点”恰好连通(其实这就是一棵树)。并且每条“边”上都有一个数。接下...

    02018年2月22日3点分治,BZOJ,Luogu
  • [POJ1741]Tree(点分治)

    [POJ1741]Tree(点分治)

    DescriptionGiveatreewithnvertices,eachedgehasalength(positiveintegerlessthan1001).Definedist(u,v)=Themindistancebetweennodeuandv.Giveanintegerk,foreverypair(u,v)ofverticesiscalledvalidifandonlyifdist(u,v)notexceedk.Writeaprogramthatwillcounthowmanypairswhicharevalidforagiventree.HttpHDUTag点分治题目大意给出一棵树,求其中路径长度不超过一个给定的数\(K\)的点对个数解决思路考虑点分治...

    02018年2月22日3点分治,POJ
  • [HDU3746]Cyclic Nacklace(KMP)

    [HDU3746]Cyclic Nacklace(KMP)

    DescriptionCCalwaysbecomesverydepressedattheendofthismonth,hehascheckedhiscreditcardyesterday,withoutanysurprise,thereareonly99.9yuanleft.heistoodistressedandthinkingabouthowtotideoverthelastdays.Beinginspiredbytheentrepreneurialspiritof"HDUCakeMan",hewantstosellsomelittlethingstomakemoney.Ofcourse,thisisnotaneasytask.AsChristmasisaroundthecorner,Boysarebusyinchoosingchristmaspresents...

    02018年2月22日7KMP,HDU
  • [BZOJ2753/Luogu2573][SCOI2012]滑雪与时间胶囊(生成树)

    [BZOJ2753/Luogu2573][SCOI2012]滑雪与时间胶囊(生成树)

    Descriptiona180285非常喜欢滑雪。他来到一座雪山,这里分布着M条供滑行的轨道和N个轨道之间的交点(同时也是景点),而且每个景点都有一编号i(1<=i<=N)和一高度Hi。a180285能从景点i滑到景点j当且仅当存在一条i和j之间的边,且i的高度不小于j。与其他滑雪爱好者不同,a180285喜欢用最短的滑行路径去访问尽量多的景点。如果仅仅访问一条路径上的景点,他会觉得数量太少。于是a180285拿出了他随身携带的时间胶囊。这是...

  • [BZOJ3670/Luogu2375][Noi2014]动物园(KMP)

    [BZOJ3670/Luogu2375][Noi2014]动物园(KMP)

    Description近日,园长发现动物园中好吃懒做的动物越来越多了。例如企鹅,只会卖萌向游客要吃的。为了整治动物园的不良风气,让动物们凭自己的真才实学向游客要吃的,园长决定开设算法班,让动物们学习算法。某天,园长给动物们讲解KMP算法。园长:“对于一个字符串S,它的长度为L。我们可以在O(L)的时间内,求出一个名为next的数组。有谁预习了next数组的含义吗?”熊猫:“对于字符串S的前i个字符构成的子串,既是它的后...

    02018年2月21日17KMP,NOI,BZOJ,Luogu
  • [HDU4763]Theme Section(KMP)

    [HDU4763]Theme Section(KMP)

    DescriptionIt'stimeformusic!Alotofpopularmusiciansareinvitedtojoinusinthemusicfestival.Eachofthemwillplayoneoftheirrepresentativesongs.Tomaketheprogramsmoreinterestingandchallenging,thehostsaregoingtoaddsomeconstraintstotherhythmofthesongs,i.e.,eachsongisrequiredtohavea'themesection'.Thethemesectionshallbeplayedatthebeginning,themiddle,andtheendofeachsong.Morespecifically,givenathemesection...

    02018年2月21日16KMP,HDU
  • [BZOJ1143][CTSC2008]祭祀river(二分图)

    [BZOJ1143][CTSC2008]祭祀river(二分图)

    Description在遥远的东方,有一个神秘的民族,自称Y族。他们世代居住在水面上,奉龙王为神。每逢重大庆典,Y族都会在水面上举办盛大的祭祀活动。我们可以把Y族居住地水系看成一个由岔口和河道组成的网络。每条河道连接着两个岔口,并且水在河道内按照一个固定的方向流动。显然,水系中不会有环流。由于人数众多的原因,Y族的祭祀活动会在多个岔口上同时举行。出于对龙王的尊重,这些祭祀地点的选择必须非常慎重。准确地说,Y...

    02018年2月20日21CTSC,二分图,BZOJ
  • [BZOJ1924/Luogu2403][Sdoi2010]所驼门王的宝藏(Tarjan,动态规划)

    [BZOJ1924/Luogu2403][Sdoi2010]所驼门王的宝藏(Tarjan,动态规划)

    Description在宽广的非洲荒漠中,生活着一群勤劳勇敢的羊驼家族。被族人恭称为“先知”的AlpacaL.Sotomon是这个家族的领袖,外人也称其为“所驼门王”。所驼门王毕生致力于维护家族的安定与和谐,他曾亲自率军粉碎河蟹帝国主义的野蛮侵略,为族人立下赫赫战功。所驼门王一生财宝无数,但因其生性节俭低调,他将财宝埋藏在自己设计的地下宫殿里,这也是今天HenryCurtis故事的起点。Henry是一个爱财如命的贪婪家伙,而又非常聪...

  • [BZOJ1064/Luogu1477][Noi2008]假面舞会(图论,gcd)

    [BZOJ1064/Luogu1477][Noi2008]假面舞会(图论,gcd)

    Description一年一度的假面舞会又开始了,栋栋也兴致勃勃的参加了今年的舞会。今年的面具都是主办方特别定制的。每个参加舞会的人都可以在入场时选择一个自己喜欢的面具。每个面具都有一个编号,主办方会把此编号告诉拿该面具的人。为了使舞会更有神秘感,主办方把面具分为k(k≥3)类,并使用特殊的技术将每个面具的编号标在了面具上,只有戴第i类面具的人才能看到戴第i+1类面具的人的编号,戴第k类面具的人能看到戴第1类面具的人的...

    02018年2月20日13NOI,图论,BZOJ,Luogu
  • [HDU6153]A Secret(KMP)

    [HDU6153]A Secret(KMP)

    DescriptionTodayisthebirthdayofSF,soVSgivestwostringsS1,S2toSFasapresent,whichhaveabigsecret.SFisinterestedinthissecretandaskVShowtogetit.TherearethethingsthatVStell:Suffix(S2,i)=S2[i...len].NiisthetimesthatSuffix(S2,i)occursinS1andLiisthelengthofSuffix(S2,i).ThenthesecretisthesumoftheproductofNiandLi.NowSFwantsyoutohelphimfindthesecret.Theanswermaybeverylarge,sot...

    02018年2月20日18KMP,HDU
  • [HDU1358/UVA1328/SPOJ PERIDO/POJ1961/ZOJ2177]Period(KMP)

    [HDU1358/UVA1328/SPOJ PERIDO/POJ1961/ZOJ2177]Period(KMP)

    DescriptionForeachprefixofagivenstringSwithNcharacters(eachcharacterhasanASCIIcodebetween97and126,inclusive),wewanttoknowwhethertheprefixisaperiodicstring.Thatis,foreachi(2<=i<=N)wewanttoknowthelargestK>1(ifthereisone)suchthattheprefixofSwithlengthicanbewrittenasAK,thatisAconcatenatedKtimes,forsomestringA.Ofcourse,wealsowanttoknowtheperiodK.HttpHDUUVASPOJPOJ...

    02018年2月20日19KMP,HDU,POJ,UVA,SPOJ,ZOJ
  • [HDU3031]To Be Or Not To Be(可并堆,左偏树)

    [HDU3031]To Be Or Not To Be(可并堆,左偏树)

    DescriptionThat'saquestion.NowHappy(XiYangyang)hasbeencaughtbyWolffy(HuiTailang).AsWolffyisbusypreparingthebigmeal,agoodideacomestoHappy.HeproposesagamethatonlyWolffyhadwon,hecaneatHappy.Wolffyalwaysbelievesheisthecleverestone,sotheyreachaconsensus.AndtheybothagreewithWolnie(HongTailang)whenthereferee.AtheaterwillbebeattodiebyWolnie'span.Thegameisdefinedasfollow.Therearemul...

    02018年2月18日24左偏树,HDU,可并堆
1 / 7 1 2 3 ...7 下一页 »