题解 P7071 【优秀的拆分(暂无数据)】

ccbb0530

2020-11-07 17:02:44

Solution

不得不说,今年的普及组第一题比去年难太多了 题目大意: 将给定的数n用2^k数的和表示(k为正整数) 20分代码: 如果真有人不会写的话,下面这个代码可以帮助你: 因为k>=1, 所以n若能表示,必定是偶数 则若n为奇数时,输出"-1"。 ```cpp if (n%2==1) cout<<-1<<endl; ``` 40分代码: 在上面的基础上,再考虑n=2^k的形式 此时,直接输出原数即可。 ```cpp if (n%2==1) cout<<-1<<endl; else cout<<n<<endl; ``` 60分代码: 在此不细说了,将40分代码+讨论1<=n<=10的情况 100分代码: 这个代码还是很好想的。 题目给定n<=1e7,我们可以将2^k存入一个数组里 为了保险,我将最大的k定为25 然后将给定的n进行暴力,尝试去减掉2^k方数,并输出。 上代码: ```cpp #include <bits/stdc++.h> using namespace std; int a[30],b[150]; int main() { freopen("power.in","r",stdin); freopen("power.out","w",stdout); a[1]=2; for (int i=2;i<=25;++i) a[i]=a[i-1]*2; int n; cin>>n; int tmp=n,j=1; while (tmp!=0){ for (int i=25;i>=1;--i) if (a[i]<=tmp){ tmp=tmp-a[i]; b[j]=a[i]; j++; break; } if (tmp==1){ cout<<-1<<endl; return 0; } } for (int i=1;;++i){ if (b[i]==0) break; cout<<b[i]<<" "; } cout<<endl; return 0; } ``` 希望考试的同学们都能获得一个好成绩!