数位dp

自用笔记算法

数位dp

windy数

Problem Description
windy定义了一种windy数。不含前导零且相邻两个数字之差至少为2的正整数被称为windy数。 windy想知道，
在A和B之间，包括A和B，总共有多少个windy数？

Input

包含两个整数，A B。

Output
一个整数

Sample Input
1 10
25 50

Sample Output
9
20

参考AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <iostream>  
#include <string.h>  
#include <math.h>   
using namespace std; 
int dp[11][10],A[10];    //dp[i][j]表示长度为i 最高位为j的windy数的个数
void init()
{
	memset(dp,0,sizeof(dp));
	for(int i=0;i<=9;i++)   //dp[1][i]表示一位数字的windy数为1
		dp[1][i]=1;
	for(int i=2;i<=10;i++)
		for(int j=0;j<=9;j++)
			for(int k=0;k<=9;k++)
				if(abs(j-k)>=2)
					dp[i][j]+=dp[i-1][k];  //状态转移方程d[i][j]=∑d[i-1][k](0≤k≤9且|k-j|≥2)
}
int sum(int a)
{
	int m=0,ans=0;
	while(a)           //把大数变为数组存放
	{
		A[m++]=a%10;
		a/=10;
	}
	for(int i=1;i<m;i++)    //首先考虑位数小于m的情况
		for(int j=1;j<=9;j++)
			ans+=dp[i][j];
	for(int i=1;i<A[m-1];i++)   //其次考虑位数等于m 首位数字小于A[m-1]的情况
		ans+=dp[m][i];
	for(int i=m-1;i>=1;i--)
	{
		for(int j=0;j<A[i-1];j++)  //使用for循环一位一位搜索 使用状态转移方程的思想
		{
			if(abs(j-A[i])>=2)
				ans+=dp[i][j];
		}
		if(abs(A[i]-A[i-1])<=1)    //如果开头两位不满足windy数的要求 那么已经不满足条件 退出
			break;
	}
	return ans;
}
int main()
{
	int a,b;
	init();
	while(cin>>a>>b)
	{
		cout<<sum(b+1)-sum(a)<<endl;    //此算法b并未考虑入内 所以带入的实参为b+1
	}
	return 0;
}

递增数

参考AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include<iostream>
#include<cstring>
using namespace std;
int dp[10][10],A[10];   //dp[i][j]表示长度为i 最高位为j的递增数个数
void init()
{
	memset(dp,0,sizeof(dp));
	for(int i=0;i<=9;i++)
		dp[1][i]=1;
	for(int i=2;i<=9;i++)
		for(int j=0;j<=9;j++)
			for(int k=j;k<=9;k++)
				dp[i][j]+=dp[i-1][k];
}
int sum(int a)
{
	int ans=0,m=0;
	while(a)
	{
		A[m++]=a%10;
		a/=10;
	}
	for(int i=1;i<m;i++)
		for(int j=1;j<=9;j++)
			ans+=dp[i][j];
	for(int i=1;i<A[m-1];i++)
		ans+=dp[m][i];
	for(int i=m-1;i>=1;i++)
	{
		for(int j=A[i];j<=A[i-1];j++)
			ans+=dp[i][j];
		if(A[i]-A[i-1]>0)
			break;
	}
	return ans;
}
int main()
{
	init();
	int t;
	cin>>t;
	while(t--)
	{
		int x;
		cin>>x;
		cout<<sum(x+1)<<endl;
	}
	return 0;
}

HDU 2089 （不要62）

Problem Description

Input

Output

Sample Input

Sample Output

参考AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include<iostream>
#include<cstring>
using namespace std;
int dp[10][3],A[10];  //dp[i][j]表示长度为i的吉利数的状态
//dp[i][0]:长为i的数字区间内全为吉利数字
//dp[i][1]:长为i的数字区间内全为吉利数字 且最高位为2
//dp[i][2]:长为i的数字区间内有非吉利数字
void init()
{
	memset(dp,0,sizeof(dp));
	dp[0][0]=1;
	for(int i=1;i<=6;i++)
	{
		dp[i][0]=dp[i-1][0]*9-dp[i-1][1];    //首位可以取0~9中除了4的其余9种情况 减去首位为6 次位为2的情况
		dp[i][1]=dp[i-1][0];      //首位为2 剩下i-1位满足是吉利数即可
		dp[i][2]=dp[i-1][2]*10+dp[i-1][0]+dp[i-1][1];   //若后i-1位已经是非吉利数字 那么首位0~9均可取
	}				//再加上首位为4的情况和和首位为6 次位为的的情况
}
int sum(int a)                           //求出非吉利数 再用a-求得的ans算出吉利数
{ 
	int len=0,ans=0,temp=a;
	int flag=0;
	while(a)
	{
		A[++len]=a%10;
		a/=10;
	}
	A[len+1]=0;                           //最高位置0 用在第三个if语句需要判断A[i+1]是否为6的情况
	for(int i=len;i>=1;i--)
	{
		ans+=dp[i-1][2]*A[i];             //首先加上后i-1位已经有非吉利数字 乘以A[i]的情况
		if(flag)                          //若已经是非吉利数字 加上后i-1位全是吉利数字的情况
			ans+=dp[i-1][0]*A[i];
		if(!flag&&A[i]>4)                 //首位若大于4 则可以取到4的情况
			ans+=dp[i-1][0];
		if(!flag&&A[i+1]==6&&A[i]>2)      //首位+1若等于6次位大于2 则可以取到62的情况
			ans+=dp[i][1];
		if(!flag&&A[i]>6)                 //首位若大于6 则可以取到6 进而可能取到62的情况
			ans+=dp[i-1][1];
		if(A[i]==4||(A[i+1]==6&&A[i]==2))  //判断是否为非吉利数字
			flag=1;
	}
	return temp-ans;
}
int main()
{
	int n,m;
	init();
	while(cin>>n>>m)
	{
		if(n==0&&m==0)
			break;
		cout<<sum(m+1)-sum(n)<<endl;
		//因为sum函数中并没有考虑a是不是不幸数的情况，所以m+1只算了1~m，而n只算了1~n-1
		//这两者相减才是正确答案  
	}
	return 0;
}

HDU 3555

Problem Description

Input

Output

Sample Input

Sample Output

参考AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
//思路与上题相似
#include<iostream>
#include<cstring>
#define LL long long
using namespace std;
LL dp[25][3];
int A[25];     
//dp[i][0]表示长度为i 不含49的数字
//dp[i][1]表示长度为i 不含49的数字 且最高位为9
//dp[i][2]表示长度为i 含49的数字
void init()
{
	memset(dp,0,sizeof(dp));
	dp[0][0]=1;
	for(int i=1;i<=22;i++)
	{
		dp[i][0]=dp[i-1][0]*10-dp[i-1][1];    
		dp[i][1]=dp[i-1][0];
		dp[i][2]=dp[i-1][2]*10+dp[i-1][1];
	}
}
LL sum(LL a)
{
	int len=0,flag=0;
	LL ans=0;
	while(a)
	{
		A[++len]=a%10;
		a/=10;
	}
	A[len+1]=0;
	for(int i=len;i>=1;i--)
	{
		ans+=dp[i-1][2]*A[i];
		if(flag)
			ans+=dp[i-1][0]*A[i];
		if(!flag&&A[i]>4)
			ans+=dp[i-1][1];
		if(A[i+1]==4&&A[i]==9)
			flag=1;
	}
	return ans;
}
int main()
{
	int t;
	cin>>t;
	init();
	while(t--)
	{
		LL x;
		cin>>x;
		cout<<sum(x+1)<<endl;
	}
	return 0;
}

HDU 3709

Problem Description

Input

Output

Sample Input

Sample Output

题目要求

寻找平衡数 平衡数的概念是 寻找一个枢轴 枢轴左边的力矩（数字大小×该数距离枢轴的距离）与右边相等

参考AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include<iostream>
#include<cstring>
#define LL long long
using namespace std;
int bit[20];
LL dp[20][20][2005];   //dp[i][j][k]表示长为i 平衡点在j位置 k的力矩和
LL dfs(int po,int o,int l,int limit)
{
	if(po==-1)                               //po为-1 已经匹配结束 返回力矩和是否为0
		return l==0;
	if(l<0)                                  //l<0 说明后面已经不可能等于0 直接返回0 剪枝
		return 0;
	if(!limit&&dp[po][o][l]!=-1)             //若未到上限且该状态已经访问过 直接返回dp存储的数字
		return dp[po][o][l];
	int end=limit?bit[po]:9;                 //若到达上限 end为bit存储的该位数字 后一位只能放≤它的数字
	LL ans=0;                                //若未到上限 end取9 0~9均可取
	for(int i=0;i<=end;i++)                  //每个po遍历所有≤end的数字
	{
		int next=l;
		next+=(po-o)*i;                      //计算力矩和
		ans+=dfs(po-1,o,next,limit&&i==end); //若i==end 则该位置到达上限
	}
	if(!limit)                                //dp里存储的是所有未到上限的状态值
		dp[po][o][l]=ans;
	return ans;
}
LL sum(LL a)
{
	int len=0;
	LL ans=0;
	while(a)
	{
		bit[len++]=a%10;
		a/=10;
	}
	for(int i=0;i<len;i++)
		ans+=dfs(len-1,i,0,1);       //for循环遍历所有平衡点
	return ans-(len-1);              //减去所有00，000···与0重复的情况
} 
int main()
{
	int t;
	cin>>t;
	memset(dp,-1,sizeof(dp));         //初始化-1
	while(t--)
	{
		LL x,y;
		cin>>x>>y;
		cout<<sum(y)-sum(x-1)<<endl;   //此算法考虑的y本身的情况 所以不能用sum(y+1)-sum(x)
	}
	return 0;
}

POJ 3252

Problem Description
The cows, as you know, have no fingers or thumbs and thus are unable to play Scissors, Paper, Stone’ (also known as ‘Rock, Paper,
Scissors’, ‘Ro, Sham, Bo’, and a host of other names) in order to make arbitrary decisions such as who gets to be milked first.
They can’t even flip a coin because it’s so hard to toss using hooves.
They have thus resorted to “round number” matching. The first cow picks an integer less than two billion. The second cow does the
same. If the numbers are both “round numbers”, the first cow wins,
otherwise the second cow wins.
A positive integer N is said to be a “round number” if the binary representation of N has as many or more zeroes than it has ones.
For example, the integer 9, when written in binary form, is 1001. 1001 has two zeroes and two ones; thus, 9 is a round number.
The integer 26 is 11010 in binary; since it has two zeroes and three ones, it is not a round number.
Obviously, it takes cows a while to convert numbers to binary, so the winner takes a while to determine. Bessie wants to cheat
and thinks she can do that if she knows how many “round numbers” are in a given range.
Help her by writing a program that tells how many round numbers appear in the inclusive range given by the input
(1 ≤ Start < Finish ≤ 2,000,000,000).

Input
Line 1: Two space-separated integers, respectively Start and Finish.

Output
Line 1: A single integer that is the count of round numbers in the inclusive range Start..Finish

Sample Input
2 12

Sample Output
6

题目要求

判断一个数转换成二进制数后 若0的个数大于等于1的个数 则这个数字就为round number
求给定区间内有多少这样的数字

参考AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include<stdio.h>
#include <iostream> 
#include <cstring> 
using namespace std;
int c[33][33],bit[33];
void init()                         //初始化组合数数组
{
	c[0][0]=1,c[1][0]=1;
	c[1][1]=1;
	for(int i=2;i<33;i++)           //运用组合数性质c[i][j]=c[i-1][j-1]+c[i-1][j]
	{
		c[i][0]=1;
		for(int j=1;j<i;j++)
			c[i][j]=c[i-1][j-1]+c[i-1][j];
		c[i][i]=1;
	}
}
int sum(int a)
{
	if(a<=1)                        //1不符合条件 0非正数
		return 0;
	int len=0,ans=0;
	while(a)                        //把a转换成二进制存储
	{
		if(a&1)
			bit[len++]=1;
		else
			bit[len++]=0;
		a>>=1;
	}
	for(int i=len-1;i>=1;i--)         //运用计算出的公式算位数小于len的round数
	{                                 //i-1是因为剩下的i位数字首位必为1 剩下i-1位使用推出的公式
		if(i&1)
			ans+=((1<<(i-1))-c[i-1][(i-1)/2])/2;
		else
			ans+=(1<<(i-1))/2;
	}
	int cnt0=0,cnt1=1;
	for(int i=len-2;i>=0;i--)         //计算位数等于len的round数
	{
		if(bit[i])                    //每一位数进行判断 若为0 cnt0++ 若为1进行下一步判断
		{
			for(int j=i;j>=0&&cnt0+1+j>=cnt1+i-j;j--)        
				ans+=c[i][j];
			cnt1++;                   //cnt0表示该位之前0的个数 j表示该位之后0的个数 +1表示该位置为0
		}                             //cnt1表示该位之前1的个数 i表示该位之后的所有位数和 i-i即为1的个数
		else                          //0≥1
			cnt0++;
	}
	return ans;
}
int main()
{
	int a,b;
	init();
	while(cin>>a>>b)
	{
		cout<<sum(b+1)-sum(a)<<endl;
	}
	return 0;
}

公式推导

本题需要用到的组合数公式：


比如：
22 = 10110b
如果要求 <=22的Round Numbers，也就是找出1-22有多少个二进制的0不少于1的数的个数。
22的二进制长度是5.
首先找长度比5小的Round Numbers（长度比5小的数肯定小于22啦）
长度为4的话，第一位必须是1，后面三位的话，可以有2个0，3个0 所以就是C(3,2)+C(3,3);
长度为3的Round Numbers，同理有 C(2,2);
长度为2的Round Numbers，有 C(1,1)
长度为1的Round Numbers，有 0个

下面是找长度和22相同的Round Numbers。
首先第一位是1.
22的第二位是0，所以第二位不能为1，必须是0
第三位为0的话，（前面有了2个0，1个1），后面两位可以有1个0，2个0
C（2，1）+C（2，2）
接下来把第三位恢复为1，看第四位。假如第四位是0，（前面有2个0，2个1），后面一位必须是0 C（1，1）

所以大致求的过程就如上面所述。

HOJ 1982

Problem Description
Volodya is an odd boy and his taste is strange as well. It seems to him that a positive integer number is beautiful if and only if
it is divisible by each of its nonzero digits. We will not argue with this and just count the quantity of beautiful numbers in given
ranges.

Input
Multiple test cases.
Each line contains two natural numbers li and ri (1 ≤ li ≤ ri ≤ 9 · 10^18).

Output
One line specifies the answer.

Sample Input
1 9
12 15

Sample Output
9
2

题目要求

如果一个数能被他每一位的数字整除 那么这个数就称为美丽数
求在区间内有多少美丽数

参考AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include<iostream>
#include<cstring>
using namespace std;
#define LL long long
LL hashh[2530];
int bit[25];
LL dp[25][2530][55];    //20×2520×48
//dp[len][mod][lcm]表示长度为len mod需要进行对2520取余操作从1^18优化到2520 lcm为最小公倍数 因为2520的公约数只有48个
//所以使用hash离散操作可以大大减少内存开销
LL dfs(int len,int mod,int lcm,int limit);
int GCD(int x,int y)               //求最大公约数
{
	if(y==0)
		return x;
	else
		return GCD(y,x%y);
}
int LCM(int x,int y)               //求最小公倍数
{
	return (x*y)/GCD(x,y);
}  
void init()
{
	memset(dp,-1,sizeof(dp));
	int len=0;
	for(int i=1;i*i<2520;i++)      //对2520的公约数hash处理
	{
		if(2520%i==0)
		{
			hashh[i]=len++;
			hashh[2520/i]=len++;
		}
	}
}
LL sum(LL a)
{
	int len=0;
	while(a)
	{
		bit[++len]=a%10;
		a/=10;
	}
	return dfs(len,0,1,1);
}
LL dfs(int len,int mod,int lcm,int limit)   //数位dp模版
{                                           //mod需要×10+i后就是更新后的数字 %2520进行hash优化
	LL ans=0;
	if(len<=0)
		return (mod%lcm)==0;
	if(!limit&&dp[len][mod][hashh[lcm]]!=-1)
		return dp[len][mod][hashh[lcm]];
	int end=limit?bit[len]:9;
	for(int i=0;i<=end;i++)
		ans+=dfs(len-1,(mod*10+i)%2520,i?LCM(lcm,i):lcm,limit&&i==end);
	if(!limit)
		dp[len][mod][hashh[lcm]]=ans;
	return ans;
}
int main()
{
	LL a,b;
	init();
	while(cin>>a>>b)
	{
		cout<<sum(b)-sum(a-1)<<endl;
	}
	return 0;
}

HDU 6148

长度为N 可以递增 递减 递减后递增(不能递增后递减)
转跳链接

本文标题:数位dp

文章作者:Hippopmonkey

发布时间:2017-01-26, 22:43:18

最后更新:2017-08-19, 09:50:19

原始链接:http://xuboming8.github.io/2017/01/26/数位dp/

许可协议: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

文章目录
  1. 1. 数位dp
    1. 1.1. windy数
      1. 1.1.1. 参考AC代码
    2. 1.2. 递增数
      1. 1.2.1. 参考AC代码
    3. 1.3. HDU 2089 （不要62）
      1. 1.3.1. 参考AC代码
    4. 1.4. HDU 3555
      1. 1.4.1. 参考AC代码
    5. 1.5. HDU 3709
      1. 1.5.1. 题目要求
      2. 1.5.2. 参考AC代码
    6. 1.6. POJ 3252
      1. 1.6.1. 题目要求
      2. 1.6.2. 参考AC代码
      3. 1.6.3. 公式推导
    7. 1.7. HOJ 1982
      1. 1.7.1. 题目要求
      2. 1.7.2. 参考AC代码
    8. 1.8. HDU 6148
|