題目鏈接：點(diǎn)擊查看

題目大意：給出n和k，問能否將n分解成k個(gè)二的冪次之和，可以重復(fù)

題目分析：首先我們需要知道二的冪次是1,2,4,8等等之類二的n次方這樣的類型，我們很容易知道不能分解的情況，一種情況是n轉(zhuǎn)換成二進(jìn)制之后，出現(xiàn)的1的個(gè)數(shù)比k多，那么肯定是沒法用k個(gè)數(shù)分解的，還有一種情況就是k大于n，因?yàn)樽顗那闆r也是n分解為n個(gè)1，再然后就沒辦法分解了，所以當(dāng)k大于n的時(shí)候也可以直接判斷了

剩下的就是如何分解，一開始我是不太會(huì)操作的，總感覺自己實(shí)現(xiàn)會(huì)超級(jí)麻煩，于是上網(wǎng)搜了一下，發(fā)現(xiàn)有個(gè)大佬用的mutilset，也就是用了他內(nèi)部自動(dòng)排序的功能，等等。。內(nèi)部自動(dòng)排序？這給我提供了思路，于是我就用優(yōu)先隊(duì)列簡簡單單的實(shí)現(xiàn)了。。因?yàn)樘肆瞬粫?huì)用mutilset

具體是怎么實(shí)現(xiàn)的呢？我們讓優(yōu)先隊(duì)列默認(rèn)給int排序，就是從大到小排的，如果當(dāng)前的二的冪次個(gè)數(shù)不足k個(gè)，我們就取出最大的那個(gè)數(shù)，將其先出隊(duì)，除以二后加入兩遍隊(duì)列即可

很簡單的實(shí)現(xiàn)，不多解釋了，上代碼：

#include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cstring> #include<algorithm> #include<stack> #include<queue> #include<map> #include<sstream> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=110;int decode(int n) {int cnt=0;while(n){if(n&1)cnt++;n>>=1;}return cnt; }int main() { // freopen("input.txt","r",stdin);int n,k;while(scanf("%d%d",&n,&k)!=EOF){int num=decode(n);if(k<num||k>n){printf("NO\n");continue;}else{printf("YES\n");}priority_queue<int>q;int cnt=0;while(n){if(n&1)q.push((1<<cnt));n>>=1;cnt++;}while(q.size()<k){if(q.top()==1)break;int temp=q.top();q.pop();q.push(temp/2);q.push(temp/2);}while(!q.empty()){printf("%d ",q.top());q.pop();}printf("\n");}return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的CodeForces - 1095C Powers Of Two(思维)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。