1.题目
题目大致意思是说给定一个正整数NN,让你用二进制表示(但不包括2^020),又因为我们可以证明二进制可以表示任何整数,所以在题目中,只要是偶数,就是“优秀的拆分”,因此,如果NN为奇数,就可以直接排除,即输出-1−1。
接着我们来看NN为偶数的情况,由于二进制有其专有的特性,就是说如果能取大的,就尽量取大的,因此我们只需要从最大的二的正整数幂找起,然后一次次除以二,一直除到二时,就可以结束。
于是我们用a_iai来表示二的ii次幂,所以只要用boolbool型来存即可。
2.代码
#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。 }
3.结语
请大家祝福一下我,祝我能过入门组!!!