PDF文档回复:20240927

1 2020 CSP-J 题目1 优秀的拆分

[题目描述]

一般来说，一个正整数可以拆分成若干个正整数的和

例如，1=1，10=1+2+3+4 等。对于正整数 n的一种特定拆分，我们称它为“优秀的”，当且仅当在这种拆分下，n被分解为了若干个不同的 2 的正整数次幂。注意，一个数 x 能被表示成 2 的正整数次幂，当且仅当 x 能通过正整数个 2 相乘在一起得到

例如，10=8+2=2^3 + 2^1 是一个优秀的拆分。但是，7=4+2+1=2^2 + 2^1 + 2^0 就不是一个优秀的拆分，因为 1 不是 2 的正整数次幂

现在，给定正整数 nn，你需要判断这个数的所有拆分中，是否存在优秀的拆分。若存在，请你给出具体的拆分方案

[输入格式]

输入只有一行，一个整数 n，代表需要判断的数

[输出格式]

如果这个数的所有拆分中，存在优秀的拆分。那么，你需要从大到小输出这个拆分中的每一个数，相邻两个数之间用一个空格隔开。可以证明，在规定了拆分数字的顺序后，该拆分方案是唯一的

若不存在优秀的拆分，输出 -1

[输入输出样例]

输入 #1

6

输出 #1

4 2

输入 #2

7

输出 #2

-1

说明/提示

样例 1 说明

6=4+2=2^2 + 2^1 是一个优秀的拆分。注意，6=2+2+2 不是一个优秀的拆分，因为拆分成的 3 个数不满足每个数互不相同

数据范围

对于 100% 的数据，1≤n≤10^7

2 相关知识点

1) 对数函数

C++提供了几个对数函数，可以用于计算不同底数的对数

自然对数

#include<bits/stdc++.h>
using namespace std;
/*自然对数 以e为底的对数 e的值约为2.718281828459045 
*/
int main(){double x= 3; double natural_log = log(x);cout<<natural_log<<endl;x= 2.718281828459045;natural_log = log(x);cout<<natural_log<<endl;return 0;
}
/*
输出
1.09861
1 
*/ 

10为底对数

#include<bits/stdc++.h>
using namespace std;
/*10为底的对数log10(100)=2 
*/
int main(){double x= 100; double _log10 = log10(x);cout<<_log10<<endl;x= 1000;_log10 = log10(x);cout<<_log10<<endl;return 0;
}
/*
输出
2
3
*/ 

2为底对数

#include<bits/stdc++.h>
using namespace std;
/*2为底的对数log2(16)=4 
*/
int main(){double x= 4; double _log2 = log2(x);cout<<_log2<<endl;x= 32;_log2 = log2(x);cout<<_log2<<endl;return 0;
}
/*
输出
2
5
*/ 

2) 幂函数

cmath pow

#include<iostream>
#include<cmath>
using namespace std;
/*pow函数该函数接收两个参数，base 为要取次方的数，exponent 为指数。返回结果为 base 的 exponent 次方 double x =pow(base,exponent);pow=(2,3)=8 
*/ 
int main(){int base=2;int exponent=3;double x=pow(base,exponent);cout<<x<<endl;exponent=4;x=pow(base,exponent);cout<<x<<endl;return 0;
}
/*
输出
8
16 
*/ 

3) 打表

在编程中，是指将重要或计算成本较高的结果预先计算好并存放在内存（表）中，以供后续操作快速引用。这种技术经常在解决算法问题时使用，尤其是面对那些具有固定规律性、重复运算量大的场景

提前计算2的幂次方，把符合范围的2的幂次方都提前计算存储数组中，后续可以直接使用

#include<bits/stdc++.h>
using namespace std;
int n,a[30],m=1;
/*计算所有小于10^7的数的2的幂存储的数组a
*/
int main(){for(int i=0;i<=22;i++){m*=2;a[22-i]=m;}for(int i=0;i<=22;i++){cout<<a[i]<<" ";} return 0;
}

输出a数组数据如下

3 思路分析

思路1

1 可以分解到最小2^1次幂的和，一定是偶数，所以奇数返回-1
2 通过log2(n)计算以2为底n的对数_log2，再通过2^(_log2)计算小于n的2的最大幂次数
3 每次去除并输出2的最大幂次数
4 剩余的n 重复步骤2

#include<bits/stdc++.h>
using namespace std;int main(){int n;cin>>n;if(n%2==1){//奇数返回-1cout<<-1;return 0;}while(n>1){int x=log2(n);//n的最大幂int base=pow(2,x);//n的最大幂次数 比如n=16 此时base为16 ，n=17此时base也为16 if(n>=base){//有2的幂次数n-=base;//去除本次输出的2的幂次数cout<<base<<" ";//输出此次2的幂次数}}
}

思路2

同思路1，计算2的幂次数使用打表法

提前计算所有小于等于n的最大幂次数，此时n的最大取整为10^7

#include<bits/stdc++.h>
using namespace std;int n,a[30],m=1;
int main(){for(int i=0;i<=22;i++){//打表提前计算所有小于10^7的幂次数，从大到小存储到a数组m*=2;a[22-i]=m;}cin>>n;if(n%2==1){//奇数返回-1cout<<"-1";return 0;}int idx=0;while(n>0 && idx<=23){//n都去除所有的2的幂次数if(n>=a[idx]){//包含此2的幂次数cout<<a[idx]<<" ";//输出此2的幂次数n=n-a[idx];//去除此2的幂次数}idx++;//找下一个2的幂次数}return 0;
}