首页 > 代码库 > ACDream - Lowbit Sum

ACDream - Lowbit Sum

2024-07-13 23:20:52   227人阅读

先上题目：

C - Lowbit Sum

Time Limit: 2000/1000MS (Java/Others) Memory Limit: 128000/64000KB (Java/Others)
SubmitStatus

Problem Description

long long ans = 0;
for(int i = 1; i <= n; i ++)
    ans += lowbit(i)
lowbit(i)的意思是将i转化成二进制数之后，只保留最低位的1及其后面的0，截断前面的内容，然后再转成10进制数
比如lowbit(7),7的二进制位是111，lowbit(7) = 1
6 = 110(2),lowbit(6) = 2,同理lowbit(4) = 4,lowbit(12) = 4,lowbit(2) = 2,lowbit(8) = 8

每输入一个n，求ans

Input

多组数据，每组数据一个n(1 <= n <= 10^9)

Output

每组数据输出一行，对应的ans

Sample Input

123

Sample Output

134

　　规律题，如果熟悉树状数组的话说不定可以直接得到答案，如果不熟悉的话可以打表看一下，可以发现前几项lowbit大概是1,2,1,4,1,2,1,8，······发现奇数项都是1，这是lowbit运算导致的，然后偶数项提出来，如果都除以2，发现就会变成1,2,1,4，···然后就有感觉是迭代了，最终得到公式
　　ans(x)=2*ans(x/2)+n/2+(n&1)

上代码：

 1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #include <iostream> 5 #define lowbit(x) (x & (-x)) 6 #define MAX 100002 7 #define LL long long 8 using namespace std; 9  10  11 LL solve(int n){12     if(n==1) return 1;13     LL ans =  2*solve(n>>1) + n/2;14     if(n&1) ans++;15     return ans;16 }17  18 int main()19 {20     int n;21     while(scanf("%d",&n)!=EOF){22         printf("%lld\n",solve(n));23     }24     return 0;25 }
Lowbit Sum

 


联系
我们