ACdream OJ 1154 Lowbit Sum

题目链接~~>

做题感悟：这题是昨天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 ;
     
    
   

    

     

    
    

     

      }
     
    
  
 

文章来源: blog.csdn.net，作者：Linux猿，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/nyist_zxp/article/details/38311595