【洛谷】【P1010题解】 [NOIP1998 普及组] 幂次方
题目描述
描述:输入一个整数n,1 <= n < 2 * 10^4
举例:
1315
答案:
2(2(2+2(0))+2)+2(2(2+2(0)))+2(2(2)+2(0))+2+2(0)
分析:
因为1315=210+28+2^5+2+1,所以输出2(2(2+2(0))+2)+2(2(2+2(0)))+2(2(2)+2(0))+2+2(0)
题目思路:
-
首先,确定大的解题方向:观察1315及其答案,很容易发现1315需要被拆解成2的n次方之和,并且这个n也需要拆解,1需要拆成2(0),2不需要拆。所以,可以尝试用递归去解决这个问题。
因为整个解题过程就把大的数拆成小的数,当这个数拆到1或2时,就可以直接返回。 -
如何拆数?因为是2的幂次方之和,所以需要log2函数来辅助拆数。
即:int num = (int)log2(n)
--------①
这里的n是要求的数,得到的num是能分解出的最大2的幂次方数的幂。
举个例子:如n=3=2^1+1时,num=1
很明显log2(n)不一定是一个整数,比如上面的n,当处理完21后,还剩下一个1需要处理,观察答案,在21和1的中间需要插入一个+号。
总结:输入数n,调用①,得到num,求解num,然后判断(key = (int)pow(2, num))==n?
,如果相等,就不需要做任何处理。不相等,需要输出一个+号,然后继续求解n-key. -
完善思路。按照第二步走,很明显可以一个很大的n化解成两部分,一个是n中能取的最大2的幂次方数,一个是剩余部分。然后递归调用,所以两部分各自都会继续再分,直到分到最小值时退出(也就是2和2(0))。
但是考虑到题目所给的n的范围,思考:2049=210+210+1,如果只是按照上述实现会发现10会被重复求两次,当重复过多时会浪费大量不必要的时间,所以需要使用记忆化递归,用map来记录已求的n对应的字符串,递归的返回值也因此需要是string。
整理思路
- 声明函数DFS,输入int n,返回string
编写递归函数体: - 先判断当前n是否在map中存在,如果存在直接返回
- 使用①求出num,此时需要注意2的num次方也有可能重复计算,所以需要得到2的num次方的值(根据题意是不可能溢出的)并赋值给key,判断这个key是否在map中存在,如果存在,用临时变量string temp记录这个结果,如果不存在,则需要按照题意令temp=“2(” + DFS(num) + “)”;,直接求这个num的再进行拼接。
- 继续判断key是否等于n,如果相等就代表上一步已经分割完n,记录temp后,直接返回temp即可。不然,需要使用temp += “+” + DFS(n - key);,将剩下的部分连上+号,追加到temp的后面。
- 当前temp已经求解完毕,用n作为key,temp作为value,使用unordered_map<int,string>记录。最后返回这个temp
- 函数体编写完毕,剩下最轻松的部分:
- (1)用变量n,完成键盘录入。
- (2)声明map,初始化um[1] = “2(0)”;和um[2] = “2”;
- (3)输出DFS(n)
代码实现(c++)
#include<iostream> // 基本输入输出
#include<cmath> // log2和pow
#include<unordered_map> // map
using namespace std;
unordered_map<int, string> um;
string DFS(int n){
if(um.find(n) != um.end()){ return um[n];}
string temp;
int num = (int)log2(n), key = (int)pow(2, num);
if(um.find(key) != um.end()){ temp = um[key];}
else{
temp = "2(" + DFS(num) + ")";
}
if(key != n){
temp += "+" + DFS(n - key);
}
um[n] = temp;
return temp;
}
int n;
int main(){
cin >> n;
// 非常关键的初始化工作
um[1] = "2(0)";
um[2] = "2";
// 直接打印结果
cout << DFS(n);
return 0;
}
时空复杂度就不分析了…水平有限,望轻喷
特么写了这么多,发现不能作为题解发出去…只好直接放CSDN上了