題目

P7071 [CSP-J2020] 優秀的拆分 - 洛谷 https://www.luogu.com.cn/problem/P7071

代碼

#include <bits/stdc++.h>
using namespace std;
const int N=1e7+1;
int d;
vector<int> v;
bool k[N];
bool fen(int x){if(x==0)return 1;//能拆分完 for(int i=x;i>x/2;i--){//從大到小嘗試拆分,其實該區間只有一個數是2的冪//因為是2的冪，要么是x,要么就大于x/2。//折半，每次只有1個，時間復雜度O(logN) if(k[i]){//該加數得是2的冪 v.push_back(i);//放進容器 if(fen(x-i))return 1;//繼續遞歸判斷是否能拆分完else v.pop_back();//否則取消該加數}	}return 0;//不能拆分完 
}
int main(){//freopen("data.cpp","r",stdin);for(int i=2;i<=N;i*=2)k[i]=1;//得到1到10^7間所有的2的冪 cin>>d;if(fen(d))for(int i=0;i<v.size();i++)cout<<v[i]<<" ";//能拆分，輸出所有數 else cout<<"-1";return 0;
}

總結

1. N=10⁷數據量大，時間復雜度起碼得O(N)
2. 用bool k[N]記住哪些數是2的冪有效提高效率。
3. 只想著多分支遞歸拆分for(int i=x;i>x/2;i–)，沒想到這個區間只可能有一個數是2的冪。如果x是，則不包括x/2。這樣每層折半，時間復雜度就是O(logN)。
4. if(fen(i))如果最后能拆分到0就ok。