ACdream 1154 Lowbit Sum （数位dp）

Dear 丶 2022-06-13 00:52 167阅读 0赞

题目链接：  
[ACdream 1154][]

题解：数位dp。  
这题可以加深对 lowbit 的理解啊。  
你打个表就可以发现规律了。  
当 n 为偶数时，dp\[n\]=dp\[n2\]\+n2  
当 n 为奇数时，dp\[n\]=dp\[n2\]\+n2\+1

AC代码：

/*
    * this code is made by LzyRapx
    * Problem: 1154
    * Verdict: Accepted
    * Submission Date: 2017-06-21 23:56:51
    * Time: 180MS
    * Memory: 1664KB
    */
    #include <bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    int lowbit(int x)
    {
        return x&(-x);
    }
    ll DP(int x)
    {
        if(x==1)return 1;
        return 2*DP(x>>1) + (x>>1) + (x&1); 
    }
    int main()
    {
        int n =0 ;
        /*
       for(int n=1;n<=10;n++){
           int  ans  = 0 ;
          for(int i=1;i<=n;i++){
              ans+=lowbit(i);
              cout<<lowbit(i)<<" "; 
          }
          cout<<endl;
          cout<<ans<<endl;
      }   */
        while(~scanf("%d",&n))
        {
            cout<<DP(n)<<endl;
        }
        return 0;
    }

[ACdream 1154]: http://acdream.info/problem?pid=1154

发表评论取消回复

表情：

评论列表（有 0 条评论，167人围观）

还没有评论，来说两句吧...

相关阅读

相关 1154 回文串划分（dp）

[1154 回文串划分][1154] ![ok.png][] 基准时间限制：1 秒空间限制：131072 KB 分值: 40 [1154]: http://www.51

爱被打了一巴掌/ 2024年02月18日 14:37/ 0 赞/ 60 阅读

相关数位DP 详解

序 > 天堂在左，战士向右引言数位DP在竞赛中的出现几率极低，但是如果不会数位DP，一旦考到就只能暴力骗分。以下是数位DP详解，涉及到的例题有：

叁歲伎倆/ 2023年08月17日 17:38/ 0 赞/ 169 阅读

相关数位dp小结

数位dp小结关于limit的问题在数位dp中,limit的作用主要有两个。控制枚举的界限，倘若没有界限，每一位的枚举范围都是0-9. 但如果有界限，

桃扇骨/ 2023年07月03日 07:22/ 0 赞/ 57 阅读

相关数位dp总结

数位dp的题目一般问的是某个区间内满足某种性质的数的个数，而且对于数位dp的题目一般有都有比较通用的做法，在考虑问题的时候一般以树的形式来考虑： ![watermark_ty

「爱情、让人受尽委屈。」/ 2022年09月14日 03:06/ 0 赞/ 253 阅读

相关 Bomb（数位Dp）

Bomb Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 131072/65536 K (Java/Oth

布满荆棘的人生/ 2022年08月03日 00:09/ 0 赞/ 231 阅读

相关数位DP

Problem Description 据说，QAQ 的幸运数字是含有 "47" （4 和 7 相邻）的数，例如 47, 147, 247, 470, 471, 2047

小灰灰/ 2022年06月15日 00:40/ 0 赞/ 346 阅读

相关 ACdream 1064 完美数（数位dp）

题目链接： [点击我打开题目][Link 1] 题意：在\[L,R\]的正整数区间内，要么包含3 要么包含 8 的不同的整数有多少个？题解：数位dp。设：

一时失言乱红尘/ 2022年06月14日 01:58/ 0 赞/ 227 阅读

相关 ACdream 1025 Transform (dp)

题目链接： [ACdream 1025][] 题意：让你求从a转换到b的最少步数，a可以转化到a\+x,x是a的因子。题解： dp题。转换方程很容易推

Myth丶恋晨/ 2022年06月14日 00:50/ 0 赞/ 177 阅读

相关 ACdream 1154 Lowbit Sum （数位dp）

题目链接： [ACdream 1154][] 题解：数位dp。这题可以加深对 lowbit 的理解啊。你打个表就可以发现规律了。当 n 为偶数时，dp\

Dear 丶/ 2022年06月13日 00:52/ 0 赞/ 168 阅读

相关数位DP模板

int a[20]; ll dp[20][state]; ll dfs(int pos,/state变量/,bool lead/前导零/,bool li

左手的ㄟ右手/ 2021年09月19日 05:42/ 0 赞/ 406 阅读