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){//奇数返回-1
cout<<-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){//奇数返回-1
cout<<"-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;
}