ACdream 1154 Lowbit Sum （数位DP）

2022-05-25 23:03:23

Lowbit Sum

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

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

Sample Output

大致题意：中文的，都能看懂吧。

。

解题思路：这里利用了数论的一些小技巧，关于lowbit的规律。我发现这类题数论题上来直接暴力严重超时的。一般来说都有规律！

！

開始做的时候直接暴力打表，结果打个表都跑了十几秒，还是算了。。。

然后就潜心于找规律了。先随便输出了从1開始的几个连续数的lowbit值。还没啥感觉，后来又多输出了几组，才渐渐发现了规律——奇数的lowbit都是1。偶数的lowbit是先增后减的并且还是对称的，并且从两边向中间看的话，都是公比为2的等比数列。这样就能够计算了。假设n为偶数，偶数的能够转化为2*dp[n/2]，然后再加上奇数的n/2个1。就能够了； n为奇数时。偶数的还是转化成2*dp[n/2]，可是奇数的如今不是n/2个了,而是n/2 + 1个了。要想方便的总结一下。就能够写成dp[n] = 2*dp[n/2]
+ n/2 + (n%2)；可是近期又发现了一种新的写法，那就是位运算的写法。位运算也能够实现乘除，并且比乘除运算要快，当然也能判别一个数的奇偶，可能是由于计算机本来就仅仅能识别0和1的缘故吧，这些位运算就是直接对二进制数操作，所以更快。

于是状态转移方程就能够写成dp[n] = 2*dp[n>>1] + (n>>1) + (n&1).

AC代码：

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

long long dp(int x){

	if(x == 1)  return 1;

	return  2*dp(x>>1) + (x>>1) + (x&1);

}

int main(){

	#ifndef ONLINE_JUDGE

	freopen("in.txt","r",stdin);

	#endif

	int n;

	while(~scanf("%d",&n)){

		printf("%lld\n", dp(n));

	}

	return 0;

}

码农公寓