题目链接~~>
做题感悟:这题是昨天ACdream的手速赛的一题,开始时直接进不去,不对是一直进不去,后来从群里读了D题的题意,打了一下表发现有规律,但是为时已晚楼管要关门了只好先放着了,今天写了一下成功AC。
解题思路:
(1) 只要自己列举一下前 15 个左右的数的二进制,就会发现: 1 每 2 个数出现一次 , 2 每 4 个数出现一次, 4 每 8 个数出现一次,只要 1<< i 的出现次数的循环为 1<<(i+1) ,这样把所有的加起来求和便可。
(2) 网上挖掘的:规律题:如果熟悉树状数组的话说不定可以直接得到答案,如果不熟悉的话可以打表看一下,可以发现前几项lowbit 大概是 1 , 2 , 1 , 4 , 1, 2, 8......... 发现奇数项都是 1 , 这是lowbit 运算导致的,然后偶数项提出来,如果除以 2 ,发现就会变成 1 , 2 , 1, 4 .......... 然后就有感觉是迭代了,最终得到公式 : ans ( x ) = 2 * ans( x / 2 ) + x/2 + (x&1) ;
代码:
#include<stdio.h>
#include<cmath>
#include<string.h>
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<stdlib.h>
#define INT long long int
using namespace std ;
const int INF = 99999999 ;
const int MY = 20 + 10 ;
const int MX = 62500 + 10 ;
INT n ;
int main()
{
while(~scanf("%lld",&n))
{
// 2 倍循环
INT sum=0,x=0,m ;
sum+=n/2+n%2 ; // 先计算 1 的个数
for(int i=1 ; ;i++)
{
m=n-(1<<i) ;
if(m<0) break ;
sum+=((m/(1<<(i+1)))+1)*(1<<i) ;
}
cout<<sum<<endl ;
}
return 0 ;
}