这个有个小结论吧,应该不是用搜索
by iiiiiyang @ 2022-07-28 06:56:05
@[zhaosi_0930](/user/652419) 可以直接用位运算的()
by cmaths @ 2022-07-28 06:59:56
@[zhaosi_0930](/user/652419)
+ 这不是 $\tt BFS$
+ 这是用二进制做的
by SegTree @ 2022-07-28 08:07:25
@[jpb_Saturn](/user/678965)
二进制做法能看懂,只是想把搜索优化一点
by zhaosi_0930 @ 2022-07-28 11:04:17
```cpp
#include<iostream>
#include<cmath>
#include<iomanip>
#include<cstdio>
#include<cstring>
using namespace std;
int mi[25],cunchu[101],n;
bool mib[30];
bool b;
int sum,i;
void bfs(int step,int ht)
{
if(step>int(log(n)/log(2))+1){
return;
}
if(b==true)
{
return;
}
if(sum==n)
{
b=true;
if(cunchu[1]!=0)printf("%d ",cunchu[1]);
for(int i=2;i<step;i++)
{
printf("%d ",cunchu[i]);
}
exit(0);
}
if(sum>n)
{
return;
}
for(int ij=ht;ij>=1;ij--)
{
if(mib[ij]==false)
{
cunchu[step]=mi[ij];
sum+=cunchu[step];
mib[ij]=true;
bfs(step+1,ht);
sum-=cunchu[step];
mib[ij]=false;
}
}
}
int main ()
{
sum=1;
cin>>n;
if(n%2!=0)
{
printf("-1");
return 0;
}
for(i=1;sum<n;i++)
{
sum*=2;
mi[i]=sum;
}
sum=0;
bfs(1,i);
if(b==false)
{
printf("-1");
}
return 0;
}
```
@[zhaosi_0930](/user/652419)
帮您加了一个剪枝就能过
by SegTree @ 2022-07-28 11:51:17
[record](https://www.luogu.com.cn/record/81494184)
by SegTree @ 2022-07-28 11:57:15
@[jpb_Saturn](/user/678965)
谢谢(^-^)
by zhaosi_0930 @ 2022-07-28 12:53:14
不用bfs,bfs太麻烦了,我程序36行。
```cpp
#include <bits/stdc++.h>
using namespace std;
string join(vector<unsigned> arr, const char* interval = " ") {
string result;
unsigned len = arr.size() - 1;
for (unsigned i = 0; i < len; i++) {
result += (to_string(arr[i]));
result += interval;
}
result += to_string(arr[len]);
return result;
}
string apart(unsigned num) {
if (num == 0 || num % 2)
return "-1\n";
vector<bool> aprt;
for (num /= 2; num > 0; num /= 2)
aprt.push_back(num % 2);
vector<unsigned> result;
for (unsigned i = 0, j = 2; i < aprt.size(); i++, j *= 2)
if (aprt[i])
result.push_back(j);
reverse(result.begin(), result.end());
return join(result) + '\n';
}
int main() {
// freopen("P7071_2.in", "r", stdin);
// freopen("P7071_2.ans", "w", stdout);
unsigned num;
cin >> num;
cout << apart(num);
// fclose(stdin);
// fclose(stdout);
return 0;
}
```
by hansiqi2011 @ 2022-10-02 07:53:18
_谁说要bfs??_
```cpp
#include<bits/stdc++.h>
using namespace std;
int n, t;
int main() {
cin >> n;
if (n % 2 || (!n)) {
cout << -1 << endl;
return 0;
}
t = n;
while (t & (t - 1))t--;
while (n != 0) {
if (n >= t) {
n -= t;
cout << t << " ";
}
t /= 2;
}
return 0;
}
```
by YHX2010 @ 2022-10-27 18:00:48