首先这题可以使用 dfs 来暴力模拟，然后你就会得到这样的 $20$ 分代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
int dfs(int x)
{
	if(x<=1)return 0;
	return x+dfs(x/2)+dfs(x-x/2);
}
void solve()
{
	int n;cin>>n;
	cout<<dfs(n)<<'\n';
}
signed main()
{
	freopen("cookie.in","r",stdin);
	freopen("cookie.out","w",stdout);
	int c,t;cin>>c>>t;
	while(t--)solve();
	return 0;
}

那这份代码为什么会 TLE 呢？因为它会执行 $O(N)$ 级别的 dfs 次数。

那我们怎么优化它呢？

调试时不难发现会 dfs 非常多相同的数字。

那我们就开个 map 记录这些数字对应的值（反正又不变）。

这就叫记忆化搜索。

#include<bits/stdc++.h>
using namespace std;
#define int long long
map<int,int>mp;
int dfs(int x)
{
	if(x<=1)return 0;
	if(mp[x])return mp[x];
	int ans=x+dfs(x/2)+dfs(x-x/2);
	return mp[x]=ans;
}
void solve()
{
	int n;cin>>n;
	cout<<dfs(n)<<'\n';
}
signed main()
{
	freopen("cookie.in","r",stdin);
	freopen("cookie.out","w",stdout);
	int c,t;cin>>c>>t;
	while(t--)solve();
	return 0;
}