codeforce 457DIV2 B题

题意：
题目给出两个整数n,k,（n<=10^18,k<=10^5),求一个含有k个整数的序列，要求以2为底，以序列内数字为幂的和为n，其中序列内最大的数最小，若有多个序列满足条件，输出字典序最大的一个。

样例：input :23 5 output:Yes 3 3 2 1 0 ,其中2^3+2^3+2^2+2^1+2^0=23=n

分析

两个点：1：2^n=2*2^n-1,也就是说答案序列中任何一个数x都可以变为两个x-1
2: 结合二进制化十进制的方法，可以得到用2的幂次方表示的n

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 #include <iostream>

 #include <map>

 using namespace std;

 long long n;

 int k;

 map<int,int>b;

 int main(){

     cin>>n>>k;

     int m=;

     while(n){

         b[m]=n&;

         n/=;

         if(b[m++])k--;

     }

     if(k<){

         printf("No");

         return ;

     }

     m--;

     int i;

     for(i=m;;i--){//使最大值最小

         if(b[i]>k)break;

         b[i-]+=*b[i];

         k-=b[i];

         b[i]=;

     }

     int j;

     for(j=min(,i);j<=i;j++)if(b[j])break;

     for(;;j--){

         if(!k)break;

         if(b[j]){

         b[j]--;

         b[j-]+=;

         k--;}

     }

     printf("Yes\n");

     for(int ll=m;ll>=j;ll--)

         for(int l=;l<=b[ll];l++)printf("%d ",ll);

 return ;

 }

巴特西

codeforce 457DIV2 B题

最新文章

热门文章