C++ 解法, 执行用时: 2ms, 内存消耗: 376KB, 提交时间: 2021-06-05

#include <iostream>
#include <cstdio>
#include <cstring>
#include <map>

using namespace std;

long long n;
map<long long, int> mp;

long long dp(long long n) {
    int ret;
    if (n == 1) {
        ret = 1;
        mp[n] = ret;
        return ret;
    } else if (n == 0) {
        ret = 1;
        mp[n] = ret;
        return ret;
    } else if (mp.count(n) == 1) {
        return mp[n];
    }
    
    if (n & 1) {
        ret = dp (n >> 1);
    }
    else {
        ret = dp(n >> 1) + dp((n >> 1) - 1);
    }
    mp[n] = ret;
    return ret;
}

int main() {
    cin >> n;
    
    cout << dp(n) << endl;
    
    return 0;
}

C++ 解法, 执行用时: 2ms, 内存消耗: 376KB, 提交时间: 2021-04-18

#include<iostream>
#include<map>
using namespace std;
// #define long i
map<long, long> m;

long solve(long n){  //记忆搜索法 
    if(m.count(n)) return m[n]; //如果已有直接返回
    long count = 0;
    if((n&1) != 1) count = solve(n>>1) + solve((n-2)>>1);  //n为偶数
    else count = solve(n>>1);  //n为奇数
    m[n] = count;
    return count;
}

int main(){
    m[0] = 1; m[1] = 1;  //初始值
    long n; cin>>n;
    cout<<solve(n)<<endl;
    return 0;
}

C++ 解法, 执行用时: 2ms, 内存消耗: 376KB, 提交时间: 2021-03-22

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
unordered_map<ll, ll> hmp;
ll ff(ll n){
    if(hmp.find(n) != hmp.end()) return hmp[n];
    if(n == 1) return 1;
    else if(n == 2) return 2;
    long long res = 0;
    if(n & 1){
        res = ff(n >> 1);
    }
    else{
        res = ff(n >> 1) + ff((n >> 1) - 1);
    }
    return hmp[n] = res;
}
int main(){
    // int T;
    // cin>>T;
    // cout<<T<<endl;
    // char c = getchar();//用于吸收初始数字信息和接下来读入1行之间的换行。
    // string str;
    // getline(cin, str);
    // cout<<str<<endl;
    long long N;
    cin>>N;
    cout<<ff(N)<<endl;
    return 0;
}

C++ 解法, 执行用时: 2ms, 内存消耗: 376KB, 提交时间: 2021-03-22

#include <bits/stdc++.h>
#include<iostream>
#include<map>
using namespace std;
map<long, long> m;

long solve(long n){  //记忆搜索法 
    if (m.find(n) != m.end())
    {
        return m[n];
    }
    long cnt = 0;
    if (n&1==1)
    {
        //n是奇数
        cnt = solve(n>>1);
    }
    else
    {
        cnt = solve(n>>1)+solve((n>>1)-1);
    }
    m[n] = cnt;
    return cnt;
}

int main(){
    m[0] = 1; m[1] = 1;  //初始值
    long n;
    cin>>n;
    //本题还是用递归来去做
    cout<<solve(n)<<endl;
    return 0;
}


// #include <bits/stdc++.h>
// using namespace std;

// map<long, long> mp;

// long F(long n){
//     if(mp.find(n) != mp.end())
//         return mp[n];
//     long cnt = 0;
//     if(n&1 == 1)
//         cnt = F(n/2);
//     else
//         cnt = F(n/2) + F(n/2-1);
//     mp[n] = cnt;
//     return cnt;
// }

// int main(){
//     m[0] = m[1] = 1;
//     long n;
//     scanf("%ld", &n);
//     cout<<solve(n)<<endl;
//     return 0;
// }

C++ 解法, 执行用时: 2ms, 内存消耗: 376KB, 提交时间: 2021-03-05

#include<iostream>
#include<map>
using namespace std;
map<long, long> m;
long solve(long n){  //记忆搜索法 
    if(m.count(n)) 
        return m[n]; //如果已有直接返回
    long count = 0;
    if((n&1) != 1) 
        count = solve(n>>1) + solve((n>>1)-1);  //n为偶数
    else 
        count = solve(n>>1);  //n为奇数
    m[n] = count;
    return count;
}
int main(){
    m[0] = 1; m[1] = 1;  //初始值
    long n; 
    cin>>n;
    cout<<solve(n)<<endl;
    return 0;
}