程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> hdu 5587 Array 2015.11.28 bestcoder 1003

hdu 5587 Array 2015.11.28 bestcoder 1003

編輯：C++入門知識

hdu 5587 Array 2015.11.28 bestcoder 1003

題意：一開始是一個數列1，每操作一次就復制一遍這個數列放到後面，然後在他們之間放一個0，然後從這個0開始包括0後面每一個數都+1。1——112——1121223……然後這個數列經過若干次操作，問你前M個數的合是多少，M最大是10的16次方

思路：我們發現每一次操作之後，他們的和都是上一個狀態的和*2+2的n-1次方，n代表第幾個數列。於是打個表A，大小最多五六十。然後我們發現每一個數列的長度都是2的n次方-1。於是我又打了個表B記錄這些長度。最後，給你一個M，你就對它dfs，在表B裡用二分尋找小於等於它的第一個數的序號，然後對應的A數組裡存的就是這前若干項的和。把這個和加到最終解裡，對於剩下的一部分長度為 L 的序列，因為題意說後面要全+1所以我們要+L，然後還說中間間隔一個0所以再加dfs（L-1）。遞歸一遍，很快的。我估計找B的位置的時候不用2分都ok，因為表B也很小，就幾十。

Array

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 139 Accepted Submission(s): 74

Problem Description Vicky is a magician who loves math. She has great power in copying and creating.
One day she gets an array {1}。 After that, every day she copies all the numbers in the arrays she has, and puts them into the tail of the array, with a signle '0' to separat.
Vicky wants to make difference. So every number which is made today (include the 0) will be plused by one.
Vicky wonders after 100 days, what is the sum of the first M numbers.
Input There are multiple test cases.
First line contains a single integer T, means the number of test cases.(1≤T≤2∗103)
Next T line contains, each line contains one interger M. (1≤M≤1016)
Output For each test case,output the answer in a line.

Sample Input

Sample Output

1
4
7

Source BestCoder Round #64 (div.2)

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include
#include 
using namespace std;
typedef long long LL;
const int INF=0x7fffffff;
const int MAX_N=10000;
int T;
long long M;

long long A[109];
long long B[109];

long long dfs(long long x){
    long long ans=0;
    long long b=upper_bound(B+1,B+63,x)-upper_bound(B+1,B+63,1)+1;
    ans+=A[b];
    if(x-B[b]==0)return ans;
    if(x-B[b]==1)return ans+1;
    ans+=dfs(x-B[b]-1)+x-B[b];
    return ans;
}
int main(){
    A[1]=1;
    long long m=1;
    for(int i=2;i<=100;i++){
        A[i]=A[i-1]*2+2*m;
        m*=2;
    }
    B[1]=1;
    for(int i=2;i<=100;i++){
        B[i]=2*B[i-1]+1;
    }
    cin>>T;
    while(T--){
        scanf(%I64d,&M);
        long long ans=0;
        printf(%I64d
,dfs(M));
    }
    return 0;
}