♐ CSP_J 组真题
2020年
1. 优秀的拆分

线上OJ:

洛谷:https://www.luogu.com.cn/problem/P7071 (opens in a new tab)
acwing:https://www.acwing.com/problem/content/2769/ (opens in a new tab)
一本通:http://ybt.ssoier.cn:8088/problem_show.php?pid=2004 (opens in a new tab)

核心思想:

由题意可知,
1、如果 n 是奇数,则肯定不可能为 2 的幂次方和。因为 1 不是 2 的正整数次幂。 所以,如果 n 是奇数,直接输出 -1 即可。
2、如果 n 是偶数,则本题就变成了十进制转二进制,然后从高位起遇到1则输出。

关于十进制转二进制方法举例:
十进制的10能实现优秀的拆分 10 = 8+2,实际上对应着二进制后的 1010 ,即
10 / 2 = 5 … 0
5 / 2 = 2 … 1
2 / 2 = 1 … 0
1 / 2 = 0 … 1
先得到的余数是低位,后得到的是高位。按倒序取余数,得到 10 对应的二进制数字为1010
第一个1对应着 23=82^3=8 ,第二个1对应 21=22^1=2。 所以,本题就变成了十进制转二进制,然后从高位起遇到1则输出

注意:最后输出时由于使用 pow() 函数,但 pow()的返回是 double型,故需强制加上 int() 转换

题解代码:

#include<bits/stdc++.h>
using namespace std;
 
int n; 
 
int main()
{	
	cin >> n;
	int num, a[100], i;	//r:数字数组 ri:数组填充用下标 
	
	if(n % 2 == 1)	cout << -1;	// 如果是奇数,直接输出 -1 	
	else
	{	// 这个for实现 10进制转 2进制 
	    for(i = 0; n > 0; i++)	a[i] = n%2, n/=2;     // 保留余数至a[i],然后n/2准备下一轮除余 
	    
        for(int j = i - 1; j >= 0; j--)		//倒序遍历数组 
        {
            if(a[j] == 1)
                cout << int(pow(2, j)) << " "; //注意:pow返回浮点型,且浮点型在很长时输出样式可能变为科学计数法,故此处必须加上强制转换 int() 
        }
	}
	return 0;
}