思路

记忆化递归

不要用记忆化数组,可以用map

递归式:

$f(x)=x+f(⌊\dfrac{x}{2}⌋)+f(⌈\dfrac{x}{2}⌉),x\ge 2$

这里可以考虑分偶数和奇数

• 偶数只要求出一个就可以了,因为一个偶数可以分为$2$个相同的数
• 奇数就不可以只求$1$个,要分开求

代码

#include<iostream>
#include<map>
#define int long long
using namespace std;
int n,sum=0;
map<int ,int >mp;
int fun(int x)
{
    if(mp[x]!=0)//有记录时
    {
        return mp[x];//返回之前的值
    }
	if(x>=2)
	{
        if(x%2==0)//偶数
        {
            int l=fun(x/2);
            mp[x]=x+2*l;//乘两倍,记得保存
            return mp[x];
        }
        else//奇数
        {
            int f=fun(x/2),s=fun(x/2+1);//分两个部分
            mp[x]=x+f+s;//和,记得保存
            return mp[x];
        }
	}
    return 0;
}
signed main()
{
    cin>>n;//输入
    cout<<fun(n);//输出
    return 0;//完结散花
}

思路

记忆化递归

不要用记忆化数组,可以用map

递归式:

$f(x)=x+f(⌊\dfrac{x}{2}⌋)+f(⌈\dfrac{x}{2}⌉),x\ge 2$

这里可以考虑分偶数和奇数

• 偶数只要求出一个就可以了,因为一个偶数可以分为$2$个相同的数
• 奇数就不可以只求$1$个,要分开求

代码

#include<iostream>
#include<map>
#define int long long
using namespace std;
int n,sum=0;
map<int ,int >mp;
int fun(int x)
{
    if(mp[x]!=0)//有记录时
    {
        return mp[x];//返回之前的值
    }
	if(x>=2)
	{
        if(x%2==0)//偶数
        {
            int l=fun(x/2);
            mp[x]=x+2*l;//乘两倍,记得保存
            return mp[x];
        }
        else//奇数
        {
            int f=fun(x/2),s=fun(x/2+1);//分两个部分
            mp[x]=x+f+s;//和,记得保存
            return mp[x];
        }
	}
    return 0;
}
signed main()
{
    cin>>n;//输入
    cout<<fun(n);//输出
    return 0;//完结散花
}

题意

题目没有难理解的地方，照着做就行了

思路

大家不用看我的暴力代码了

记忆化递归就行了，但是得用 map，开数组会过大而 CE

代码

#include <bits/stdc++.h>
#define int long long
using namespace std;
map<int,int> a;
int dfs(int n){
	if (a[n])	return a[n];
	if (n < 2)	return 0;
	if (n == 2)	return a[2] = 2;
	bool jw = n % 2;
	return a[n] = dfs(n >> 1) + dfs(n / 2 + jw) + n;
}
signed main(int argc, char **argv){
	int n;
	cin >> n;
//	queue<int> q;
//	q.push(n);
//	while (!q.empty()){
//		int x = q.front();
//		sum += x;
//		if ((x >> 1) >= 2)	q.push(x >> 1);
//		if ((ceil(1.0 * x / 2)) >= 2)	q.push(ceil(1.0 * x / 2));
//		q.pop();
//	}
	cout << dfs(n);
	return 0;
}

$update 2024/4/16 :$ 更新了无特判的代码