首页 > 其他分享 >P7071 [CSP-J2020] 优秀的拆分

P7071 [CSP-J2020] 优秀的拆分

时间:2022-08-18 01:11:19浏览次数:65  
标签:正整数 nn 22 优秀 21 拆分 P7071 CSP J2020

题目描述

一般来说,一个正整数可以拆分成若干个正整数的和。例如,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,你需要判断这个数的所有拆分中,是否存在优秀的拆分。若存在,请你给出具体的拆分方案。

输入格式

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

输出格式

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

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

输入输出样例

输入 
6
输出 
4 2
输入 
7
输出
-1

说明/提示

样例 1 解释

6=4+2=2^2+2^16=4+2=22+21 是一个优秀的拆分。注意,6=2+2+26=2+2+2 不是一个优秀的拆分,因为拆分成的 33 个数不满足每个数互不相同。


数据规模与约定

  • 对于20%的数据,n≤10。
  • 对于另外20% 的数据,保证 n为奇数。
  • 对于另外20% 的数据,保证 n 为 2 的正整数次幂。
  • 对于80% 的数据,n≤1024。
  • 对于100% 的数据,1≤n≤107。
#include<iostream>
#include<cmath>
using namespace std;

int main(){
    int n;
    cin >> n;
    if(n%2 == 1)
        cout << -1;
    else{
        for(int i=23; i>0; i--){
            if(pow(2,i)<=n){
                cout<<int(pow(2,i))<<" ";
                n -= pow(2,i);
            }
        }
    }
    return 0;
}

 

标签:正整数,nn,22,优秀,21,拆分,P7071,CSP,J2020
From: https://www.cnblogs.com/dks0313/p/16597367.html

相关文章

  • P5660 [CSP-J2019] 数字游戏
    题目描述小K同学向小P同学发送了一个长度为8的 01字符串来玩数字游戏,小P同学想要知道字符串中究竟有多少个1。注意:01字符串为每一个字符是0或者1的字符......
  • P5681 [CSP-J2019 江西] 面积
    题目描述Alice有一个边长为 aa 的正方形,Bob有一个长宽分别为 b,cb,c 的矩形,请你告诉他们俩谁的图形面积更大。输入格式仅一行三个正整数 a,b,ca,b,c输出格......
  • P7909 [CSP-J 2021] 分糖果
    题目描述红太阳幼儿园有 nn 个小朋友,你是其中之一。保证 n\ge2n≥2。有一天你在幼儿园的后花园里发现无穷多颗糖果,你打算拿一些糖果回去分给幼儿园的小朋友们。由......
  • P7074 [CSP-J2020] 方格取数
    题目描述题目传送门()点击查看题目题目描述设有n*m的方格图,每个方格中都有一个整数。现有一只小熊,想从图的左上角走到右下角,每一步只能向上、向下或向右走一格......
  • Unity 代码调用重新生成csproj文件
    结论先放结论:editor代码中直接调用Unity.CodeEditor.CodeEditor.CurrentEditor.SyncAll();原因在一些操作后,比如修改csc.rsp的内容之后,需要重新生成csproj文件方......
  • CSP-J 2022备战——树的基础
    前身树,顾名思义,是一种植物一些基本概念:根节点:树上任意一点都可以被定义成根节点,也就是所有点的祖先祖节点(祖先):在某节点的上层,且跟该节点有直接联系的点父节点(父亲):在子......
  • CSP202112-4 磁盘文件操作
        第一眼,嗯,线段树裸题。开写,交,发现空间炸了,遂离散化。再交,发现在操作0的时候有可能遇到离散化中没出现过的点(即给定数据外的点),因为要二分右端点。怎么办呢?大胆观......