首页 > ACM题库 > HDU-杭电 > HDU 3271-SNIBB-动态规划-[解题报告]HOJ
2014
03-13

HDU 3271-SNIBB-动态规划-[解题报告]HOJ

SNIBB

问题描述 :

  As we know, some numbers have interesting property. For example, any even number has the property that could be divided by 2. However, this is too simple.
  One day our small HH finds some more interesting property of some numbers. He names it the “Special Numbers In Base B” (SNIBB). Small HH is very good at math, so he considers the numbers in Base B. In Base B, we could express any decimal numbers. Let’s define an expression which describe a number’s “SNIBB value”.(Note that all the “SNIBB value” is in Base 10)
  
The Diophantine Equation

    Here N is a non-negative integer; B is the value of Base.
  For example, the “SNIBB value” of “1023” in Base “2” is exactly:10
(As we know (1111111111)2=(1023)(10))
  Now it is not so difficult to calculate the “SNIBB value” of the given N and B.
But small HH thinks that must be tedious if we just calculate it. So small HH give us some challenge. He would like to tell you B, the “SNIBB value” of N , and he wants you to do two kinds of operation:
1.  What is the number of numbers (whose “SNIBB value” is exactly M) in the range [A,B];
2.  What it the k-th number whose “SNIBB value” is exactly M in the range [A,B]; (note that the first one is 1-th but not 0-th)

Here M is given.

输入:

  There are no more than 30 cases.
  For each case, there is one integer Q,which indicates the mode of operation;
  If Q=1 then follows four integers X,Y,B,M, indicating the number is between X and Y, the value of base and the “SNIBB value”.
(0<=X,Y<=2000000000,2<=B<=64,0<=M<=300)
  If Q=2 then follows five integers X,Y,B,M,K, the first four integer has the same meaning as above, K indicates small HH want to know the k-th number whose “SNIBB value” is exactly M.
(1<=K<=1000000000)

输出:

  There are no more than 30 cases.
  For each case, there is one integer Q,which indicates the mode of operation;
  If Q=1 then follows four integers X,Y,B,M, indicating the number is between X and Y, the value of base and the “SNIBB value”.
(0<=X,Y<=2000000000,2<=B<=64,0<=M<=300)
  If Q=2 then follows five integers X,Y,B,M,K, the first four integer has the same meaning as above, K indicates small HH want to know the k-th number whose “SNIBB value” is exactly M.
(1<=K<=1000000000)

样例输入:

1 0 10 10 3
2 0 10 10 1 2
1 0 10 2 1

样例输出:

Case 1:
1
Case 2:
10
Case 3:
4
Hint
In case 1, the number in the range [0,10] whose “SNIBB value” is exactly 3 is 3(in Base 10); In case 2, the numbers in the range [0,10] whose “SNIBB value” is exactly 1 are 1 and 10; Of course the 2-th number is 10. In case 3, the number in the range [0,10] whose “SNIBB value” is exactly 1 is 1,10,100,1000(in Base 2);

思路:dp[i][j]:表示第i位在B进制下数字和。

用二分找第k个数!

代码如下:

 

SNIBB

#include<iostream>
 #include<stdio.h>
 #include<algorithm>
 #include<iomanip>
 #include<cmath>
 #include<cstring>
 #include<vector>
 #define ll __int64
 using namespace std;
 int dp[45][310],b,m,bit[45];
 int dfs(int pos,int mm,bool f)
 {
     if(pos==-1) return mm==m;
     if(!f&&dp[pos][mm]!=-1) return dp[pos][mm];
     int ans=0;
     int e=f?bit[pos]:(b-1);
     for(int i=0;i<=e;i++){
         ans+=dfs(pos-1,mm+i,f&&i==bit[pos]);
     }
     if(!f) dp[pos][mm]=ans;
     return ans;
 }
 int solve(int n)
 {
     if(n<=0) return n==m;
     int s=0;
     while(n){
         bit[s++]=n%b;
         n/=b;
     }
     return dfs(s-1,0,1);
 }
 int main(){
     int q,x,y,n,k,ca=0;
     while(scanf("%d%d%d%d%d",&q,&x,&y,&b,&m)!=EOF){
         memset(dp,-1,sizeof(dp));
         printf("Case %d:\n",++ca);
         if(x>y) swap(x,y);
         if(q==1) printf("%d\n",solve(y)-solve(x-1));
         else{
             scanf("%d",&k);
             int low=solve(x-1);
             int high=solve(y);
             if(high-low<k){
                 puts("Could not find the Number!");
                 continue;
             }
             int l=x,r=y,mid,ans=0;
             while(l<=r){
                 mid=(int)(((ll)l+(ll)r)>>1);
                 int t=solve(mid);
                 if(t-low>=k) r=mid-1,ans=mid;
                 else l=mid+1;
             }
             printf("%d\n",ans);
         }
     }
     return 0;
 }

View Code

 

 

 

参考:http://www.cnblogs.com/xin-hua/p/3319051.html


  1. 第二种想法,我想来好久,为啥需要一个newhead,发现是把最后一个节点一直返回到嘴上面这层函数。厉害,这道题之前没样子想过。

  2. 思路二可以用一个长度为k的队列来实现,入队后判断下队尾元素的next指针是否为空,若为空,则出队指针即为所求。

  3. 算法是程序的灵魂,算法分简单和复杂,如果不搞大数据类,程序员了解一下简单点的算法也是可以的,但是会算法的一定要会编程才行,程序员不一定要会算法,利于自己项目需要的可以简单了解。