首页 > 代码库 > ACdreamOJ 1154 Lowbit Sum (数位dp)
ACdreamOJ 1154 Lowbit Sum (数位dp)
ACdreamOJ 1154 Lowbit Sum (数位dp)
ACM
题目地址:ACdreamOJ 1154
题意:
long long ans = 0;
for(int i = 1; i <= n; i ++)
ans += lowbit(i)
lowbit(i)的意思是将i转化成二进制数之后,只保留最低位的1及其后面的0,截断前面的内容,然后再转成10进制数。即lowbit(i) = i&(-i)。
每输入一个n,求ans
分析:
用二进制去考虑,可以发现这是个数位dp,如果当前第i位为1,说明这个数肯定包含i+1位的全部和,不要忘了第i位也会被求和到。
额,举个例子:
10->1010,
第一位是1,所以它肯定包含000~111,也包含1000
第二位是0,不考虑
第三位是1,包含0~1,也包含10
第四位是0,不考虑
所以我们只要算出0~1, 00~11, 000~111...的和就行了
列出1~15的二进制码,发现,最后一个1在最后一位有一半,在倒数第二位的有1/4,所以根据这个规律打表就行了。
代码:
/* * Author: illuz <iilluzen[at]gmail.com> * File: 1154.cpp * Create Date: 2014-07-31 08:46:56 * Descripton: aoj 1154 */ #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; #define repf(i,a,b) for(int i=(a);i<=(b);i++) typedef long long ll; const int N = 30; ll n; ll dp[N]; // table void init() { repf (i, 1, N - 1) { ll ans = 0, t = (1<<i), v = 1; while (t) { ans += (t>>1) * v; // there was (t>>1) numbers whose last 1 is in log2(v) v <<= 1; t >>= 1; } dp[i] = ans; // cout << ans << ' '; } } ll solve(ll n) { int i = 0; ll ret = 0; while (n) { if (n & 1) ret += dp[i] + (1<<i); // don't forget there must be a 1<<i n >>= 1; i++; } return ret; } // brute force ll bf(ll n) { ll ans = 0; repf (i, 1, n) ans += i&(-i); return ans; } int main() { init(); while (cin >> n) { cout << solve(n) << endl; // cout << n << ' ' << solve(n) << ' ' << bf(n) << endl; } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。