题目链接 题意：给出l,r,k，定义f(n,k)为将数n分成左右两个非空的部分，再求和之后能被k整除的方案数。 现在问区间[l,r]中所有f(i,k)的和。 思路：数位dp... 枚举一下分点即可。。想到这个这题就A了。。。 然后相当于做分点个数个数位dp...求和即可。 dp[i][j][k][p]表示第i位，前半部分%k的结果，后半部分%k的结果，是否有前导0. 然后关于前导0这个。。。换了一种写法。。。加了一个状态在dp数组里。。。 不然每次都要一个if。。。感觉有点丑。。。。这样写简介了一点。。。 以及。。因为每次k是不同的。。。我dp状态记录的时候又没有记录k...所以记得每次初始化成-1。。。 因为忘记这个结果第二个样例 …

题目链接 题意：统计区间[a,b]里数字1出现的次数。 思路：数位dp。 收获是，dfs传递的参数可能是为了判断符合条件的答案（比如不要62中的preis6等） 但是也可能是在统计答案信息。。。pos等于0的时候返回值未必是1和0.。。 然后傻逼fzu。。。long long 必须交 I64d..因为这个wa到死。 傻逼fzu，毁我青春。 /* *********************************************** Author :111qqz Created Time :Thu 29 Sep 2016 02:20:09 AM CST File Name :code/fzu/2113.cpp …

题目链接 题意：题意说得一点页不清楚。。。意思在询问在区间[l,r]中满足某条件的数。该条件是，该数的任何一段数字是奇数组成的数串必须有偶数长度，任何一段数字是偶数组成的数串必须由奇数长度。 对于样例1，满足条件的29个数字分别是： 2,4,6,8,11,13,15,17,19,31,33,35,37,39,51,53,55,57,59,71,73,75,77,79,91,93,95,97,99. 对于样例2，满足条件的36的数字分别是： 110,112,114,116,118, 130,132,134,136,138 150,152,154,156,158 170,172,174,176,178 …

hdu5787 题意:给出l,r,k求区间[l,r]中满足任意相邻k个数字都不相同的数的个数. 思路:数位dp,dp[i][k1][k2][k3][k4]表示长度为i,前1位是k1,前2位是k2,前3位是k3,前4位是k4的方案数. 注意不允许前导0.2A /* *********************************************** Author :111qqz Created Time :2016年08月02日 星期二 16时28分29秒 File Name :code/multi2016/#5/1007.cpp …

题目链接 题意：设条件A为一个数恰好是k个互不相同的b的整数次幂的和，问某一个区间内满足条件A的数的个数是有多少个。 Example. Let X=15, Y=20, K=2, B=2. By this example 3 numbers are the sum of exactly two integer degrees of number 2: 17 = 24+20, 18 = 24+21, 20 = 24+22. 思路：数位dp..需要理解清楚恰好有k个b的互不相同的整数次幂的和这句话。 如果恰好是b的整数幂。。可以转化成b进制。。 互不相同。。说明。。所有位置上的数字要么是0，要么是1. 于是题目可以转化成求某区间内，满足一 …

题目链接s 题意：将一个10进制数x按照2进制展开后得到的值设为f(x)...现在给出a,b（10^9）问【0，b】中满足f[x]<=f[a]的数的个数。 思路：先算出f[a]...然后我们发现f(x)最大也就10*2^10=10240.。。数组可以存下。。搞之。和上一道题类似。。我们不关心两个f函数的值具体是多少。。。只关心他们的相对大小情况。。所以还是可以合并成一个变量。。。然而我用两个变量为什么错了。。不懂== 错误代码（用两个变量分别记录） /* *********************************************** Author :111qqz Created Time :2016年03月17 …

hdu5642题目链接 题意：问长度为n的仅由26个小写字母组成的合法字符串有多少个。如果某个字符连续出现四次或以上，则这个字符串为非法。否则为合法。 思路：当时以为是组合数学的题。。。推了半天公式还是还是gg... 现在学了数位dp..果然是数位dp里很简单的一种。。。 dp[i][j][k]表示长度为i,最后一个字符对应的数字为j,最后一个字符出现了k次的方案数。 需要注意的是，这种连续几个位置相等或者不相等什么的。。。没有必要维护具体那些位置上的字符是什么。。。所以这种只统计最后一个字符，以及最后一个字符出现的次数的方法具有普遍意义。。注意理解。。。

题目链接 题意：找到某区间中平衡数的个数。所谓平衡数是指，存在某个位置，值得两边的力矩相等。举个例子。。比如14326，如果把4作为中间。。那么左边=11=1 右边=31+22+62=19。。。 思路：枚举中间的pivot。。。注意如果是个位数也是平衡数（就是认为两边的力矩都是0了。。。），所以每一个位置都可能是平衡位置。。枚举的时候从1到len... 一开始我是分别记录两边的值。。非常浪费空间。。。然而发现其实没必要。。我们只关心左边是否相等。。而不关心左右的值到底是多少。。所以可以把两边的值带符号合并成一个值（pivot左边为+，pivot右边为负）。。。如果最后为0。。说明左右相等。。。 以及。。这个值(设为sum)是递减 …

题目链接 题意：问某区间中，round number 的个数是多少。所谓round number,当且仅当一个数的二进制表示中，‘0’的个数大于等于‘1’的个数。 思路：简单数位dp..和windy数那道题类似，都是不允许前导0.。。所以在dfs中要加一维判断前面是否有非0的数。。。 /* *********************************************** Author :111qqz Created Time :2016年03月17日 星期四 16时17分07秒 File Name :code/poj/3252.cpp …

题目链接 题意：如果一个整数符合下面3个条件之一，那么我们就说这个整数和7有关—— 1、整数中某一位是7； 2、整数的每一位加起来的和是7的整数倍； 3、这个整数是7的整数倍； 现在问题来了：吉哥想知道在一定区间内和7无关的数字的平方和。 思路;如果是求count的话毫无难度。。。和之前的题目没什么区别。。不多说了。 但是是求平方数。。。一开始我的做法是在dfs中加一个LL 的参数表示当前的和，然后每次到dfs的出口，之前统计count的时候返回的是1，表示找到了满足条件的一个数，那这回就返回平方和。。但是这样做是错的。。。具体为什么错没有想得很明白。。。大概会少算？ 然后参考了如下博客： hdu4507解题报告1 hdu4507解 …