hdu 5587（算法之二分） Array

75 阅读 0 评论 50 点赞

我是靠谱客的博主虚幻小海豚，最近开发中收集的这篇文章主要介绍hdu 5587（算法之二分） Array，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

Array

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

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)

这道题是经典二分，需要对二分有比较深刻的理解。
简单的说就找规律吧。
令k[i]储存每次操作后的数的个数，k1[i]储存i操作后的所有数总和。
则有：


k[0]=1;
k1[0]=1;
for(int i=1;i<58;i++)
{
k[i]=k[i-1]*2+1;
k1[i]=k1[i-1]*2+(long long)1<<i);
记住此处括号必不可少，<<的优先级比+号小。并且要把1强制转化成long long
型
}

接下来就是二分的事了，
1.查找到正好不大于n的k[i]值、由上易知前k[i]位的总和由k1[i]储存。即只需要求后n-k[i]位的值的总和
2.后面的为新增序列，则每一位都加了1，若减去1，并且去掉n+k[i]+1的0，则可将n+k[i]+2——n看做是1——n-k[i]-1位得总和，则又回到步骤1.

 while(n>0)
{
int m=lower_bound(k,k+57,n)-k;
while(k[m]>n)m--;
n-=k[m];
res+=k1[m];
if(n>0)
{
res+=n;
n--;
}
}

完整代码：

#include<stdio.h>
#include<math.h>
#include<algorithm>
using namespace std;
typedef long long ll;
ll k[111],k1[111];
int main()
{
int T;
k[0]=1;
k1[0]=1;
for(int i=1;i<58;i++)
{
k[i]=k[i-1]*2+1;
k1[i]=k1[i-1]*2;
k1[i]+=(ll)1<<i;
}
while(scanf("%d",&T)!=EOF)
while(T--)
{
ll n;
scanf("%lld",&n);
ll res=0;
while(n>0)
{
int m=lower_bound(k,k+57,n)-k;
while(k[m]>n)m--;
n-=k[m];
res+=k1[m];
if(n>0)
{
res+=n;
n--;
}
}
printf("%lldn",res);
}
return 0;
}