HDU 5587：Array Array

Array

 

 Accepts: 118

 

 Submissions: 232

 Time Limit: 2000/1000 MS (Java/Others)

 

 Memory Limit: 131072/131072 K (Java/Others)

问题描述

Vicky是个热爱数学的魔法师，拥有复制创造的能力。
一开始他拥有一个数列{1}。每过一天，他将他当天的数列复制一遍，放在数列尾，并在两个数列间用0隔开。Vicky想做些改变，于是他将当天新产生的所有数字（包括0）全加1。Vicky现在想考考你，经过100天后，这个数列的前M项和是多少？。

输入描述

输入有多组数据。
第一行包含一个整数T，表示数据组数。T. left( 1 leq T leq 2 * {10}^{3} right)(1≤T≤2∗10​3​​)
每组数据第一行包含一个整数M. left( 1leq M leq {10}^{16} right)(1≤M≤10​16​​)

输出描述

对于每组数据输出一行答案.

输入样例

3
1
3
5

输出样例

1
4
7

Hint

第一项永远为数字$1$，因此样例1输出$1$
第二天先复制一次，用0隔开，得到{1,0,1}，再把产生的数字加1，得到{1,1,2}，因此样例2输出前3项和$1+1+2=4$.
第三天先得到{1,1,2,0,1,1,2}，然后得到{1,1,2,1,2,2,3}，因此样例3输出前5项和$1+1+2+1+2=7$

一做这种题就懵，一做这种题就懵。。。。。

递归或者循环，找规律，把问题化简啊。。。。

代码：

#pragma warning(disable:4996)
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <cstring>
using namespace std;
typedef long long ll;
ll m;
ll solve(ll x)
{
ll sum = 0;
while (x > 0)
{
ll res = 1;
ll cnt = 1;
while (x > 2 * cnt + 1)//找到特定的节点
{
res = 2 * res + cnt + 1;//这个节点的值，等于原值*2(因为重复了一下)+cnt(全部加了1)+(增加了一个1)
cnt = (cnt << 1) | 1;//第几个节点
}
sum += res;
x -= cnt;
sum += x;
x--;
}
return sum;
}
int main()
{
int t;
scanf("%d", &t);
while (t--)
{
cin >> m;
cout << solve(m) << std::endl;
}
}