【正经题解】优秀的拆分

AC君

2024-02-20 16:56:08

发布于：浙江

192阅读

0回复

0点赞

题目大致意思是说给定一个正整数N，让你用二进制表示），又因为我们可以证明二进制可以表示任何整数，所以在题目中，只要是偶数，就是“优秀的拆分”，因此，如果N为奇数，就可以直接排除，即输出−1。

接着我们来看N为偶数的情况，由于二进制有其专有的特性，就是说如果能取大的，就尽量取大的，因此我们只需要从最大的二的正整数幂找起，然后一次次除以二，一直除到二时，就可以结束。

于是我们用ai

来表示二的i次幂，所以只要用bool型来存即可。

#include<bits/stdc++.h>
using namespace std;

const int maxn=100005;

int n;

long long now=1; //now代表二的次数幂。 

bool a[105];

int main()
{
	//freopen("power.in","r",stdin);
	//freopen("power.out","w",stdout);
	
	scanf("%d",&n);
	
	if (n%2!=0)
	{
		printf("-1");
		return 0;
	} //如果n为奇数，直接输出-1。 
	
	int i=0; //i用来存最高次数。 
	
	while(now*2<=n)
	{
		now*=2;
		i++;
	} //先将最大的幂求出来。 
	
	int i1=i; //这里不能直接用i，后面还要用到。 
	
	while(now>1)
	{
		if (n-now>=0)
		{
			a[i1]=1;
			n-=now;
		}
		i1--;
		now/=2;
	} //看每一次数有没有。 
	
	for (register int j=i;j>=1;--j)
	{
		if (a[j]==0) continue;
		long long ans=pow(2,j);
		printf("%lld ",ans);
	} //最后在输出拆分出来的，记住从大到小。 
	
	return 0; //一定要返回值0。 
}

有帮助，赞一个

去预览

0/2000

全部评论 3

Konglh1013

#include<bits/stdc++.h>
using namespace std;
int n;
int main(){
	cin>>n;
	if(n&1){
		cout<<-1;
	}
	else{
		for(int i=23;i>=1;i--){
			if((n>>i)&1){
				cout<<(1<<i)<<" ";
			}
		}
	}
}

2025-11-02 来自重庆

凤凰织梦

#include<iostream>
using namespace std;
int add(int x0){
    int x=x0;
    for(int i=1;;i=i*2){
        if(i>x){
            return i>>1;
        }
    }
    return 0;
}
int main(){
    int n;
    cin>>n;
    if(n%2==1){
        cout<<-1;
        return 0;
    }
    int c;
    while(n!=0){
    //for(int i=0;i<10;i++){
        //cout<<n<<" ";
        c=add(n);
        cout<<c<<" ";
        n-=c;
    }
    return 0;
}

2025-11-19 来自广东

AC是最好的

没我好

#include <bits/stdc++.h>

using namespace std;

long long n;

int main( ) {
	cin >> n;
	
	if (n % 2 == 1) {
		cout << "-1" << endl;
		return 0;
	}
	long long x = log2(n);
	
	for (int i = x ; i >= 1 ; i--) {
		if ((1 << i) <= n) {
			cout << (1 << i) << " ";
			n -= (1 << i);
		}
	}
	
	return 0;
})

2025-09-12 来自福建