题解 | 幂次方-牛客假日团队赛8L题

题目描述

任何一个正整数都可以用2的幂次方表示。例如：                  
        
同时约定方次用括号来表示，即a可表示为。
由此可知，137可表示为：

进一步：（用表示）

  
所以最后可表示为：

又如：

所以最后可表示为：
 

正整数

符合约定的n的0，2表示（在表示中不能有空格）

示例1

1315

2(2(2+2(0))+2)+2(2(2+2(0)))+2(2(2)+2(0))+2+2(0)

解答

#include<bits/stdc++.h>
using namespace std;
int x,a[32];
void npow(int n){
		for(int i=x;i>=0;--i){
			if(a[i]<=n){
				n=n-a[i];
				if(i>1){
					cout<<"2(";
					npow(i);       //可以理解为DFS搜索
					cout<<")";     //回溯     
				}
		       if(i==1) cout<<"2";
			   if(i==0) cout<<"2(0)"; 
			   if(n!=0) cout<<"+"; //若此n还没分解完，则后面还有项，所以输出一个+号
			}
		
		}	
}

int main()
{
	int n;
	cin>>n;
	a[0]=1;
	while(a[x]<n){
		x++;
		a[x]=a[x-1]*2;
	}
	npow(n);
	cout<<endl;
	return 0;
}

方法二：分治的思想，把一个数X分解为 和进行递归求解，这样可以简单的处理好“+”号的问题。

#include<bits/stdc++.h>
 using namespace std;
string f(int x){
    if (x==1) return "2(0)";
    if (x==2) return "2";
    if (x==3) return "2+2(0)";   //防止3 输出2（2（0））+2（0）；
    int n=log2(x);                      // 求出指数取整  
    int t=pow(2, n);                 
    if (x==t) return "2("+f(n)+")";              // x 恰好是 2的n次放，后面就没有了 不需要+号。
    else return "2("+f(n)+")+"+f(x-t);       //不是2的n次方，那么对2部分分别进行递归求解用+号连接
}
int main(){
    int x;
    cin>>x;
    cout<<f(x)<<endl;
}

方法三：打表法（作弊）
因为题目中数据规模是 ，所以如果 我们把指数0-14 的表示好放在一个字符串数组里面，如果来了一个数X，我们只需要把对应的幂次方直接输出即可。

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin>>n;
    string s[16]={"2(0)","2","2(2)","2(2+2(0))","2(2(2))","2(2(2)+2(0))","2(2(2)+2)",
    "2(2(2)+2+2(0))","2(2(2+2(0)))","2(2(2+2(0))+2(0))","2(2(2+2(0))+2)",
    "2(2(2+2(0))+2+2(0))","2(2(2+2(0))+2(2))","2(2(2+2(0))+2(2)+2(0))",
    "2(2(2+2(0))+2(2)+2)","2(2(2+2(0))+2(2)+2+2(0))"};
    bool temp=0;
    for(int i=15;i>=0;i--)
		if(pow(2,i)<=n)
		{
		 	n-=pow(2,i);
			if(temp)
				cout<<'+';
			cout<<s[i];
			temp=1;
		}
    return 0;
	}