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
        }
    }
}