P1010. 幂次方

考点

  • 模拟
  • 分治

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <bits/stdc++.h>

using namespace std;

void f(int x)
{
for (int i = 30; i >= 0; --i)
{
if (x & (1 << i))
{
if (i == 0)
cout << "2(0)";
else if (i == 1)
cout << "2";
else
cout << "2(", f(i), cout << ")";
x ^= 1 << i;
if (x)
cout << "+";
}
}
}

int main()
{
int n;
cin >> n;
f(n);
return 0;
}

思路

简单的分治题,最终的子问题实际上就是:

  • 什么时候往下分

    幂次大于1的时候继续往下分

  • 什么时候输出括号

    幂次等于1和0的时候直接输出22(0)

    其余幂次先输出2(,等内部递归结束后再输出)

  • 什么时候输出加号

    还需要往下分的时候