以前成都赛区的题目。。
http://acm.hdu.edu.cn/showproblem.php?pid=4734
题意很明显,就是有一个F(x)的函数,然后给你一个a和b求出在0~b中有多少小于等于F(a)的,
预处理出来dp[i][j][k]中有多少小于等于k的。。这里采用递推。。因为我太弱了。递归总是写错。。还需慢慢加深理解。。
PS.代码很丑。。还是推荐递归。。实在不会递推也可以。。蒟蒻加油!
#include <iostream>
#include <cstring>
using namespace std;
int dp[12][10][10000];
int p[11]={1,2,4,8,16,32,64,128,256,512,1024};
int init(){
for(int j=0;j<10;j++)
for(int k=0;k<5100;k++){
dp[1][j][k]=(k>j?j+1:k+1);
}
for(int i=2;i<=10;i++){
for(int k=0;k<5100;k++) dp[i][0][k]=dp[i-1][9][k];
for(int j=1;j<10;j++){
for(int k=0;k<5100;k++){
if(k-j*p[i-1]>=0)
dp[i][j][k]=dp[i][0][k-j*p[i-1]]+dp[i][j-1][k];
else
dp[i][j][k]=dp[i][j-1][k];
}
}
}
}
int num[20];
int cal(int x,int lim){
int cnt=1;
while(x){
num[cnt++]=x%10;
x/=10;
}
int ret=0,k=0,idx=1;
for(int i=1;i<cnt;i++)
if(num[i]==0)
++idx;
else
break;
for(int i=cnt-1;i>0;i--){
if(num[i]==0) continue;
if(lim-k>=0)
ret+=dp[i][num[i]-1][lim-k];
else
break;
if(i==idx&&p[i-1]*num[i]<=lim-k)
ret+=1;
k+=p[i-1]*num[i];
}
return ret;
}
int F(int x){
int ret=0;
int cnt=0;
while(x){
ret+=p[cnt]*(x%10);
x/=10;
cnt++;
}
return ret;
}
int main()
{
int t;
cin>>t;
init();
int cas=1;
while(t--){
int a,b;
cin>>a>>b;
int lim=F(a);
if(lim==0||b==0){
cout<<"Case #"<<cas++<<": "<<1<<endl;
continue;
}
cout<<"Case #"<<cas++<<": "<<cal(b,lim)<<endl;
}
return 0;
}