程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> HDU 3271 SNIBB (數位統計+二分)

HDU 3271 SNIBB (數位統計+二分)

編輯:C++入門知識

題目:將一個數轉化成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

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved