题目 1626: 蓝桥杯算法训练VIP-幂方分解

原题链接

题面

题目

题目描述
任何一个正整数都可以用2的幂次方表示。例如：
$137=2^7+2^3+2^0$
同时约定方次用括号来表示，即ab 可表示为a（b）。
由此可知，137可表示为：
2（7）+2（3）+2（0）
进一步：$7=2^2+2+2^0$ （$2^1$用2表示）
$3=2+2^0$
所以最后137可表示为：
2（2（2）+2+2（0））+2（2+2（0））+2（0）
又如：
$1315=2^{10}+2^8+2^5+2+2^0$
所以1315最后可表示为：
2（2（2+2（0））+2）+2（2（2+2（0）））+2（2（2）+2（0））+2+2（0）
输入
输入包含一个正整数N（N<=20000），为要求分解的整数。
输出
程序输出包含一行字符串，为符合约定的n的0，2表示（在表示中不能有空格）
样例输入
1315
样例输出
2(2(2+2(0))+2)+2(2(2+2(0)))+2(2(2)+2(0))+2+2(0)

思路

可以发现，是2的次方的就是用2的几次方来表示，不正好是2的次方的就用距离他最近的那个2的次方加上这个数和最近的2的次方的差即可。

再开两个变量来记录当前这个数是不是刚好是2的次方，还有一个记录是2的几次方。

代码

#include<bits/stdc++.h>
using namespace std;
string s[20005];
int main()
{
    int n;cin >> n;s[0] = "0";s[1] = "2(0)";s[2] = "2";s[3] = "2+2(0)";s[4] = "2(2)";int flag = 4;int cnt = 2;for (int i = 5; i <= n; i ++ ){
    string x = s[flag];if (i - flag == flag){
    flag *= 2;cnt ++;s[i] = "2(" + s[cnt] + ")";}else{
    s[i] = x + "+" + s[i - flag];}}cout << s[n];return 0;
}

总结

也算一道递推题吧。