HDU 3271 SNIBB （数位统计+二分）
转载请注明出处，谢谢 http://blog.csdn.net/ACM_cxlove?viewmode=contents by---cxlove
题目：将一个数转化成B进制后，他的val表示的是各位上的数字和。详见题目描述。。。。
http://acm.hdu.edu.cn/showproblem.php?pid=3271
首先还是预处理，dp[i][j]表示转化成B进制后，长度为i的数中，数字和为j的数字有多少个，感觉越来越像数位DP。。。
对于询问1：压根就是数位DP，从高位开始枚举，记录之前已经出现的位数和，然后枚举当前位。注意区间的开闭问题，边界处理好
对于询问2：首先通过询问1得出的数目，判断是否存在第K大，然后就是二分答案，判断[l,mid]中和为m的数有多少个。
#include<iostream>#include<cstring>#include<queue>#include<cstdio>#include<cmath>#include<algorithm>#define N 30#define inf 1<<29#define MOD 2007#define LL long longusing namespace std;int dp[32][305];//转换成B进制后，长度为i的数中各位和为j的个数void Init(int b,int m){ memset(dp,0,sizeof(dp)); dp[0][0]=1; for(int i=1;i<32;i++) for(int j=0;j<=m;j++) for(int k=0;k<b&&k+j<=m;k++) dp[i][j+k]+=dp[i-1][j];}//统计[0,n]中转换成b进制，和为m的个数int clac(int n,int b,int m){ int bit[35],len=0,t=n; while(t){ bit[++len]=t%b; t/=b; } int sum=0,tot=0; for(int i=len;i;i--){ for(int j=0;j<bit[i]&&m-tot-j>=0;j++) sum+=dp[i-1][m-tot-j]; tot+=bit[i]; if(tot>m) break; } //本身的和就是m，注意别落下 if(tot==m) sum++; return sum;}int main(){ int cas=0,kind,x,y,b,m,k; while(scanf("%d%d%d%d%d",&kind,&x,&y,&b,&m)!=EOF){ Init(b,m); if(x>y) swap(x,y); printf("Case %d:\n",++cas); int cnt=clac(y,b,m)-clac(x-1,b,m); if(kind==1){ printf("%d\n",cnt); continue; } scanf("%d",&k); if(k>cnt){ puts("Could not find the Number!"); continue; } int low=x,high=y,mid; while(low<high){ //二分答案，判断在[l,mid]中和为m的个数 mid=(int)((((LL)low+(LL)high))/2); int now=clac(mid,b,m)-clac(x-1,b,m); if(now<k) low=mid+1; else high=mid; } printf("%d\n",low); } return 0;}