[数据结构与算法]P7071 [CSP-J2020] 优秀的拆分 题解

这题是一道大水题其实也挺简单的

没有看过这道题的“大佬们”赶紧康康?题面

我们先来分析一下这道题：

n 被分解为了若干个不同的 2 的正整数次幂。

注意：一个数 x 能被表示成 2?的正整数次幂，当且仅当 x?能通过正整数个 2 相乘在一起得到。

我们再来分析一下：

首先，我们知道 n 一定是分成了 2 的正整数次幂，所以一定不能为奇数

由此可以得出下面的代码：

if (n % 2 == 1){
	cout << "-1";
	return 0;
}

然后，我们有一个 long long 类型的 vector 来储存每一次 n mod 2?的值

最后的最后，用一个?简简单单的? for 循环来搞定输出

话不多说，其实已经说了很多话了下面我们直接上代码：

#include <bits/stdc++.h>

using namespace std;

int main(){
	vector<long long> v; 
	long long n;
	cin >> n;
	if (n % 2 == 1){// 进行特判，如果是奇数，直接输出 "-1"，并且直接 return 掉
		cout << "-1";
		return 0;
	}
	while(n != 0){// while 循环来储存，每一次 n mod 2 的结果便于输出
		v.push_back(n % 2);
		n /= 2;
	}
	for (int i = v.size() - 1;i >= 0;i--){// 从后往前做 for 循环，毕竟要从大到小输出嘛~~~
		if (v[i] != 0){// 如果 v[i] 为 1 就输出，因为如果为 0 就要往后叠加，叠加到 n mod 2 为 1 的时候
			long long t = pow(2,i);
			cout << t << " ";
            // 此处不能简写成 cout << pow(2,i) << " ";
            // 因为这样写，数字过大，程序会自动转成科学计数法
		}
	}
    return 0;//华丽的结束~~~
}

这时本蒟蒻的第一篇题解，大佬们赏个赞呗~~~