banner

原题链接

https://www.luogu.com.cn/problem/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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include<iostream>
#include<cmath>
#define for(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
int n,mega[111];//mega数组存储预处理的2的1到14次方(2^15>20000,所以之后的枚举只需到14即可)
string open[15];
bool odd;//数的奇偶
void even()
{
if(n%2==0)return;
odd=1;
n-=1;//如果是奇数就直接先-1变成偶数,最后再把1补上
return;
}
int main()
{
cin>>n;
even();//判断奇偶
for(i,1,14)mega[i]=pow(2,i);//预处理并存储2的1~14次方
//前方高能,预处理并存储1~14拆分后的字符串,后面用
open[1]="2(0)";open[2]="2";open[3]="2+2(0)";open[4]="2(2)";
open[5]="2(2)+2(0)";open[6]="2(2)+2";open[7]="2(2)+2+2(0)";
open[8]="2(2+2(0))";open[9]="2(2+2(0))+2(0)";open[10]="2(2+2(0))+2";
open[11]="2(2+2(0))+2+2(0)";open[12]="2(2+2(0))+2(2)";
open[13]="2(2+2(0))+2(2)+2(0)";open[14]="2(2+2(0))+2(2)+2";
//前方高能,逐一枚举,七层循环最多支持拆分成8项(奇数拆分后末尾的2(0)单独特判)
for(x,0,14)
for(y,x,14)
for(z,y,14)
for(i,z,14)
for(j,i,14)
for(k,j,14)
for(l,k,14)
{
if(mega[i]+mega[j]+mega[k]+mega[l]+mega[x]+mega[y]+mega[z]==n)//如果满足条件就输出
{
if(l&&l!=1)cout<<"2("<<open[l]<<')';//特判,此项是0就不输出,是2的1次方就直接输出2,否则输出2(x),x也要拆,此时数据范围已经缩小到1~14,直接调用open数组然后输出即可
if(l==1)cout<<"+2";
if(k&&k!=1)cout<<'+'<<"2("<<open[k]<<')';
if(k==1)cout<<"+2";
if(j&&j!=1)cout<<'+'<<"2("<<open[j]<<')';
if(j==1)cout<<"+2";
if(i&&i!=1)cout<<'+'<<"2("<<open[i]<<')';
if(i==1)cout<<"+2";
if(z&&z!=1)cout<<'+'<<"2("<<open[z]<<')';
if(z==1)cout<<"+2";
if(y&&y!=1)cout<<'+'<<"2("<<open[y]<<')';
if(y==1)cout<<"+2";
if(x&&x!=1)cout<<'+'<<"2("<<open[x]<<')';
if(x==1)cout<<"+2";
if(odd)cout<<"+2(0)";//奇数的话,把末尾1补上
return 0;//找到一组就直接输出然后return0
}
}
}