【洛谷】P1010 幂次方(分治 + 递归)题解
程序员文章站
2022-03-02 22:49:56
...
原题链接:https://www.luogu.org/problem/P1010
题目描述
任何一个正整数都可以用22的幂次方表示。例如
同时约定方次用括号来表示,即a^b可表示为a(b)。
由此可知,137可表示为:
进一步:
7 = 2^2 + 2 + 2^0 (2^1用2表示),并且 3 = 2 + 2^0
所以最后137可表示为:
又如:
所以13151315最后可表示为:
输入输出格式
输入格式:
一个正整数n(n ≤ 20000)。
输出格式:
符合约定的n的0,2表示(在表示中不能有空格)
输入输出样例
输入样例#1:
1315
输出样例#1:
2(2(2+2(0))+2)+2(2(2+2(0)))+2(2(2)+2(0))+2+2(0)
说明
时空限制:1000ms 125M
思路:分治(子问题与子问题之间用加号连接)+递归
- 写一个将n分解的函数。
- 因为n小于等于20000,所以不会超过2的14次方。
- 然后倒着枚举,当找到第一个2的i次方不超过递归的参数,则判断此时i的大小。如果是0或者1则特判,如果大于1,则递归将i继续分解。
- 最后继续循环分解剩余的数。只要a没有分解完,则输出加号将各部分加起来。
代码如下:
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
void power(int a){
//n小于等于20000,所以不会超过2的14次方,同时倒着枚举,能减大的尽量减大的
for(int i=14;i>=0;i--){
if(pow(2,i)<=a){ //当2的幂次方第一次不大于a则符合
if(i==0) //2的0次方,特判
cout<<"2(0)";
else if(i==1) //2的1次方,特判
cout<<"2";
else if(i>1){ //当幂大于1
cout<<"2(";
power(i); //递归,继续分解i
cout<<")";
}
a-=pow(2,i); //继续循环分解剩下的
if(a!=0) //只要a还没有分解完,则输出加号继续循环
cout<<"+";
}
}
}
int main(){
int n;
cin>>n;
power(n); //调用函数
return 0;
}
上一篇: 【题解】洛谷P1010幂次方[NOIP1998普及] 分治
下一篇: 洛谷P1010幂次方