首页 > 代码库 > 数位dp专题 (HDU 4352 3652 3709 4507 CodeForces 55D POJ 3252)

数位dp专题 (HDU 4352 3652 3709 4507 CodeForces 55D POJ 3252)

数位dp核心在于状态描述,因为阶段很简单。

一般都是求有多少个数,当然也有求平方的变态题。

因为比这个数小的范围定然是从左至右开始小的,那么什么样的前缀对后面子数有相同的结果?

HDU 3652

题意:求能被13整除且含有13这样数的个数。

赤裸裸的两个条件,加上个pre标明下前缀,其实直接开状态也是一样的。整除这个条件可以用余数来表示。余数转移:(mod*10+i)%13

/* ***********************************************
Author        :bingone
Created Time  :2014-12-26 9:45:24
File Name     :HDU3652.cpp
************************************************ */

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <cmath>
#include <cstdlib>
#include <ctime>
#define inf 0x3f3f3f3f
#define maxn (10+1000)
typedef long long ll;
using namespace std;
int N,M,T;
int n;
int dp[25][10][13][13];//pos mod yes  no noand1 yes   
int dig[20];

int dfs(int pos,int pre,int fg,int md,int limit){
    if (pos<0) return fg&&(md==0);
    if (!limit&&dp[pos][pre][fg][md]!=-1) return dp[pos][pre][fg][md];
    int res=0;
    int last=limit?dig[pos]:9;
    for (int i=0;i<=last;i++){
        res+=dfs(pos-1,i,fg||(pre==1&&i==3),(md*10+i)%13,limit&&(i==last));
    }
    if (!limit) dp[pos][pre][fg][md]=res;
    return res;
}
int solve()
{
	int len=0;
	while(n){
		dig[len++]=n%10;
		n/=10;
	}
	return dfs(len-1,0,0,0,1);
}
int main()
{
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
	memset(dp,-1,sizeof(dp));
    while(~scanf("%d",&n))
	printf("%d\n",solve());
		
    return 0;
}


HDU 3709

题意:一个数以某点为“平衡点”,计算结果为0.eg: 4139 则 4*2+1*1==9*1

前面数字当以某个点为平衡点,前面数值是多少,两个条件就能确定了。

/* ***********************************************
Author        :bingone
Created Time  :2014-12-26 12:16:50
File Name     :HDU3709.cpp
************************************************ */

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <cmath>
#include <cstdlib>
#include <ctime>
#define inf 0x3f3f3f3f
#define maxn (10+1000)
typedef long long ll;
using namespace std;
ll N,M;
int T;
int digt[20];
ll dp[20][20][2000];
ll dfs(int pos,int piv,int num,int limit)
{
	if(pos<0) return num==0;
	if(!limit && ~dp[pos][piv][num])
		return dp[pos][piv][num];
	int last=limit?digt[pos]:9;
	ll ret=0;
	for(int i=0;i<=last;i++){
		int t;
		t=num+(pos-piv)*i;
		if(t<0) continue;
		ret+=dfs(pos-1,piv,t,limit&&(i==last));
	}
	if(!limit) dp[pos][piv][num]=ret;
	return ret;
}
ll solve(ll n)
{
	int len=0;
	while(n){
		digt[len++]=n%10;
		n/=10;
	}digt[len]=0;
	ll ret=0;
	for(int i=--len;i>=0;i--)
		ret+=dfs(len,i,0,1);
	return ret-len;
}
int main()
{
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
	memset(dp,-1,sizeof(dp));
	scanf("%d",&T);
	while(T--){
		scanf("%I64d%I64d",&N,&M);
		printf("%I64d\n",solve(M)-solve(N-1));
	}
    return 0;
}


HDU 4352

题意:小于给定数字公共子序列长度为K的数字有多少个。

起初想法是,前面数字的LIS是多少,结束的数字是哪个,但这样会陷入“后效性”的陷阱。同LIS那样定义为以xx为结尾的LIS为多少。

使用状态压缩,状态表明为前面数字上升子序列为哪几个,同时内含了长度。这个状压很巧妙,值得学习一下。

/* ***********************************************
Author        :bingone
Created Time  :2014-12-26 15:11:26
File Name     :HDU4352.cpp
************************************************ */

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <cmath>
#include <cstdlib>
#include <ctime>
#define inf 0x3f3f3f3f
#define maxn (10+1000)
typedef long long ll;
using namespace std;
ll N,M;
int T,K;
int digt[20];
ll dp[20][1<<10][11];
int getlis(int bit)
{
	int ret=0;
	for(int i=0;i<10;i++)
		if((1<<i) & bit) ret++;
	return ret;
}
int addlis(int bit,int num)
{
	if((1<<num) > bit) return ((1<<num) | bit);
	if((1<<num) & bit) return  bit;
	bit|=1<<num;
	for(int i=num+1;i<10;i++)
		if((1<<i) & bit) return (bit^(1<<i));
//	return 0;
}
ll dfs(int pos,int s,int limit)
{
	if(pos<0) return K==getlis(s);
	if(!limit && ~dp[pos][s][K])
		return dp[pos][s][K];
	int last=limit?digt[pos]:9;
	ll ret=0;
	for(int i=0;i<=last;i++){
		int t=addlis(s,i);
		if(s==0 && i==0) t=0;
		ret+=dfs(pos-1,t,limit&&(i==last));
	}
	if(!limit) dp[pos][s][K]=ret;
	return ret;
}
ll solve(ll n)
{
	int len=0;
	while(n){
		digt[len++]=n%10;
		n/=10;
	}
	return dfs(len-1,0,1);
}
int main()
{
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
	memset(dp,-1,sizeof(dp));
	scanf("%d",&T);
	int cas=1;
	while(T--){
		scanf("%I64d%I64d%d",&N,&M,&K);
		printf("Case #%d: %I64d\n",cas++,solve(M)-solve(N-1));
	}
    return 0;
}


CodeForces 55D

题意:求可以被其各个位整除的数的个数。

因为出现的数字顶多就是1~9 其最小公倍数是2520.既然要求可以整除,那么前面数字对2520取余,又有哪些数字 就可以判定唯一。

/* ***********************************************
Author        :bingone
Created Time  :2014-12-26 13:43:35
File Name     :CodeForces 55D
************************************************ */

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <cmath>
#include <cstdlib>
#include <ctime>
#define inf 0x3f3f3f3f
#define maxn (10+1000)
using namespace std;
typedef long long ll;
int T;
int digt[20],len;
ll N,M;
ll f[20][512][2520];
int check(int bit,int mod){
    for (int i=2;i<=9;i++){
        if (bit&(1<<(i-2))){
            if (mod%i) return 0;
        }
    }
    return 1;
}

ll dfs(int pos,int bit,int mod,int limit){
    if (pos<0) return check(bit,mod);
    if (!limit && f[pos][bit][mod]!=-1) return f[pos][bit][mod];
    int last=limit?digt[pos]:9;
    ll ret=0;
    for (int i=0;i<=last;i++){
        int nbit=bit;
        if (i>=2) nbit|=1<<(i-2);
        ret+=dfs(pos-1,nbit,(mod*10+i)%2520,limit&&(i==last));
    }
    if (!limit) f[pos][bit][mod]=ret;
    return ret;
}

ll solve(ll n)
{
	len=0;
	while(n){
		digt[len++]=n%10;
		n/=10;
	}
	return dfs(len-1,0,0,1);
}

int main()
{
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
	memset(f,-1,sizeof(f));
    scanf("%d",&T);
	while(T--){
		scanf("%I64d%I64d",&N,&M);
		printf("%I64d\n",solve(M)-solve(N-1));
	}
    return 0;
}



HDU 3507

中文题。

以前都是求有多少个,现在求平方和。

状态很简单,pos,pre,addmod,mulmod 就是满足题中条件。

那么平方和如何求?当处理到pos,pre,addmod,mulmod,此时若转移到后面的平方和已知。f=num*ten[pos-1] 

a1^2+a2^2+a3^2....+an^2那么对于pos位置则是(f+a1)^2+....(f+an)^2

现在要求的是2*f*(a1+a2+a3...+an) 于是我们发现要求数字和和有多少个数字。三个dfs搞定。

这个题还有一个坑爹之处,能MOD就MOD吧,因为这个WA了1次。

/* ***********************************************
Author        :bingone
Created Time  :2014-12-27 11:39:51
File Name     :HDU4507.cpp
************************************************ */

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <cmath>
#include <cstdlib>
#include <ctime>
#define inf 0x3f3f3f3f
#define maxn (10+1000)
#define MOD 1000000007
typedef long long ll;
using namespace std;
int T;
ll N,M;
ll ten[20];
ll dp1[20][10][7][7];/// tot
ll dp2[20][10][7][7];/// sum
ll dp3[20][10][7][7];/// square
int digt[20];
ll dfs1(int pos,int pre,int addmod,int mulmod,int limit)
{
    if(pos<=0) return (addmod!=0) && (mulmod!=0);
    if(!limit && ~dp1[pos][pre][addmod][mulmod])
	   return dp1[pos][pre][addmod][mulmod];
	int last=limit?digt[pos]:9;
	ll ret=0;
	for(int i=0;i<=last;i++){
		if(i==7) continue;
		ret=( ret+dfs1(pos-1,i,(addmod+i)%7,(mulmod*10+i)%7,limit&&(i==last)) )%MOD;
	}
	if(!limit) dp1[pos][pre][addmod][mulmod]=ret;
	return ret;
}
ll dfs2(int pos,int pre,int addmod,int mulmod,int limit)
{
    if(pos<=0)
		if( (addmod==0) || (mulmod==0)) return -1;
		else return 0;
    if(!limit && ~dp2[pos][pre][addmod][mulmod])
	   return dp2[pos][pre][addmod][mulmod];
	int last=limit?digt[pos]:9;
	ll ret=0;
	for(int i=0;i<=last;i++){
		if(i==7) continue;
		ll tmp=dfs2(pos-1,i,(addmod+i)%7,(mulmod*10+i)%7,limit&&(i==last));
		if(tmp==-1) continue;
		ll f1=dfs1(pos-1,i,(addmod+i)%7,(mulmod*10+i)%7,limit&&(i==last));///刚开始这里写了dp1[][][][]=.其实不对有limit限制
		ret=(ret+tmp)%MOD;///而且用dp1[][][][]的时候还是addmod,mulmod没有跟dfs1后面一样,dfs2也是同样道理
		tmp=(ten[pos-1]*f1)%MOD;
		tmp=(tmp*i)%MOD;
		ret=(ret+tmp)%MOD;
	}
	if(!limit) dp2[pos][pre][addmod][mulmod]=ret;
	return ret;
}
ll dfs3(int pos,int pre,int addmod,int mulmod,int limit)
{
	if(pos<=0)
		if( (addmod==0) || (mulmod==0)) return -1;
		else return 0;
	if(!limit && ~dp3[pos][pre][addmod][mulmod])
	   return dp3[pos][pre][addmod][mulmod];
	int last=limit?digt[pos]:9;
	ll ret=0;
	for(int i=0;i<=last;i++){
		if(i==7) continue;
		ll tmp=dfs3(pos-1,i,(addmod+i)%7,(mulmod*10+i)%7,limit&&(i==last));
		if(tmp==-1) continue;
		ll f1=dfs1(pos-1,i,(addmod+i)%7,(mulmod*10+i)%7,limit&&(i==last));
		ll f2=dfs2(pos-1,i,(addmod+i)%7,(mulmod*10+i)%7,limit&&(i==last));
		ll mul1=i*i;
		mul1=(mul1*ten[pos-1])%MOD;
		mul1=(mul1*ten[pos-1])%MOD;
		mul1=(mul1*f1)%MOD;
		ll mul2=2*i;
		mul2=(mul2*ten[pos-1] )%MOD;
		mul2=(mul2*f2)%MOD;
		ret=(ret+tmp)%MOD;
		ret=(ret+mul1)%MOD;
		ret=(ret+mul2)%MOD;
	}
	if(!limit) dp3[pos][pre][addmod][mulmod]=ret;
	return ret;
}
ll solve(ll n)
{
	int len=0;
	while(n){
		digt[++len]=n%10;
		n/=10;
	}
	///dfs1(len,0,0,0,1);
	///dfs2(len,0,0,0,1);
	ll ret=dfs3(len,0,0,0,1);
	if(ret==-1) return 0;
	return ret%MOD;
}
int main()
{
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
	ten[0]=1;
	for(int i=1;i<20;i++)
		ten[i]=(ten[i-1]*10)%MOD;
	memset(dp1,-1,sizeof(dp1));
	memset(dp2,-1,sizeof(dp2));
	memset(dp3,-1,sizeof(dp3));
	dp1[0][0][0][0]=9;
	scanf("%d",&T);
	while(T--){
		scanf("%I64d%I64d",&N,&M);
		solve(M);///
		printf("%I64d\n",((solve(M)-solve(N-1))%MOD+MOD)%MOD);
	}
    return 0;
}


数位dp专题 (HDU 4352 3652 3709 4507 CodeForces 55D POJ 3252)