posted on 2020-11-12 17:22:31 | under 题解 | source
本题正解是二进制 or 位运算
- 理解题目
P7071 优秀的拆分(民间数据) 题目链接: https://www.luogu.com.cn/problem/P7071。
现在给你一个正整数 \(n\)，请把 \(n\) 分解为若干个不同的\(2\)的正整数次幂相加的形式。要求输出拆分方法，从大到小输出。
注意点：
- “若干”包括“1”，如果 \(n\) 是\(2\)的正整数次幂，不能输出\(-1\)。
- \(2\)的正整数次幂，不包括\(2^0\) (即\(1\))。
- 从大到小输出，不要从小到大。
- 输出的数相加一定与 \(n\) 相等，不要输出指数。
- 只有奇数输出\(-1\)，因为“\(2\)的正整数次幂”一定有质因子\(2\)，而偶数相加一定不会出现奇数。
- 骗分
我们先来看看数据规模：
多么仁慈的数据啊！ #1 和 #2 可以打表过， #3 和 #4 直接输出\(-1\)， #5 和 #6 可以直接输出 \(n\) ，一下子骗了\(60\)分，出题人直呼内行！
骗分代码：
#include<iostream>
#include<string>//打的表用string存
using namespace std;
int main(){
int n;cin>>n;
if(n<=10){
string db[11]={"-1","-1","2","-1","4","-1","4 2","-1","8","-1","8 2"};
cout<<db[n];
return 0;
}
if(n%2==1){
cout<<-1;
return 0;
}
cout<<n;//2的正整数次幂，由于是骗分，所以不用特判
return 0;
}
骗到\(60\)分之后，打开提交记录，查看最优解，然后……
- 正解
首先，先回想一下二进制转十进制的方法：
整数二进制用数值乘以\(2\)的幂次依次相加(用权值依次与每一位相乘并相加)，得出的就是这个数的十进制形式。
举个简单的例子：
\((10010)_2 = 1 \times 2^4 + 0 \times 2^3 +0 \times 2^2 +1 \times 2^2 + 0 \times 2^0 = 16 + 2 = 18\)
你看，这道题的题面，像不像让我们把 \(n\) 分解成这个形式？简直像极了！
如何操控一个数的二进制形式？很简单，n&1获得最后一位，n>>=1去掉最后一位，与STL中的a.top() a.pop()类似。
知道以上信息，我们可以写出这样的代码：
int n,i=1;// i 就是权值，初始值是2^0，再乘2就是2^1，以此类推。
while(n){//当n不等于0时
//如果在二进制里这一位是1，输出权值
if(n&1) printf("%d",i);
//n去掉最后一位，权值乘2
n>>=1;i*=2;
}
再加个奇数判断，提交，A……WA了好多个点！
原因是什么？题目叫你从大到小，你从小到大，不通过不是理所当然吗？
那么，有什么方法能解决这个问题呢？有！用栈！利用栈的特性，它可以用来做倒序输出。如果你还不懂栈，请看下面：
你可以把栈想象成一个薯片筒，先进入筒的薯片被压到最底下，后进来的薯片会放在最上面。当你要把薯片拿出来时，后进来的薯片就会先从筒里出来，先进入的反而最后才能出来。这就是栈先进后出、后进先出的特点。
- 栈的头文件：
#include<stack>，s-t-a-c-k-stack-栈。- 定义栈：
stack <int> a，其中int是存放的数据类型，a是栈的名字。- 把元素压进栈：
a.push(1)，其中1是压进去的元素。- 让元素出栈：
a.pop()，注意它不会返回出栈元素。- 获得栈顶元素：
a.top()，它一般和上面的pop一起使用。- 栈是否为空：
a.empty()，栈空时返回\(1\)，反之返回\(0\)。- 栈的元素个数：
a.size()，注意不要写成a.length()。
说了这么多，是时候给出 \(AC\) \(Code\) 了：(不能只看这里啊）
#include<cstdio>
#include<stack>//栈的头文件
using namespace std;
stack<int> a;//定义栈
int n,i=1;
int main(){
scanf("%d",&n);//输入
if(n&1)//奇数判断
return printf("-1"),0;
while(n){//当n不为0时
if(n&1) a.push(i);//把i压进栈
n>>=1,i<<=1;//n去掉最后一位，i乘2
}
while(!a.empty()){//当栈还不是空的时
printf("%d ",a.top());//输出最顶上的元素
a.pop();//砍掉最顶上的元素（出栈）
}
return 0;
}