Current position : 首页 >> KMP

  • 2016 CCPC Changchun Onsite

    2016 CCPC Changchun Onsite

    hdu5912.Fraction计算连分数的答案，直接模拟即可[crayon-673fbc9792f3b112332512/]hdu5914.Triangle问长度1到n的线段，至少要去掉多少，使得剩下的线段无法构成三角形\(1\leqn\leq20\)斐波那契数列，手算完打表[crayon-673fbc9792f46545902639/]hdu5916.HarmonicValueDescription定义全排列的权值为相邻两个数的gcd，求1到n的所有全排列中第K小的排列\(1\leq2k\leqn\leq10000\)容易发现，第k大的全排列的权值为n-2+k构造方式...

    02016年11月6日5,678递推与动规,模拟,贪心,KMP,构造,深度搜索,主席树,二分法

  • 《数据结构与算法》作业 —— KMP

    《数据结构与算法》作业 —— KMP

    英文好难，我好菜QAQ你们这里洋文好的人多得很哪求神犇指点

    12016年10月8日5,236KMP

  • 2014PKU计算概论入学测试

    2014PKU计算概论入学测试

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

    42016年6月30日5,042递推与动规,KMP,后缀数组,最大流

  • 2015全国互测 1

    2015全国互测 1

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

    02015年5月17日3,492KMP,深度搜索,数位动规

  • [sdoi2008] Sandy的卡片

    [sdoi2008] Sandy的卡片

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

    72015年4月10日5,420KMP,后缀数组

  • NOI2014动物园

    NOI2014动物园

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

    112015年2月8日6,354KMP

  • 「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日4,201KMP

  • 「CF494B」Obsessive String

    「CF494B」Obsessive String

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

    02014年12月14日4,264递推与动规,KMP

  • 「CF471D」MUH and Cube Walls

    「CF471D」MUH and Cube Walls

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

    02014年9月27日3,905KMP

  • 「BZOJ1009」[HNOI2008] GT考试

    「BZOJ1009」[HNOI2008] GT考试

    Description阿申准备报名参加GT考试，准考证号为N位数X1X2....Xn(0<=Xi<=9),他不希望准考证号上出现不吉利的数字。他的不吉利数学A1A2...Am(0<=Ai<=9)有M位，不出现是指X1X2...Xn中没有恰好一段等于A1A2...Am.A1和X1可以为0Input第一行输入N,M,K.接下来一行输入M位的数。100%数据N<=10^9,M<=20,K<=100040%数据N<=100010%数据N<=6Output阿申想知道不出现不吉利数字的号...

    62014年5月9日15,346递推与动规,KMP,矩阵乘法

  • 「CODEVS1204」寻找子串位置(KMP)

    「CODEVS1204」寻找子串位置(KMP)

    题目描述 Description给出字符串a和字符串b，保证b是a的一个子串，请你输出b在a中第一次出现的位置。输入描述 InputDescription仅一行包含两个字符串a和b输出描述 OutputDescription仅一行一个整数样例输入 SampleInputabcdbc样例输出 SampleOutput2数据范围及提示 DataSize&Hint字符串的长度均不超过100Pascal用户请注意：两个字符串之间可能包含多个空格代码暴力不好玩，我们写个KMP吧KMP参看KMP...

    32014年1月1日5,587KMP