优秀的拆分[CSP-J2_2020]

admin

题目描述[color=rgba(0, 0, 0, 0.75)]

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

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

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

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

输入格式[color=rgba(0, 0, 0, 0.75)]

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

输出格式[color=rgba(0, 0, 0, 0.75)]

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

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

直播获奖[CSP-J2_2022]

admin

·n是奇数，则2的a次方必有一个是偶数，即a = 0，但是a必须是正整数，所以输出-1

·其余情况，从pow(2,1)开始枚举，一直到10^7，找到最大的小于a的数，然后a减去这个数，继续递推下去，就能得到答案，最后用一个数组储存就可以了

1. #include <bits/stdc++.h>
   
2. using namespace std;
   
3. long long n,ans,j = 1;
   
4. int main(){
   
5.         cin>>n;
   
6.         if(n%2==1){
   
7.                 ans = -1;
   
8.                 cout<<ans;
   
9.                 return 0;
   
10.         }
    
11.         while(pow(2,j)<10000000){
    
12.                 if(pow(2,j)==n){
    
13.                         ans = n;
    
14.                         cout<<ans;
    
15.                         return 0;
    
16.                 }
    
17.                 j++;
    
18.                
    
19.         }
    
20.         while(n>=2){
    
21.                 int tmp = 1;
    
22.                 while(pow(2,tmp)<=n){
    
23.                         tmp+=1;
    
24.                 }
    
25.                 ans = pow(2,(tmp-1));
    
26.                 n-=ans;
    
27.                 cout<<ans<<" ";
    
28.         }
    
29.         return 0;
    
30. }

复制代码

admin

1. #include <bits/stdc++.h>
   
2. using namespace std;
   
3. int main() {
   
4.     freopen("power.in", "r", stdin);
   
5.     freopen("power.out", "w", stdout);
   
6.     int n;
   
7.     cin >> n;
   
8.     if (n & 1)
   
9.         puts("-1");
   
10.     else {
    
11.         for (int i = 30; i >= 0; i--) {
    
12.             if (n >> i & 1) {
    
13.                 printf("%d ", 1 << i);
    
14.             }
    
15.         }
    
16.     }
    
17.     return 0;
    
18. }

复制代码