去考试的时候硬是将这道题打了个(dfs)，只过了(80)%的数据，回家路上才突然醒悟这道题的正解思路。
原来此题这么简单
“看来是智商日常不在线吧”
—— gyh
题目传送门
题面简述
给定正整数(n)，你需要判断这个数的所有拆分中，是否存在优秀的
拆分。若存在，请你给出具体的拆分方案(从大到小输出，空格隔开)。
优秀的拆分定义：
对于正整数(n)的一种特定拆分，我们称它为“优秀的”，当且仅当在这种拆分下,(n)被分解为了若干个不同的2的正整数次幂。
正解思路
“任何一个正整数都可以拆分成若干个(2)的非负整数次幂之和。”
——《小学奥数》
既然是(2)的非负整数次幂之和,我们可以直接将它转换为(2)进制
例如：
(n=24_{10}=11000_{2})
然后从大到小输出这一位是(1)的位权值
例如：
(n=24_{10}=11000_{2}=16_{10}(10000_{2})+8_{10}(1000_{2}))
输出结果就是
(16) (8)
另外，所有的奇数都木有优秀的拆分
因为奇数包含(2^0)
0不是正整数(不会吧不会吧，不会真的有人不知道0不是正整数吧)
如果是奇数，直接输出(-1)就行了。
上代码———
#include<iostream>
#include<cstdio>
using namespace std;
int main()
{
freopen("power.in","r",stdin);
freopen("power.out","w",stdout);//竞赛千万不要忘了这个
int n,i=0;
bool w[50];//由于只有0与1，可以使用布尔数组存储2进制数
cin>>n;
if(n&1)//等同于n%2==1，但是按位与运算速度更快
cout<<-1;
else
{
while(n)
w[i++]=n&1,n>>=1;//等同于w[i++]=n%2,n/=2;
for(i=i-1;i>=0;i--)
if(w[i])
cout<<(1<<i)<<" ";//输出2^i
}
return 0;//不要忘了写
}
其实还可以加一些优化，由于(2^i)的值是固定的，可以给(2)的非负整数次幂打一张表，输出时可以直接调用
优化后的代码———
#include<iostream>
#include<cstdio>
using namespace std;
const int hh[50]={1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536,131072,262144,524288,1048576,2097152,4194304,8388608,16777216};//最大到10^7，int可以存下
int main()
{
freopen("power.in","r",stdin);
freopen("power.out","w",stdout);
int n,i=0;
bool w[50];
cin>>n;
if(n&1)
cout<<-1;
else
{
while(n)
w[i++]=n&1,n>>=1;
for(i=i-1;i>=0;i--)
if(w[i])
cout<<hh[i]<<" ";//直接输出2^i
}
return 0;
}
这样速度就很快啦~~
时间复杂度是(O(2logn))
其实还可以再优化啦~~
再优化就要靠对位运算的熟练运用
从大到小判断(n)的这一位是不是(1)，是(1)就输出这一位的权值。
思路和上面差不多，但是可以省一个(while)循环
由于(n)最大是(10^7)，可以直接从(2^{24})开始枚举((2^{24})是最贴近(10^7)且小于(10^7)的(2)的非负整数次幂)
感谢来自(Daddy)的思路提供
上代码———
#include<iostream>
using namespace std;
int main()
{
int n;
cin>>n;
if(n&1)
cout<<-1;
else
for(int i=1<<24;i>0;i=i>>1)//i从2^24开始枚举,一直枚举到2^1
if(n&i)//如果这位是1
cout<<i<<" ";//输出这一位的位权值
return 0;
}
主要程序(从第10行到第12行)一共会运行24次
时间复杂度是(O(1))
对于一些不大于(10^7)的大数据来说，比上面快两倍
真是想不通比赛的时候自己为什么要打暴搜
最后