意甲冠军：有两个查询：

q=1。在[x,y]间隔，兑换b十进制，数字和m多少个月。

q=2。在[x,y]间隔，兑换b十进制，数字是m第一k的数目是多少（十进制），没有输出由给定的主题。

思维：

和比特的平均数dp如，第几个数的话就是二分推断。

然后就是按常理要开4维，就是dp[i][sum][b][m] i位，和为sum，b进制，最后和为m

可是开不下，所以开3维每次初始化。

注意一下：

1、每次都要初始化

2、x不一定小于y

3、是[x,y]不是(x,y]

代码：

#include"cstdlib"#include"cstdio"#include"cstring"#include"cmath"#include"stack"#include"algorithm"#include"iostream"using namespace std;__int64 dp[33][320][65],num[33];  // i位 和是sum 进制b 的关于m的答案 可是再替m开一维开不下。所以不能在外面初始化__int64 dfs(__int64 site,__int64 sum,__int64 b,int f,__int64 m){    if(site==0) return sum==m?1:0;    if(!f&&dp[site][sum][b]!=-1) return dp[site][sum][b];    __int64 len=f?

num[site]:b-1; __int64 ans=0; for(__int64 i=0; i<=len; i++) { ans+=dfs(site-1,sum+i,b,f&&i==len,m); } if(!f) dp[site][sum][b]=ans; return ans; } __int64 solve(__int64 x,__int64 b,__int64 m) { int cnt=0; if(x<0) return 0; while(x) { num[++cnt]=x%b; x/=b; } return dfs(cnt,0,b,1,m); } int main() { int cas=1; int q; while(scanf("%d",&q)!=-1) { __int64 x,y,b,m,k; memset(dp,-1,sizeof(dp)); //必须放里面 printf("Case %d:\n",cas++); if(q==1) { scanf("%I64d%I64d%I64d%I64d",&x,&y,&b,&m); if(x>y) swap(x,y); printf("%I64d\n",solve(y,b,m)-solve(x-1,b,m)); } else { scanf("%I64d%I64d%I64d%I64d%I64d",&x,&y,&b,&m,&k); x--; //注意这里是求 [x,y]区间内的！

if(x>y) swap(x,y); __int64 ans=-1,s; s=solve(x,b,m); s+=k; __int64 l=x+1,r=y; while(l<=r) { __int64 mid=(l+r)/2; if(solve(mid,b,m)>=s) { ans=mid; r=mid-1; } else l=mid+1; } if(ans!=-1) printf("%I64d\n",ans); else puts("Could not find the Number!"); } } return 0; }

版权声明：本文博客原创文章，博客，未经同意，不得转载。