AcWing 3483. 2的幂次方--不会递归,无奈暴力
原题链接
中等
作者:
中间层
,
2021-05-19 19:55:20
,
所有人可见
,
阅读 609
思路
1. 如何得到n对应的各个次方;
首先n在(1,20000)内, 不到2^15次方, 只要对每个2^K 从大到小对答案进行搜索;
2. 如何输出幂次方的结果
2.1 首先把枚举的结果存到path数组中;
2.2 然后根据path数组存的值依次输出幂次方的形式;
PS: 先提前打个表,提前把对应的幂次方表示结果存到数组里就好;
算法1
(暴力枚举+hash)
C++ 代码
#include<iostream>
#include<cmath>
#include<vector>
#include<string>
using namespace std;
string _hash[15]; /*存的是数对应的2的幂次方表示*/
int _i2p[15]; /*存的是对应的2次方值*/
int n;
/**
* 从大到小搜索;
* 出口: idx < 0 || target == 0;
*/
bool dfs(int idx, int target, vector<int>& path){
if(target == 0) return true;
if(idx < 0) return false;
for(int i = idx; i >= 0; i--){
int next = target - _i2p[i];
if(next < 0) continue;
//选择当前值;
path.push_back(i);
if(dfs(idx-1, next,path)) return true;
//不选择当前值;
path.pop_back();
if(dfs(idx-1, target, path)) return true;
}
return false;
}
void init(){ //打表
_hash[0] = "0";
_hash[1] = "";
_hash[2] = "2";
_hash[3] = "2+2(0)";
_hash[4] = "2(2)";
_hash[5] = "2(2)+2(0)";
_hash[6] = "2(2)+2";
_hash[7] = "2(2)+2+2(0)";
_hash[8] = "2(2+2(0))";
_hash[9] = "2(2+2(0))+2(0)";
_hash[10] = "2(2+2(0))+2";
_hash[11] = "2(2+2(0))+2+2(0)";
_hash[12] = "2(2+2(0))+2(2)";
_hash[13] = "2(2+2(0))+2(2)+2(0)";
_hash[14] = "2(2+2(0))+2(2)+2";
for(int i = 0; i < 15; i++){
_i2p[i] = pow(2,i);
}
}
int main(){
int n;
init();
while(cin>>n){
vector<int> path;
string ans;
dfs(14,n,path);
int m = path.size();
string head = "2(", end = ")+";
for(int i = 0; i < m; i++){
if(path[i] != 1){
ans += head+_hash[path[i]]+end;
}else{
ans += "2+";
}
}
ans.erase(ans.size()-1,1);
cout<<ans<<endl;
}
return 0;
}
六