atcoder beginner contest 340c -爱代码爱编程
Naively, a brute force recursion solution be implemented with O ( n ) \mathcal O (n) O(n) complexity.
int work(int x)
{
if(x==1)return 0;
return x+work(x>>1)+work((x>>1)+(x&1))
}
However, since all possible x x x can be represented as n ⋅ 2 − k + [ 0 / 1 ] n\cdot 2^{-k}+[0/1] n⋅2−k+[0/1], the number of possible x x x does not exceed 2 ⋅ log 2 ( n ) 2\cdot \log_2(n) 2⋅log2(n)
Then, we can intuitively implement a memorization search with map
.
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<map>
using namespace std;
map <long long,long long> f;
long long n,ans;
long long work(long long x)
{
if(x==1)return 0;
if(f[x])return f[x];
return f[x]=x+work(x>>1)+work((x>>1)+(x&1));
}
int main()
{
cin>>n;
cout<<work(n)<<endl;
return 0;
}