基本算法5-1
话说dp是不是都算递推啊，那就写这一道递推好了 计划写不完了啊啊啊啊啊
然后我就死了
手玩1-10之后发现
发现答案为$n+{2^x1}+{2^x2}+......$
化简再手玩一下得$n+2^k$ $k$为$n$的二进制中$1$的个数
$O(1)$
code
1 #include <bits/stdc++.h> 2 using namespace std; 3 namespace gengyf{ 4 #define ll long long 5 const int maxn=1e5+10; 6 inline int read(){ 7 int f=1,x=0;char s=getchar(); 8 while(s<‘0‘||s>‘9‘){if(s==‘-‘)f=-1;s=getchar();} 9 while(s>=‘0‘&&s<=‘9‘){x=x*10+s-‘0‘;s=getchar();} 10 return f*x; 11 } 12 int n,ans,k; 13 int qpow(int a,int b){ 14 int tmp=1; 15 while(b){ 16 if(b&1){ 17 tmp=tmp*a; 18 } 19 a=a*a;b>>=1; 20 } 21 return tmp; 22 } 23 int main(){ 24 n=read();ans+=n; 25 while(n){ 26 n&=(n-1);k++; 27 } 28 ans+=qpow(2,k)-1; 29 //n的二进制表示中的1的个数。eg:111 => 4+2+1 30 cout<<ans<<endl; 31 return 0; 32 } 33 } 34 signed main(){ 35 gengyf::main(); 36 return 0; 37 }
原文：https://www.cnblogs.com/gengyf/p/11698251.html
