** 题目链接 ** ： [kuangbin带你飞]专题十六 KMP & 扩展KMP & Manacher 题意 给出一个只由小写英文字符a,b,c…y,z组成的字符串S,求S中最长回文串的长度.回文就是正反读都是一样的字符串,如aba, abba等 思路 用特殊字符插入到s串中每两个字符中间，实现每个回文串都是奇数，再用manacher算法进行求解。 代码#include

** 题目链接 ** ： [kuangbin带你飞]专题十五 数位DP G - B-number 题意 求1～n的范围里含有13且能被13整除的数字的个数。 思路 首先，了解这样一个式子：a％m == ((b%m)*c+d)%m;式子的正确是显然的，就不证明了。那么判断数是否可以被13整除就可以分解为一位一位进行处理。当然，我们也只需要储存取余后的值。** dfs(len, num, mod

** 题目链接 ** ： [kuangbin带你飞]专题十五 数位DP E - Round Numbers 题意 给定区间，求转化为二进制后其中0比1多或相等的数字的个数。 思路 将数字转化为二进制进行数位dp，因为一个二进制数的最高位必须为1，所以设置变量first记录前面位是否有1，若有1，则可任意放，否则，只可放1。同时，上面的判断决定了搜索时len的大小与二进制本身的长度不一定相等，

** 题目链接 ** ： [kuangbin带你飞]专题十五 数位DP D - Bomb 题意 求1～n的范围里含有49的数字的个数。 思路 记忆化搜索dfs(len, pre, flag)len表示当前位数pre＝＝0 不含49且上一位不为4pre＝＝1 不含49且上一位为4pre＝＝2 含49flag表示是否可以任意取值(判断范围)。即可。 代码#include <iostrea

** 题目链接 ** ： [kuangbin带你飞]专题十六 KMP & 扩展KMP & Manacher F - The Minimum Length 题意 有一个字符串A，假设是”abcdefg”，由A可以重复组成AAA，即”abcdefgabcdefgabcdefg”，从中截取一部分(至少包含一个以上完整A)为B。现给出字符串B，求A最短的长度。 思路 因为是重复组成的

** 题目链接 ** ： [kuangbin带你飞]专题十五 数位DP C - 不要62 题意 杭州人称那些傻乎乎粘嗒嗒的人为62（音：laoer）。杭州交通管理局经常会扩充一些的士车牌照，新近出来一个好消息，以后上牌照，不再含有不吉利的数字了，这样一来，就可以消除个别的士司机和乘客的心理障碍，更安全地服务大众。不吉利的数字为所有含有4或62的号码。例如：62315 73418 88914都属

** 题目链接 ** ： [kuangbin带你飞]专题十五 数位DP B - XHXJ’s LIS 题意 给定区间，求出有多少个数满足最长上升子序列(将数看作字符串)的长度为k。 思路 一个数的上升子序列最大长度为10，所以每一个上升子序列的状态都可以用10个二进制位来表示。上升子序列的变化可以用LIS的方式来更新。dp[len][num][k]len为当前的位，num为当前上升子序列的状

** 题目链接 ** ： [kuangbin带你飞]专题十五 数位DP A - Beautiful numbers 题意ps：第一道数位dp，题真好，虽然是参考大牛方法悟过才a，但仍收获不少。 求一个区间内的Beautiful numbers有多少个。Beautiful numbers指：一个数能整除所有组成它的非0数字。例如15可以被1和5整除，所以15是Beautiful numbers

** 题目链接 ** ： [kuangbin带你飞]专题十六 KMP & 扩展KMP & Manacher E - Period 题意 给一字符串，求其所有完整循环的前缀与循环节的长度。例：aaa长度2前缀，循环节为a，个数为2长度3前缀，循环节为a，个数为3 思路 kmp求出字符串前后缀重复数，遍历所有前缀子串进行下面操作：字符串前后缀重复数next[L]，则循环节的长度为

** 题目链接 ** ： [kuangbin带你飞]专题十六 KMP & 扩展KMP & Manacher D - Cyclic Nacklace 题意 给一字符串，求在其尾部添加最少多少个字符，可以使其内部循环两次以上。例：ababa，需后面添加b即可 ababc需后面添加ababc。 思路 kmp求出字符串前后缀重复数next[n-1]，则尾部不能循环的部分长度为L＝n－

1405 树的距离之和 基准时间限制：1 秒 空间限制：131072 KB 分值: 40 难度：4级算法题 收藏 关注 给定一棵无根树，假设它有n个节点，节点编号从1到n, 求任意两点之间的距离（最短路径）之和。 Input 第一行包含一个正整数n (n <= 100000)，表示节点个数。 后面(n - 1)行，每行两个整数表示树的边。 Output 每行一个整数，第i(i =

** 题目链接 ** ： [kuangbin带你飞]专题十二 基础DP1 R - Milking Time 题意 奶牛为自己规划下面n时间内的产奶，m个时间段，每个段有a，b，c表示从a时到b时共可产奶c。挤奶工每次挤奶必须挤完完整的时间段，且每次挤完需要休息r时，求最终可获得的牛奶最大值ps. 上面的n简直了，不仔细看题很容易误解，差点让我简单问题复杂化，所有的时间段的时间都不会超出1～n的

** 题目链接 ** ： [kuangbin带你飞]专题十二 基础DP1 Q - Phalanx 题意 给定矩阵，求符合对称矩阵的最大子矩阵的宽度。 这里的对称矩阵是以 ** 左下至右上 ** 为轴的。 思路 一个n＊n的对称矩阵，对角线上的元素上方与右方的相同元素数量，一定比其左下方少1。例如123412541上面矩阵对角线上3的相同元素数量为1(包括自身)，1为2，5为3所以可以把每个矩

** 题目链接 ** ： [kuangbin带你飞]专题十二 基础DP1 P - FatMouse and Cheese 题意 给n＊n地图，老鼠初始位置在(0,0)，它每次行走要么横着走要么竖着走，每次最多可以走出k个单位长度，且落脚点的权值必须比上一个落脚点的权值大，求最终可以获得的最大权值(题目很容易会理解错题意，道友小心) 思路 记忆化搜索，具体见代码注释 代码#include&l

** 题目链接 ** ： [kuangbin带你飞]专题十二 基础DP1 O - Treats for the Cows 题意 给长度为n的序列，每次只能从首或尾取一个数，第i次取的数权值为(数值*i)，求取完所有的数可以达到的最大权值。 思路 dp[i][j]表示左边取了i个数，右边取了j个数故dp[i][j] = max(dp[i-1][j] + a[i]* (i+j), dp[i][j

** 题目链接 ** ： [kuangbin带你飞]专题十二 基础DP1 N - Longest Ordered Subsequence 题意 求最大递增子序列的长度 思路 两种方法1. dp[i] = max(dp[j]+1) 1<=j<=i-1(n^2)2. LIS(nlogn) 代码#include<iostream> #include<cstring&

参考链接： [ 博弈之 Nim 游戏和 sg 函数 ](https://software.intel.com/zh-cn/blogs/2014/03/06/nim-sg)题目链接： poj 3537 Crosses and Crosses Nim游戏的定义Nim游戏是组合游戏(Combinatorial Games)的一种，准确来说，属于“Impartial Combinatorial Gam

** 题目链接 ** ： [kuangbin带你飞]专题十二 基础DP1 M - Help Jimmy ** 做中文题真开心，不用浪费时间在翻译上，上帝啊，让中文统治世界吧。 ** 题意 Description “Help Jimmy” 是在下图所示的场景上完成的游戏。场景中包括多个长度和高度各不相同的平台。地面是最低的平台，高度为零，长度无限。![这里写图片描述](http://7x

题目链接： [kuangbin带你飞]专题十二 基础DP1 J - FatMouse’s Speed 题意 给n个老鼠的体重和速度，求找出一个最长的序列，此序列体重递增速度递减 思路 按体重递增排序，再求最长递增(此递增表示体重递增速度递减)子序列。dp[i] = max(dp[j]+1) 0<=j<=i-1 代码#include<iostream> #includ

题目链接： [kuangbin带你飞]专题十二 基础DP1 H - Tickets 题意 给出T，表示有T组样例给出n，表示有n个人买票给出n个数表示这个人单独买票会花的时间..给出n-1个数，表示这个人和前面那个人一起买票会花的时间求最快多少分钟可以把票买完 思路 dp[i] = max(dp[i-1]+a[i], dp[i-2]+b[i]) 代码#include<iostream