hdu 3967 Zero’s Number (不允许前导0(新写法)的数位dp)

题目链接

题意:给出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。。。

因为忘记这个结果第二个样例调了好久一直是31。。。。

 

 

 

 

 

FZU 2113 Jason的特殊爱好 (数位dp)

题目链接

题意:统计区间[a,b]里数字1出现的次数。

思路:数位dp。

收获是,dfs传递的参数可能是为了判断符合条件的答案(比如不要62中的preis6等)

但是也可能是在统计答案信息。。。pos等于0的时候返回值未必是1和0.。。

然后傻逼fzu。。。long long 必须交 I64d..因为这个wa到死。

傻逼fzu,毁我青春。

 

2016 ShenYang regional online 1007||hdu 5898 odd-even number (数位dp)

题目链接

题意:题意说得一点页不清楚。。。意思在询问在区间[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

190,192,194,196,198

200,202,204,206,208,220

211,213,215,217,219

 

思路:数位dp.dp[i][j][k]表示长度为i,奇偶性相同的连续由j个,上一个的奇偶性为k.

注意不允许前导0.

其他就是细节了,太久没写数位dp调了好久啊QAQ

 

 

hdu 5787 K-wolf Number 2016 Multi-University Training Contest 5 1007 (不允许前导0的数位dp)

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

 

 

ural 1057. Amount of Degrees (b进制数位dp)

题目链接
题意:设条件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.

于是题目可以转化成求某区间内,满足一个数的b进制中恰好有k个1,其余都是0的数的个数有多少个。

然后就是数位dp的套路了。。。

注意dp数组的大小。。。应该按照位数最多的2进制考虑。。。一开始是按照10进制考虑结果只开了dp[15][15]….简直蠢哭。

 

 

hdu 4734 F(x) (数位dp)

题目链接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函数的值具体是多少。。。只关心他们的相对大小情况。。所以还是可以合并成一个变量。。。然而我用两个变量为什么错了。。不懂==

 

错误代码(用两个变量分别记录)

 

AC代码:

bc #75 C || hdu 5642 King’s Order (数位dp)

hdu5642题目链接
题意:问长度为n的仅由26个小写字母组成的合法字符串有多少个。如果某个字符连续出现四次或以上,则这个字符串为非法。否则为合法。

思路:当时以为是组合数学的题。。。推了半天公式还是还是gg…
现在学了数位dp..果然是数位dp里很简单的一种。。。
dp[i][j][k]表示长度为i,最后一个字符对应的数字为j,最后一个字符出现了k次的方案数。

需要注意的是,这种连续几个位置相等或者不相等什么的。。。没有必要维护具体那些位置上的字符是什么。。。所以这种只统计最后一个字符,以及最后一个字符出现的次数的方法具有普遍意义。。注意理解。。。

 

hdu 3709 Balanced Number (数位dp)

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

以及。。这个值(设为sum)是递减的。。。所以任何时刻如果sum<0。。那么狗带。。算一个剪枝。。而且避免了下标为负。。。

以及,关于前导0的问题。。。有些题目不允许前导0.。。。但是并不是所有不允许前导0的都需要特别处理。。。像这道。。前导0不会导致更新答案。。。所以不用管。。。 但是要注意。。。由于0,00,000,0000都是合法的balanced数。。。然而其实他们是一个数。。多加了len-1次。。记得减去。

 

 

 

poj3252 Round Numbers (不允许前导0的二进制数位dp)

题目链接
题意:问某区间中,round number 的个数是多少。所谓round number,当且仅当一个数的二进制表示中,‘0’的个数大于等于‘1’的个数。
思路:简单数位dp..和windy数那道题类似,都是不允许前导0.。。所以在dfs中要加一维判断前面是否有非0的数。。。

hdu 4507 吉哥系列故事——恨7不成妻 (返回平方和的数位dp)

题目链接
题意:如果一个整数符合下面3个条件之一,那么我们就说这个整数和7有关——
1、整数中某一位是7;
2、整数的每一位加起来的和是7的整数倍;
3、这个整数是7的整数倍;

现在问题来了:吉哥想知道在一定区间内和7无关的数字的平方和。

思路;如果是求count的话毫无难度。。。和之前的题目没什么区别。。不多说了。

但是是求平方数。。。一开始我的做法是在dfs中加一个LL 的参数表示当前的和,然后每次到dfs的出口,之前统计count的时候返回的是1,表示找到了满足条件的一个数,那这回就返回平方和。。但是这样做是错的。。。具体为什么错没有想得很明白。。。大概会少算?

然后参考了如下博客:
hdu4507解题报告1
hdu4507解题报告2

适牛的博客之数位dp

 

正解是,之前的dp只统计了一个cnt,这回要同时统计cnt,sum,sqsum(平方和)..

 

我们先讨论如何求得满足条件的数的和。

 

我们设某次进入dfs的数是x,当前长度为pos(长度是越来越短的,因为是从高位到低位,对于没有处理到的低位,是按0算的,比如一个五位数xxxxx,第一次dfs以后也许得到4xxxx,x表示没有填的数的位置,实际上这个数就是40000),当前位置要防止的数字是i,考虑其位置,i对这个数的大小(不是和,就是最后要得到的一个数)的贡献是i*10^(pos-1),设为f. 那么当前的数就是f+x. 我们要求的就是所有f+x的和。现在我们考虑当新添加pos位的数字i对于和的贡献。

当新添加i时,相当与把之前的数整体左移了一位,相当于×10(因为之前[1,x]中的每个满足条件的数都乘了10,所以和也乘了10),然后对于新添加的i,它的贡献是i*cnt[x],含义是对于之前[1,x]所有满足条件的每个数,都进行了pos位置填i的操作,所有对于所有满足条件的和一共添加了cnt[x]个i.

如果写成用递推的式子就是  

sum[10*x+i] = 10 * sum[x] + cnt[x]*i;//感谢@clq学长

如果用dfs的话式子就是

sum[new_state] = Σ{ sum[old_state] + (number to add at the postion) * (its base) * count[old_state] }。

 

接下来我们考虑维护平方和,方法类似。

(f+x)^2=f*f+x*x+2*f*x.

f*f直接可以算,x*x..其实就是上一层dfs得到的(f’+x’)^2嘛…也就是sum2[x] (sum2表示平方和)

2*f*x也可以算,x就是上一个状态的和。

同样,我们考虑现在已经有了x,处理到pos位置,填到该位置的数字是i的时候对平方和的影响。

x*x部分在上一个状态处理过了,即为sum2[x], 2*f*x 也可以通过sum[x]得到…

注意f*f,同样,对于之前的[1,x]中每个满足的数,都相当于第pos位添加了i,每个数对平方和的贡献都是i*i,所以要*cnt[x]… 

 

以及要不断取模,为了方便写了两个函数来搞,代码看起来清楚一些。。。

哦,还有一个小坑。。取模相减以后可能为负数。。。。记得加MOD…

 

 

 

 

 

 

hdu 3652 B-number (带整除的数位dp )

题目链接
题意:给出n,问[1,n]中,满足包含“13”且这个数(不是各位的和)能被13整除的数的个数。
思路:依然是数位dp..不过有一个小tip。。

由于包含13的情况非常难考虑(包含一个“13”,两个“13”…..)

所以要从反面考虑,即不包含13的情况。

但是由于还有另一个条件。

做法是把能被13整除的数考虑成全集U,然后在U中做分划,一部分是含13的,另一部分是不含13的。

这样我们要求两个答案,一个是能被13整除的,另一个是能被13整除并且不含13的,相减即为题目所求。

 

 

hdu 4722 good numbers (带整除的数位dp)

题目链接
题意:求一个区间内所有位数字之和能被10整除的数的个数。
思路:数位dp,dfs要一个参数记录从最高位到现在的pos位置的数字之和%10的结果。
dp[i][j] 表示长度为i,和%10为j的方案数。
记得开long long ,然而我开了那么多long long 忘了dp 的long long 结果wa到死。。果然大早上不清醒吗==

bzoj 1026 windy数(数位dp入门题)

题目链接
题意:不含前导零且相邻两个数字之差至少为2的正整数被称为windy数。 windy想知道,在A和B之间,包括A和B,总共有多少个windy数?
思路:数位dp
这道题的特点是前面不允许前导0,也就是说,如果第i位前面全是0的话,这个数就变成了i位数,i就变成了最高位,而最高位没有前面的数(如果这里不考虑不允许前导0这个因素而把前面的一个数认为成是0就错了) 最高位的数可以直接取。 还有记忆化调用以及存储的时候也要注意…只有当位数相同的时候转移才有意义。 具体的方法是dfs中多了一个prehasnonzero的bool变量,就是字面意思,判断当前位置前面的位置是够存在一个非0的值。

 

 

hdu 3555 Bomb (数位dp入门题)

题目链接
题意:问从1到n的所有数中,有多少个数含有数字串“49”
思路:和上一道不要62很像,但是由于是要统计有49的,但是有49的情况实在太多了,正难则反,用减法定理反过来考虑,先统计出不含49的数的个数,这样就和不要62一样了,然后再用总数减。

hdu 2089 不要62 (数位dp模板题,附带详细解释)

题目链接
题意:问区间[n,m]中,不含数字4,也不含数字串“62”的所有数的个数。

思路:可以转化成求区间[0,x]

第一次接触数位dp,参考了这几篇博客。

不要62(数位dp)解题报告

解题报告2

解题报告3

比较重要的前提:

¨对于一个小于n的数,肯定是从高位到低位出现某一位<n的那一位。
¨如 n = 58 n为十进制数。
¨  x = 49 此时x的十位<n
¨  x = 51 此时x的个位<n
¨有了上述性质,我们就可以从高到低枚举第一次<n对应位是哪一位。
这样之前的位确定了,之后的位就不受n的限制即从00…0~99…9,可以先预处理
以及写成递归形式代码会简洁很多,所以就写了递归形式。
更详细的解释参加代码注释。