首页 > 代码库 > 数位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)