AcWing 3483. 记忆化搜索(不太一样的递归)
原题链接
中等
作者:
Jayce
,
2021-05-29 15:59:14
,
所有人可见
,
阅读 325
利用lowbit函数直接每次拆分二进制中所有的1
C++ 代码
/**
* Created by Jayce on 2021/5/29.
* 题目:3483. 2的幂次方
* 知识点:记忆化搜索
*/
#include <bits/stdc++.h>
using namespace std;
#define for_(i, a, b) for(int i=(a);i<(b);++i)
#define rep_(i, a, b) for(int i=(a);i<=(b);++i)
#define endl '\n'
typedef long long ll;
const int maxn = 2e4 + 5, inf = 0x3f3f3f3f, mod = 1e9 + 7;
string str[maxn];
map<int, int> mp;//用于记录一个数是2的几次方
int lowbit(int x) {
return x & (-x);
}
string solve(int num) {
if(str[num].length()) return str[num];//如果计算过了直接返回结果
int tmp = lowbit(num);
if(tmp == num) str[num] = string("2(") + solve(mp[tmp]) + string(")");//2的k次方的处理
else str[num] = solve(num - tmp) + string("+") + solve(tmp);//差分成2的k次方和不是2的k次方相加处理
return str[num];
}
void init() {
str[0] = "0";
str[1] = "2(0)";
str[2] = "2";
for_(i, 0, 16) mp[1 << i] = i;
}
int main() {
init();
int n;
while (~scanf("%d", &n)) cout << solve(n) << endl;
return 0;
}