当前位置:编程学习 > C/C++ >>

HDU 3271 SNIBB (数位统计+二分)

题目:将一个数转化成B进制后,他的val表示的是各位上的数字和。详见题目描述。。。。
首先还是预处理,dp[i][j]表示转化成B进制后,长度为i的数中,数字和为j的数字有多少个,感觉越来越像数位DP。。。
对于询问1:压根就是数位DP,从高位开始枚举,记录之前已经出现的位数和,然后枚举当前位。注意区间的开闭问题,边界处理好
对于询问2:首先通过询问1得出的数目,判断是否存在第K大,然后就是二分答案,判断[l,mid]中和为m的数有多少个。
[cpp]
#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 long 
using 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; 

作者:ACM_cxlove
补充:软件开发 , C++ ,
CopyRight © 2022 站长资源库 编程知识问答 zzzyk.com All Rights Reserved
部分文章来自网络,