当前位置:网站首页>Csp-j-2020-excellent split multiple solutions
Csp-j-2020-excellent split multiple solutions
2022-07-05 05:20:00 【Korloa】
Title Description
Generally speaking , A positive integer can be split into the sum of several positive integers .
for example ,1=1,10=1+2+3+4 etc. . For positive integers n A specific split of , Let's call it alpha “ first-class ”, If and only if under this split ,n It's broken down into a number of Different Of 2 Of Positive integer The next power . Be careful , a number x Can be expressed as 2 The positive integer power of , If and only if x Can pass a positive integer 2 Multiply together to get .
for example ,
Is an excellent split . however , It's not an excellent split , because 1 No 2 The positive integer power of .
Now? , Given a positive integer n, You need to judge all the splits of this number , Is there a good split . If exist , Please give us the specific split plan .
Input
There is only one line of input , An integer n, Represents the number to be judged .
Output
If all the splits of this number , There are excellent splits . that , You need to output every number in this split from large to small , Separate two adjacent numbers with a space . Can prove that , After specifying the order of splitting numbers , The splitting scheme is unique .
If there is no good split , Output -1
.
Examples 1
The sample input 1
6
Sample output 1
4 2
explain
Is an excellent split . Be careful ,6=2+2+2 Not a good split , Because it's split into 3 The number is not satisfied, and each number is different from each other .
Examples 2
The sample input 2
7
Sample output 2
-1
Data scale
- about 20% The data of ,n≤10.
- For another 20% The data of , Guarantee n It's odd .
- For another 20% The data of , Guarantee n by 2 The positive integer power of .
- about 80% The data of ,n≤1024.
- about 100% The data of ,
Ideas
Readers can find a rule , For a number N, If it is greater than 1 An even number of , It must meet an excellent split .
For a number of legal excellent split , You will find that you can enumerate from large to small , This becomes a bit operation . Of course, if you don't find it , Just use it DFS
AC Code ( Bit operation is not optimized )
#include<iostream>
using namespace std;
unsigned long long n;
int main(){
cin>>n;
if(n%2==1 || n<2){
cout<<"-1";
return 0;
}
else{
for(unsigned long long i=1<<30;i>0;i>>=1){
if(i<=n){
n=n-i;
cout<<i<<" ";
}
if(n==0)break;
}
}
return 0;
}
AC Code ( Bit operation optimization )
#include<cstdio>
signed main(){
int n;
scanf("%d",&n);
if(n%2==1 || n<2){
putchar('-');
putchar('1');
return 0;
}
int i=2;
while(i*2<=n)i<<=1;
while(n!=0){
if(i<=n){
n=n-i;
printf("%d ",i);
}
i>>=1;
}
return 0;
}
ha-ha , I used it very informally during the exam DFS, Yes, I'm the good one , Fortunately, the data is not large .
DFS Code Here
#include<cstdio>
int ans[100];
int n,tot=0;
int dfs(int start){
for(int i=start;i<=n;i=i*2){
if(i==n){
printf("%d ",i); // Output in reverse order
for(int j=tot;j>0;j--){
printf("%d ",ans[j]);
}
return 0;
}
else if(i<=n){
n=n-i;
ans[++tot]=i;
dfs(i*2);
tot--; // Restore
n=n+i;
}
else
return 0;
}
}
int main(){
scanf("%d",&n);
if(n%2==1 || n<2){
printf("-1");
return 0;
}
else
dfs(2);
return 0;
}
Thank you for your support
边栏推荐
- 使用Room数据库报警告: Schema export directory is not provided to the annotation processor so we cannot expor
- Heap sort summary
- 支持多模多态 GBase 8c数据库持续创新重磅升级
- sync.Mutex源码解读
- Three dimensional dice realize 3D cool rotation effect (with complete source code) (with animation code)
- Introduction to memory layout of FVP and Juno platforms
- Quick sort summary
- MySQL数据库(一)
- 对象的序列化
- Add level control and logger level control of Solon logging plug-in
猜你喜欢
YOLOv5添加注意力机制
Reverse one-way linked list of interview questions
Applet live + e-commerce, if you want to be a new retail e-commerce, use it!
[轉]: OSGI規範 深入淺出
The present is a gift from heaven -- a film review of the journey of the soul
Quick sort summary
C语言杂谈1
win10虚拟机集群优化方案
Research on the value of background repeat of background tiling
Binary search basis
随机推荐
Ue4/ue5 illusory engine, material chapter, texture, compression and memory compression and memory
Magnifying glass effect
[to be continued] [UE4 notes] L2 interface introduction
BUUCTF MISC
xftp7与xshell7下载(官网)
远程升级怕截胡?详解FOTA安全升级
Web APIs DOM节点
[turn to] MySQL operation practice (III): table connection
2022 / 7 / 1 Résumé de l'étude
2022上半年全国教师资格证下
UE fantasy engine, project structure
A preliminary study of sdei - see the essence through transactions
Unity card flipping effect
[转]: OSGI规范 深入浅出
lxml.etree.XMLSyntaxError: Opening and ending tag mismatch: meta line 6 and head, line 8, column 8
MySQL数据库(一)
What is the agile proportion of PMP Exam? Dispel doubts
Ue4/ue5 illusory engine, material part (III), material optimization at different distances
Haut OJ 1347: addition of choice -- high progress addition
2022/7/2 question summary