此文章是vip文章,如何查看?  

1,点击链接获取密钥 http://nicethemes.cn/product/view29882.html

2,在下方输入文章查看密钥即可立即查看当前vip文章


div2题目题解:I. Powers Of Two

  • 时间:
  • 浏览:
  • 来源:互联网

题目:
I. Powers Of Two
time limit per test4 seconds
memory limit per test256 megabytes
inputstandard input
outputstandard output
A positive integer x is called a power of two if it can be represented as x=2y, where y is a non-negative integer. So, the powers of two are 1,2,4,8,16,….

You are given two positive integers n and k. Your task is to represent n as the sum of exactly k powers of two.

Input
The only line of the input contains two integers n and k (1≤n≤109, 1≤k≤2⋅105).

Output
If it is impossible to represent n as the sum of k powers of two, print NO.

Otherwise, print YES, and then print k positive integers b1,b2,…,bk such that each of bi is a power of two, and ∑i=1kbi=n. If there are multiple answers, you may print any of them.

Examples
inputCopy
9 4
outputCopy
YES
1 2 2 4
inputCopy
8 1
outputCopy
YES
8
inputCopy
5 1
outputCopy
NO
inputCopy
3 7
outputCopy
NO

题意:
给n,k让你用k个二次幂数表示n;
我们知道9用二次幂数表示就是1 8,样例要用4个二次幂数来表示9就是1 2 2 4:
算是一个半水不水的手速题目:
首先要判断:最少要多少个二次幂数来表示n,如果k小于这个最小值,那就很尴尬了,所以要有特判,至于做法:
首先要用二进制表示n:
我们举个例子:19就是10011;(16+2+1)
这个10011放数组存着,然后就是记录1的个数,这个个数就是我们要用的表示出来n要用的最少的二次幂数的个数:

int i=n;
	int num=2;
	int time;
	int num_1=0;
	for(time=0;i>0;time++)
	{
		if(i%num){num_1++;all[time]=1;i-=(num/2);}
		else all[time]=0;
		num*=2;
	}
	int point=time;//二进制的位数
	//input finished;
	int goal;
	if(k<num_1||k>n)printf("NO\n");
	

代码如上,可以看到是这样获取的;
然后就是做法,得到了19变成10011这个数组,我们怎么做下一步?
假设:k为4;

10011如果变成02011会不会等于原来?显然相等,2个8和1个16是相等的,如果需要k个数,但是我只有num_1个1,如何表示呢,只能从高位到低位一直化,相当于什么?大面额的钱给他敞开了来花;上代码:
完整代码:

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <string>
#include <climits>
#include <queue>
#include <stack>
#include <map>
//鬼畜头文件
using namespace std;
#define INF 0x3f3f3f3f
#define ULL unsigned long long
#define LL long long
//鬼畜define
int n,k;
int all[40];
int main()
{
	scanf("%d %d",&n,&k);
	int i=n;
	int num=2;
	int time;
	int num_1=0;
	for(time=0;i>0;time++)
	{
		if(i%num){num_1++;all[time]=1;i-=(num/2);}
		else all[time]=0;
		num*=2;
	}
	int point=time;//二进制的位数
	//input finished;
	int goal;
	if(k<num_1||k>n)printf("NO\n");
	else
	{
		printf("YES\n");
		for(int time1=point-1;time1>=0;time1--)
		{
			int P=k-num_1;
			if(P==0){break;}
			if(all[time1]<=P)
			{
				num_1+=all[time1];
				all[time1-1]+=all[time1]*2;
				all[time1]=0;
				goal=time1;
			}
			else
			{
				num_1+=P;
				all[time1-1]+=P*2;
				all[time1]-=P;
				goal=time1;
			}
		}
		int num=1;
		for(int time=0;time<=goal;time++)
		{
			for(int time2=0;time2<all[time];time2++)
			{
				printf("%d ",num);
			}
			num*=2;
		}
		printf("\n");
	}
 
 
}

本文链接http://element-ui.cn/news/show-43702.aspx