https://wenku.baidu.com/view/d2414ffe04a1b0717fd5dda8.html
Jason的特殊爱好
题意：统计a到b之间有多少个数位1.
数位入门~
1 #include <iostream> 2 #include <cstdio> 3 using namespace std; 4 #define ll long long 5 ll base[20]; 6 int dig[25]; 7 void init(){ 8 base[0]=1; 9 for(int i=1;i<19;i++) 10 base[i]=base[i-1]*10; 11 } 12 ll f(ll x){ 13 ll res=0,m=x; 14 int pos=0; 15 while(x){ 16 dig[++pos]=x%10; 17 x/=10; 18 } 19 for(int i=1;i<=pos;i++){ 20 ll r=m%base[i-1]; 21 ll l=m/base[i]; 22 if(dig[i]>1){ 23 res+=(l+1)*base[i-1]; 24 }else if(dig[i]==1){ 25 res+=l*base[i-1]+r+1; 26 }else{ 27 res+=l*base[i-1]; 28 } 29 } 30 return res; 31 } 32 int main(){ 33 ll a,b; 34 init(); 35 while(scanf("%I64d%I64d",&a,&b)!=EOF){ 36 printf("%I64d ",f(b)-f(a-1)); 37 } 38 }
Bomb
不要62
题意：求a到b中不含数位4和62的数字个数。
1 #include <bits/stdc++.h> 2 using namespace std; 3 #define ll long long 4 int dig[20]; 5 int dp[20][2]; 6 7 int dfs(int pos,int pre,int sta,int lim){ 8 if(pos==-1) return 1; 9 if(!lim&&dp[pos][sta]!=-1) return dp[pos][sta]; 10 int up=lim?dig[pos]:9; 11 int temp=0; 12 for(int i=0;i<=up;i++){ 13 if(pre==6&&i==2) continue; 14 if(i==4) continue; 15 temp+=dfs(pos-1,i,i==6,lim&&i==dig[pos]); 16 } 17 if(!lim) dp[pos][sta]=temp; 18 return temp; 19 } 20 int solve(int x){ 21 int pos=0; 22 while(x){ 23 dig[pos++]=x%10; 24 x/=10; 25 } 26 return dfs(pos-1,-1,0,true); 27 } 28 29 int main(){ 30 int a,b; 31 memset(dp,-1,sizeof(dp)); 32 while(scanf("%d%d",&a,&b)&&(a||b)){ 33 printf("%d ",solve(b)-solve(a-1)); 34 } 35 }
F(x)
题意：定义了f(x)函数，让求在区间[0,b]中的f值小于等于f(a)的有多少个数。
1 #include <bits/stdc++.h> 2 using namespace std; 3 int f; 4 int dig[20]; 5 int dp[20][5010]; //dp[pos][sum]还需枚举pos位，并且剩下的pos位和为sum 6 int cal(int x){ 7 if(x==0) return 0; 8 int ans=cal(x/10); 9 return ans*2+(x%10); 10 } 11 int dfs(int pos,int sum,int lim){ 12 if(pos==-1) return sum<=f; 13 if(sum>f) return 0; 14 if(!lim&&dp[pos][f-sum]!=-1) return dp[pos][f-sum]; 15 int up=lim?dig[pos]:9; 16 int ans=0; 17 for(int i=0;i<=up;i++){ 18 ans+=dfs(pos-1,sum+i*(1<<pos),lim&&i==dig[pos]); 19 } 20 if(!lim) dp[pos][f-sum]=ans; 21 return ans; 22 } 23 int solve(int x){ 24 int pos=0; 25 while(x){ 26 dig[pos++]=x%10; 27 x/=10; 28 } 29 return dfs(pos-1,0,1); 30 } 31 int main(){ 32 int t; 33 int kase=0; 34 scanf("%d",&t); 35 memset(dp,-1,sizeof(dp)); 36 while(t--){ 37 int a,b; 38 scanf("%d%d",&a,&b); 39 f=cal(a); 40 printf("Case #%d: %d ",++kase,solve(b)); 41 } 42 return 0; 43 }
Round Numbers
题意：求区间[a,b]之间有多少个数的二进制形式中0的个数大于1的个数。
好像还可以用组合数搞
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 using namespace std; 5 int a,b; 6 int dp[35][65]; 7 int bit[35]; 8 int dfs(int pos,int sta,int lead,int lim){ 9 if(pos==-1) return sta>=32; 10 if(!lim&&!lead&&dp[pos][sta]!=-1) return dp[pos][sta]; 11 int up=lim?bit[pos]:1; 12 int ans=0; 13 for(int i=0;i<=up;i++){ 14 if(lead&&i==0) ans+=dfs(pos-1,sta,lead,lim&&i==bit[pos]); 15 else ans+=dfs(pos-1,sta+(i==0?1:-1),lead&&i==0,lim&&i==bit[pos]); 16 } 17 if(!lim&&!lead) dp[pos][sta]=ans; 18 return ans; 19 } 20 int solve(int x){ 21 int pos=0; 22 while(x){ 23 bit[pos++]=x&1; 24 x>>=1; 25 } 26 return dfs(pos-1,32,1,1); 27 } 28 29 int main(){ 30 memset(dp,-1,sizeof(dp)); 31 while(scanf("%d%d",&a,&b)!=EOF){ 32 printf("%d ",solve(b)-solve(a-1)); 33 } 34 return 0; 35 }
吉哥系列故事——恨7不成妻
题意：求区间[a,b]中与7无关的数字的平方和。与7无关：数位中不含7，这个数不是7的倍数，各数位和不是7的倍数。
难点在求平方和。
例如求256和289的平方和 ，可以写成(200+56)2+(200+89)2 = 2002×2+2×200×(56+89)+(562+892)，
即 base[pos]*i*base[pos]*i*temp.cnt+2*i*base[pos]*temp.sum+temp.qsum。当前位置为pos，当前位置放i这个数，temp是后面的位置的结果。
1 #include <bits/stdc++.h> 2 using namespace std; 3 #define ll long long 4 const int mod=1e9+7; 5 6 struct Node{ 7 ll cnt; //数字个数 8 ll sum; // 各数字之和 9 ll qsum; // 各数字的平方和 10 Node (ll cnt=0,ll sum=0,ll qsum=0):cnt(cnt),sum(sum),qsum(qsum){} 11 }dp[20][7][7]; 12 int bit[20]; 13 ll base[20]; 14 15 ll a,b; 16 17 Node dfs(int pos,int pa,int pb,int lim){ //当前位置，数位之和除以7的余数，数字除以7的余数，上一位是否达到上限 18 if(pos==-1) return Node(pa&&pb,0,0); 19 if(!lim&&dp[pos][pa][pb].cnt!=-1) return dp[pos][pa][pb]; 20 int up=lim?bit[pos]:9; 21 Node ans(0,0,0); 22 for(int i=0;i<=up;i++){ 23 if(i!=7){ 24 Node temp=dfs(pos-1,(pa+i)%7,(pb*10+i)%7,lim&&i==bit[pos]); 25 ans.cnt=(ans.cnt+temp.cnt)%mod; 26 ans.sum=(ans.sum+(((base[pos]*i)%mod*temp.cnt)%mod+temp.sum)%mod)%mod; 27 //平方和展开成三项 28 ans.qsum=(ans.qsum 29 +base[pos]*i%mod*base[pos]*i%mod*temp.cnt%mod 30 +2*i*base[pos]%mod*temp.sum%mod 31 +temp.qsum)%mod; 32 } 33 } 34 if(!lim) dp[pos][pa][pb]=ans; 35 return ans; 36 } 37 38 ll solve(ll x){ 39 int pos=0; 40 while(x){ 41 bit[pos++]=x%10; 42 x/=10; 43 } 44 Node ans=dfs(pos-1,0,0,1); 45 return ans.qsum; 46 } 47 int main(){ 48 int t; 49 base[0]=1; 50 for(int i=1;i<20;i++) base[i]=base[i-1]*10%mod; 51 memset(dp,-1,sizeof(dp)); 52 scanf("%d",&t); 53 while(t--){ 54 scanf("%lld%lld",&a,&b); 55 printf("%lld ",((solve(b)-solve(a-1))%mod+mod)%mod); 56 } 57 return 0; 58 }
K-th Nya Number
HDU - 3943题意：找到区间[p+1,q]之间的第k个Nya数。Nya数是指数位含有x个4和y个7的数。
二分法~，，因为Nya数的个数满足单调性，即在[0,d]中，d越大，Nya数越多。
dp记录的状态是剩余那些数位需要满足的条件，，这样才可以记忆化~
1 #include <bits/stdc++.h> 2 using namespace std; 3 #define ll long long 4 const int maxn=25; 5 6 int bit[maxn]; 7 ll dp[maxn][maxn][maxn]; 8 ll p,q,x,y; 9 ll k; 10 11 ll dfs(int pos,int fa,int fb,int lim){ 12 if(pos==-1) return fa==0&&fb==0; 13 if(fa<0||fb<0) return 0; 14 if(!lim&&dp[pos][fa][fb]!=-1) return dp[pos][fa][fb]; 15 int up=lim?bit[pos]:9; 16 ll ans=0; 17 for(int i=0;i<=up;i++){ 18 ans+=dfs(pos-1,fa-(i==4),fb-(i==7),lim&&i==bit[pos]); 19 } 20 if(!lim) dp[pos][fa][fb]=ans; 21 return ans; 22 } 23 ll solve(ll c){ 24 int pos=0; 25 while(c){ 26 bit[pos++]=c%10; 27 c/=10; 28 } 29 return dfs(pos-1,x,y,1); 30 } 31 32 void get_k(){ 33 ll c1=solve(p); 34 ll c2=solve(q); 35 if(k>c2-c1){ 36 puts("Nya!"); 37 return ; 38 } 39 k+=c1; 40 ll l=p+1,r=q; 41 while(l<=r){ 42 ll m=(l+r)>>1; 43 if(solve(m)>=k) r=m-1; // 44 else l=m+1; 45 } 46 printf("%lld ",l); 47 } 48 int main(){ 49 int t,kase=0; 50 memset(dp,-1,sizeof(dp)); 51 scanf("%d",&t); 52 while(t--){ 53 printf("Case #%d: ",++kase); 54 scanf("%lld%lld%lld%lld",&p,&q,&x,&y); 55 int m; 56 scanf("%d",&m); 57 while(m--){ 58 scanf("%lld",&k); 59 get_k(); 60 } 61 } 62 return 0; 63 }
SNIBB
题意：操作1求区间[x,y]之间的数写成b进制形式后数位和等于m的有几个数。操作2求第k个 在区间[x,y]之间的数写成b进制形式后数位和等于m的数。
数位DP是做的多了就感觉都差不多了~
这个题有几点注意的地方，一是题目并没有说x一定小于y，要判断一下。二是二分答案的时候x+y可能会溢出导致超时要用long long 。
1 #include <bits/stdc++.h> 2 using namespace std; 3 #define ll long long 4 const int maxn=35; 5 6 int dp[maxn][320]; 7 int bit[maxn]; 8 int x,y,b,m,k; 9 10 int dfs(int pos,int sum,int lim){ 11 if(pos==-1) return sum==0; 12 if(sum<0) return 0; 13 if(!lim&&dp[pos][sum]!=-1) return dp[pos][sum]; 14 int up=lim?bit[pos]:b-1; 15 int ans=0; 16 for(int i=0;i<=up;i++){ 17 ans+=dfs(pos-1,sum-i,lim&i==bit[pos]); 18 } 19 if(!lim) dp[pos][sum]=ans; 20 return ans; 21 } 22 23 int solve(int c){ 24 int pos=0; 25 while(c){ 26 bit[pos++]=c%b; 27 c/=b; 28 } 29 return dfs(pos-1,m,1); 30 } 31 32 int main(){ 33 int c; 34 int kase=0; 35 while(scanf("%d",&c)!=EOF){ 36 memset(dp,-1,sizeof(dp)); 37 printf("Case %d: ",++kase); 38 if(c==1){ 39 scanf("%d%d%d%d",&x,&y,&b,&m); 40 if(x>y) swap(x,y); 41 printf("%d ",solve(y)-solve(x-1)); 42 }else{ 43 scanf("%d%d%d%d%d",&x,&y,&b,&m,&k); 44 if(x>y) swap(x,y); 45 int c1=solve(x-1); 46 int c2=solve(y); 47 if(k>c2-c1){ 48 puts("Could not find the Number!"); 49 continue; 50 } 51 k+=c1; 52 while(x<=y){ 53 int m=((long long)x+y)>>1; 54 if(solve(m)>=k) y=m-1; 55 else x=m+1; 56 } 57 printf("%d ",x); 58 } 59 } 60 return 0; 61 }
Zero's Number
题意：在区间[a,b]内，将x分成两半，两半之和是k的倍数。问共有多少种分法。
也可以多开一维数组记录一下k，然后把memset放到外面，稍快一点。
1 #include <bits/stdc++.h> 2 using namespace std; 3 #define ll long long 4 5 ll dp[22][22][22][2]; //当前位置、分位点、余数、是否有前导零 6 ll base[22]; 7 int bit[22]; 8 ll a,b; 9 int k; 10 ll dfs(int pos,int id,int mod,int lead,int lim){ 11 if(pos==-1) return mod?0:1; 12 if(!lim&&dp[pos][id][mod][lead]!=-1) return dp[pos][id][mod][lead]; 13 int up=lim?bit[pos]:9; 14 ll ans=0; 15 for(int i=0;i<=up;i++){ 16 if(pos>=id){ 17 if((lead==0&&pos==id&&i==0)) continue; 18 ans+=dfs(pos-1,id,(i*base[pos-id]+mod)%k,lead||i,lim&&i==bit[pos]); 19 }else { 20 ans+=dfs(pos-1,id,(i*base[pos]+mod)%k,lead||i,lim&&i==bit[pos]); 21 } 22 } 23 if(!lim) dp[pos][id][mod][lead]=ans; 24 return ans; 25 } 26 ll solve(ll x){ 27 int pos=0; 28 if(x<10) return 0; 29 while(x){ 30 bit[pos++]=x%10; 31 x/=10; 32 } 33 ll ans=0; 34 for(int i=1;i<pos;i++) 35 ans+=dfs(pos-1,i,0,0,1); 36 return ans; 37 } 38 int main(){ 39 base[0]=1; 40 for(int i=1;i<19;i++) base[i]=base[i-1]*10; 41 while(scanf("%lld%lld%d",&a,&b,&k)!=EOF){ 42 memset(dp,-1,sizeof(dp)); 43 printf("%lld ",solve(b)-solve(a-1)); 44 } 45 }
Bi-peak Number
题意：问区间[a,b]内的双峰的数的最大数位之和。如121121就是双峰的数。
看来我还是只会做水题~复杂一点就不会了。。。
1 #include <bits/stdc++.h> 2 using namespace std; 3 const int inf=0x3f3f3f3f; 4 #define ull unsigned long long 5 ull a,b; 6 int dp[22][10][7]; 7 int bit1[22],bit2[22]; 8 9 int dfs(int pos,int pre,int sta,int lim1,int lim2){ 10 if(pos==-1) return sta==6?0:-inf; 11 if(!lim1&&!lim2&&dp[pos][pre][sta]!=-1) return dp[pos][pre][sta]; 12 int down=lim1?bit1[pos]:0; 13 int up=lim2?bit2[pos]:9; 14 int ans=-inf; 15 for(int i=down;i<=up;i++){ 16 int temp=0; 17 if(sta==0&&i){ 18 temp=1; 19 }else if(sta==1){ 20 if(i>pre) temp=2; 21 else temp=-1; 22 }else if(sta==2){ 23 if(i>pre) temp=2; 24 else if(i<pre) temp=3; 25 else temp=-1; 26 }else if(sta==3){ 27 if(i>pre) temp=4; 28 else if(i<pre) temp=3; 29 else { 30 if(i) temp=4; 31 else temp=-1; 32 } 33 }else if(sta==4){ 34 if(i>pre) temp=5; 35 else temp=-1; 36 }else if(sta==5){ 37 if(i<pre) temp=6; 38 else if(i>pre) temp=5; 39 else temp=-1; 40 }else if(sta==6){ 41 if(i<pre) temp=6; 42 else temp=-1; 43 } 44 if(temp!=-1){ 45 int res=dfs(pos-1,i,temp,lim1&&i==bit1[pos],lim2&&bit2[pos]==i); 46 ans=max(ans,res+i); 47 } 48 } 49 if(!lim1&&!lim2) dp[pos][pre][sta]=ans; 50 return ans; 51 } 52 int solve(ull a,ull b){ 53 int pos=0; 54 while(b){ 55 bit1[pos]=a%10; 56 bit2[pos++]=b%10; 57 a/=10;b/=10; 58 } 59 return dfs(pos-1,0,0,1,1); 60 } 61 int main(){ 62 int t; 63 int kase=0; 64 scanf("%d",&t); 65 memset(dp,-1,sizeof(dp)); 66 while(t--){ 67 scanf("%llu%llu",&a,&b); 68 printf("Case %d: %d ",++kase,max(0,solve(a,b))); 69 } 70 }
Investigating Div-Sum Property
题意：区间[a,b]中数位和和数字是k的倍数的数字有多少个。
1 #include <bits/stdc++.h> 2 using namespace std; 3 #define ll long long 4 const int maxn=10000; 5 int dp[20][100][100]; 6 int bit[10]; 7 int base[10]; 8 int a,b; 9 int k; 10 int dfs(int pos,int pa,int pb,int lim){ 11 if(pos==-1) return pa==0&&pb==0; 12 if(!lim&&dp[pos][pa][pb]!=-1) return dp[pos][pa][pb]; 13 ll ans=0; 14 int up=lim?bit[pos]:9; 15 for(int i=0;i<=up;i++){ 16 ans+=dfs(pos-1,(pa+i)%k,(pb+i*base[pos])%k,lim&&i==bit[pos]); 17 } 18 if(!lim) dp[pos][pa][pb]=ans; 19 return ans; 20 } 21 int solve(int x){ 22 int pos=0; 23 while(x){ 24 bit[pos++]=x%10; 25 x/=10; 26 } 27 return dfs(pos-1,0,0,1); 28 } 29 int main(){ 30 int t; 31 scanf("%d",&t); 32 base[0]=1; 33 for(int i=1;i<=10;i++) base[i]=base[i-1]*10; 34 while(t--){ 35 memset(dp,-1,sizeof(dp)); 36 scanf("%d%d%d",&a,&b,&k); 37 if(k>=100) puts("0"); 38 else printf("%d ",solve(b)-solve(a-1)); 39 } 40 return 0; 41 }