Codeforces 1095C. Powers Of Two——————multiset

素颜马尾好姑娘i 2022-03-31 06:48 229阅读 0赞

# [C. Powers Of Two][] #

A positive integer x is called a power of two if it can be represented as  x = 2 y x=2^y 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≤1e9, 1≤k≤2⋅1e5).

## 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 b 1 , b 2 , … , b k \\ b\_1,b\_2,…,b\_k b1,b2,…,bk such that each of bi is a power of two, and  ∑ i = 1 k b i = n ∑\_\{i=1\}^\{k\}b\_i=n i=1∑kbi=n. If there are multiple answers, you may print any of them.

### Examples ###

input  
9 4  
output  
YES  
1 2 2 4

input  
8 1  
output  
YES  
8

input  
5 1  
output  
NO

input  
3 7  
output  
NO

--------------------

题目就是说，给你n和k，让你用k个 2 n , 0 ≤ n ≤ 31 \\ 2^n\\ ,0\\le n \\le 31 2n,0≤n≤31，使得 ∑ i = 1 k b i = n ∑\_\{i=1\}^\{k\}b\_i=n ∑i=1kbi=n,根据样例可以知道， b i b\_i bi可以使重复的。  
我们可以知道，对于任何一个正整数，都可以将其写成二进制的加法形式。比如  
 9 = ( 1001 ) 2 = 2 3 + 2 1 = 8 + 1 = 9 9=(1001)\_2 = 2^3+2^1 =8+1=9 9=(1001)2=23\+21=8\+1=9，  
此时k = 2，但是我们可以将 2 3 2^3 23分解为 2 2 + 2 2 2^2+2^2 22\+22  
于是k = 3，此时 9 = 2 2 + 2 2 + 2 0 9=2^2+2^2+2^0 9=22\+22\+20，在将大的分解  
于是k = 4，此时 9 = 2 2 + 2 1 + 2 1 + 2 0 9 = 2^2+2^1+2^1+2^0 9=22\+21\+21\+20,符合题意，输出

&ThickSpace; m u l t i s e t &ThickSpace; \\;multiset\\; multiset是一种某个数可以重复出现的集合，它通常以平衡二叉树完成.  
![在这里插入图片描述][3801213fb80e7bec26a434f7242eb9389b506bad.jpg]

#include<bits/stdc++.h>
    // #define SUBMIT
    using namespace std;
    typedef long long ll;
    int main()
    {
        
        #ifdef SUBMIT
            freopen("in.txt","r",stdin);
            freopen("out.txt","w",stdout);
            ll _begin_time = clock();
        #endif
    
        int n,k;
        multiset<int> s;
        cin>>n>>k;
        int m = n;
        for(int i=0;m;m>>=1,i++)    if(m&1) s.insert(1<<i);
        // for(multiset<int>::iterator it=s.begin();it!=s.end();++it)
        //     cout<<*it<<" ";
        // cout<<endl;
        if(n<k||s.size()>k)  cout<<"NO"<<endl;
        else
        {
        
            while(s.size()<k)
            {
        
                int a = *(--s.end()); s.erase(--s.end());
                if(a==1)    break;
                s.insert(a/2);
                s.insert(a/2);
            }
            cout<<"YES"<<endl;
            while(s.size())
            {
        
                cout<<*s.begin()<<" ";
                s.erase(s.begin());
            }
            cout<<endl;
        }
        #ifdef SUBMIT
            ll _end_time = clock();
            printf("Time: %I64d ms\n",_end_time - _begin_time);
        #endif
        return 0;
    }

[C. Powers Of Two]: https://codeforc.es/problemset/problem/1095/C
[3801213fb80e7bec26a434f7242eb9389b506bad.jpg]: https://gss2.bdstatic.com/9fo3dSag_xI4khGkpoWK1HF6hhy/baike/c0=baike80,5,5,80,26/sign=f997b13a8c01a18be4e61a1dff466c6d/3801213fb80e7bec26a434f7242eb9389b506bad.jpg