专题链接
链接
有关数位统计问题,无法暴力求解 则在数位上进行递推 [n,m]=[0,m]-[0,n-1] 统计小于<n的合法数字即可
对于任意一个<n的数字x 肯定从高位到低位出现某一位<n的那一位.
则可以从高位到低位枚举 第一次<n的对应位是哪一位,这样之后的位不受n的限制[x00.00]~[x9999] 把不受限制的整体用DP记录
HDU 2089 不要62 (入门)
题意:非法数字为含4或者62的数字,问[n,m]区间内有多少个合法数字,n,m<=1e9
dp[i][0/1] //当前为第i位,前一位是否为6 枚举每一位 合法转移状态即可
ps:dfs暴力枚举的同时 用DP记录相同状态的方法数
#include <bits/stdc++.h>using namespace std;typedef long long ll;const ll mod=1e9+7;const int N=2e3+20;int n,m,a[N];int dp[N][2];//dp[i][0/1] //当前为第i位,前一位是否为6 int DP(int pos,int pre,int sta,bool limit)//limit 当前位是否<n的对应位 {if(pos==-1)return 1;if(!limit && dp[pos][sta]!=-1)//后面位任意return dp[pos][sta];int up=limit? a[pos]:9;int sum=0;for(int i=0;i<=up;i++){if(pre==6&&i==2||(i==4))continue;sum+=DP(pos-1,i,i==6,limit&&(i==a[pos]));}if(!limit) //dp统计是固定位数pos位[000.00,999.99]无限制时的合法个数 dp[pos][sta]=sum;return sum;}int solve(int x){int pos=0;while(x){a[pos++]=x%10;x/=10;}return DP(pos-1,-1,0,true);}int main(){ memset(dp,-1,sizeof(dp));while(cin>>n>>m&&(n+m))printf("%dn",solve(m)-solve(n-1));return 0;}
HDU 3652 B-number (20)
题意:给出n<=1e9 合法数为包含13&&能被13整除,求[0,n]内合法数的个数
首先整除13->模13为0 所以加上状态模13的余数
dp[i][j][l][1/0] i位数 前一位为pre,除13余数为mod,是否包含13.
枚举当前位 合法转移状态即可
#include <bits/stdc++.h>using namespace std;typedef long long ll;const ll mod=1e9+7;const int N=20;int n,m,a[N];int dp[N][N][N][2]; // i位数 前一位为pre,除13余数为mod,是否包含13.int DP(int pos,int pre,int mod,int sta,bool limit)//limit 当前位是否<n的对应位 {if(pos==-1)return sta&&mod==0;//枚举完毕 返回是否合法 if(!limit&&dp[pos][pre][mod][sta]!=-1)return dp[pos][pre][mod][sta];int up=limit?a[pos]:9; int sum=0;for(int i=0;i<=up;i++)sum+=DP(pos-1,i,(mod*10+i)%13,sta||(pre==1&&i==3),limit&&(i==a[pos])); if(!limit)dp[pos][pre][mod][sta]=sum;return sum;}int solve(int x){int pos=0;while(x){a[pos++]=x%10;x/=10;}return DP(pos-1,0,0,0,true);}int main(){ memset(dp,-1,sizeof(dp));while(cin>>n)printf("%dn",solve(n));return 0;}
HDU 4734 F(X)
题意:给出A,B<=1e9,定义F(x)=a[n-1]*2^(n-1)+....a[0]*2^0 a[i]为x每位上的数字,问[0,B]内有多少数 <=F(A)
A为给出的,F(A)是变化的 最大不超过1e4 所以设状态,dp[i][y] i位数,权值不大于y的个数
当pos<0返回num>=0 其余按照枚举每位数转移状态即可
#include <bits/stdc++.h>using namespace std;typedef long long ll;const ll mod=1e9+7;const int N=20;ll A,B,C,a[N],pw2[N];int dp[N][50000];//dp[i][y] i位数,权值不大于y的个数 int DP(int pos,int num,bool limit){if(pos==-1)return num>=0;if(num<0)return 0;if(!limit&&dp[pos][num]!=-1)return dp[pos][num];int up=limit?a[pos]:9;int sum=0;for(int i=0;i<=up;i++)sum+=DP(pos-1,num-i*pw2[pos],limit&&(i==a[pos]));if(!limit)dp[pos][num]=sum;return sum;}int solve(int x){int pos=0;while(x){a[pos++]=x%10;x/=10;}return DP(pos-1,C,true);}int main(){ pw2[0]=1;for(int i=1;i<=10;i++)pw2[i]=pw2[i-1]*2;int t,cas=0;scanf("%d",&t);memset(dp,-1,sizeof(dp));while(t--){scanf("%d%d",&A,&B);C=0;for(int i=0;i<10&&A;i++)C+=pw2[i]*(A%10),A/=10;printf("Case #%d: %dn",++cas,solve(B));}return 0;}
POJ 3252 Round Number
题意:给出n,m<=2e9 问[n,m]内有多少个数,其二进制表示中1的个数不多0的个数?
设状态dp[i][x][y] i为二进制 1的个数为x,0的个数为y
注意前导0为缺位,不能加入0的个数中
#include <iostream>#include <vector>#include <cstring>#include <algorithm>#include <cstdio> using namespace std;typedef long long ll;const ll mod=1e9+7;const int N=40;ll n,m,a[N];ll dp[N][N][N];ll DP(int pos,int x,int y,int sta,bool limit){if(pos<0)return y>=x;if(!limit&&dp[pos][x][y]!=-1)return dp[pos][x][y];int up=limit?a[pos]:1;ll sum=0;for(int i=0;i<=up;i++){if(i==0)sum+=DP(pos-1,x,y+sta,sta,limit&&i==a[pos]);if(i==1)sum+=DP(pos-1,x+1,y,1,limit&&i==a[pos]);}if(!limit)dp[pos][x][y]=sum;return sum;}ll solve(ll n){int pos=0;while(n){a[pos++]=n%2;n/=2;}return DP(pos-1,0,0,0,true);}int main(){memset(dp,-1,sizeof(dp));while(cin>>n>>m)printf("%I64dn",solve(m)-solve(n-1));return 0;}
题意:给出n,m<=2e9 定义合法数为:数x存在一个轴 其左边部分数字*offset[i]==其右边部分数字*offset[i].
offset[i]为第i位数字到轴距离,问[n,m]内合法的数的个数?
设状态dp[i][j][k] i位数字,轴为第j位 左右是否相等 则平衡度为k
枚举轴为第x位时的ans 累加即可
#include <bits/stdc++.h>using namespace std;typedef long long ll;const ll mod=1e9+7;const int N=20;ll dp[N][N][2005];int a[N];ll DP(int pos,int piv,int sta,bool limit){if(pos==0)return sta==0;if(sta<0)//平衡度若为负 则之后都为递减 return 0;if(!limit&&dp[pos][piv][sta]!=-1)return dp[pos][piv][sta];int up=limit?a[pos]:9;ll sum=0;for(int i=0;i<=up;i++)sum+=DP(pos-1,piv,sta+(pos-piv)*i,limit&&i==up);if(!limit)dp[pos][piv][sta]=sum;return sum;}ll solve(ll n){int pos=0;while(n){a[++pos]=n%10;n/=10; }ll sum=0;for(int i=pos;i>=1;i--)//枚举轴 sum+=DP(pos,i,0,true);return sum-pos+1;//除去全部为0的情况 } int main(){memset(dp,-1,sizeof(dp));ll t,n,m;cin>>t;while(t--){cin>>n>>m;printf("%I64dn",solve(m)-solve(n-1));}return 0;}
FZU 2109 Mountain Number
题意:合法的数a[0]a[1]..a[len-1]定义为:a[2i+1]>=a[2i]&&a[2i+1]>=a[2i+2],问[l,r]内有多少个数为合法? l,r<=1e9;
奇数位要大于相邻的两个偶数位.i位数 因为前导0原因 第i位可能为偶或者奇数位,所以状态要加上[0/1]
数位DP设dp[i][pre][0/1] i位数,前一位为pre,当前位为偶/奇数位时的合法个数
最高位始终为偶数位,有前导0时,sta=0,前面放9方便判断
#include <iostream>#include <cstring>#include <algorithm>#include <cstdio>using namespace std;typedef long long ll;const int N=2e2+20;int n,a[N],dp[N][N][2];int DP(int pos,int pre,int sta,int lead,bool limit){if(pos<0)return 1;if(!limit&&dp[pos][pre][sta]!=-1)return dp[pos][pre][sta];int up=limit?a[pos]:9;int res=0;for(int i=0;i<=up;i++){if(lead&&i==0)res+=DP(pos-1,9,0,1,limit&&i==a[pos]);//最高位始终为偶数位,有前导0 前面放9方便判断else if(sta==0&&i<=pre)res+=DP(pos-1,i,1-sta,0,limit&&i==a[pos]);else if(sta&&i>=pre)res+=DP(pos-1,i,1-sta,0,limit&&i==a[pos]);}if(!limit)dp[pos][pre][sta]=res;return res;}int solve(int x){int pos=0;while(x){a[pos++]=x%10;x/=10;} //最高位开始为偶数位 return DP(pos-1,9,0,1,true); }int main(){memset(dp,-1,sizeof(dp));int T;cin>>T;while(T--){int l,r;cin>>l>>r;int ans=solve(r)-solve(l-1);cout<<ans<<endl;}return 0;}
P.d
题意:定义数x合法:当x能被自己所有的digit整除,i.e:15能被1和5整除为合法.l,r<=1e18,问[l,r]内有多少个数合法?
能被自己所有的digit整除 也就是被lcm(d[1]..d[i])整除
lcm(1,2..9)=2520 则设dp[pos][lcm][num] 因为x%2520和x同余任意一个lcm 所以num为当高位到pos位的数%2520 最后判断num%lcm==0是否成立即可
#include <bits/stdc++.h>using namespace std;typedef long long ll;const int N=2530;ll dp[20][50][N],n,m;int a[20];int gcd(int a,int b){return b==0?a:gcd(b,a%b);}int index[N];void init(){int cnt=0;for(int i=1;i<=2520;i++)if(2520%i==0)index[i]=cnt++;}ll dfs(int pos,int lcm,int num,bool limit){if(pos<0)return num%lcm==0;if(!limit&&dp[pos][index[lcm]][num]!=-1)return dp[pos][index[lcm]][num];ll res=0;int up=limit?a[pos]:9;for(int i=0;i<=up;i++){int now=lcm;if(i)now=lcm*i/gcd(lcm,i);res+=dfs(pos-1,now,(num*10+i)%2520,limit&&i==a[pos]);}if(!limit)dp[pos][index[lcm]][num]=res;return res;}ll solve(ll n){int pos=0;while(n){a[pos++]=n%10;n/=10;}return dfs(pos-1,1,0,true);}int main(){init(); int T;cin>>T;memset(dp,-1,sizeof(dp));while(T--){cin>>n>>m;cout<<solve(m)-solve(n-1)<<endl;}return 0;}