题意
有一些蛋糕，最开始只有一块。每次可以选择质量为 \(x(x\ge2)\) 的一块，将其切成 \(\left\lfloor\frac x2\right\rfloor\) 和 \(\left\lceil\frac x2\right\rceil\) 两块。现在给定切 \(n-1\) 次后的结果，判断能否通过最开始的一块切出来。
思路
容易发现，每切一次，总质量都不会改变。因此，可以一开始直接确定蛋糕初始质量 \(s=\sum_{i=1}^na_i\)。
将 \(a\) 中的每个元素的出现次数存进一个 map 里。对于任意质量 \(sum\) 进行以下分类讨论：
- 如果 \(sum\) 在
map里，则将其出现次数 \(-1\)，返回真。 - 如果 \(sum\) 不在
map里且 \(sum=1\)，由于不能再切了，即不可能再生成map里存在的元素，因此返回假。 - 如果 \(sum\) 不在
map里且 \(sum\ge2\)，则将其切开后分别递归处理，返回两次递归结果的逻辑与。
但这样裸的 DFS 显然会 TLE，因此还要另开一个全局变量 \(m\)，记录现在已经切出来了多少块，当 \(m>n\) 时，直接返回假。
此外数据范围 \(a_i\le1e9,n\le2e5\)，加起来肯定会爆 int，所以要开 long long。
代码
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
map<ll,int>mp;
int n,m;
inline void div(ll x,ll &a,ll &b){
if(x&1)a=x/2,b=a+1;
else a=b=x/2;
}
bool dfs(ll sum){
if(mp[sum])return 1;
else if(sum==1)return 0;
ll x,y;div(sum,x,y);m++;
if(m>n)return 0;
bool ans=1;
if(mp[x])mp[x]--;
else ans&=dfs(x);
if(mp[y])mp[y]--;
else ans&=dfs(y);
return ans;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
//freopen("out","w",stdout);
int t;cin>>t;
while(t--){
cin>>n;ll sum=0;
for(int i=1;i<=n;i++){int x;cin>>x;mp[x]++;sum+=x;}
m=1;
cout<<(dfs(sum)?"Yes\n":"No\n");
mp.clear();
}
return 0;
}
时间复杂度：显然由于有 \(m\) 的存在，递归的复杂度一定是 \(O(n)\)，外加 map 的一个 \(\log\)，总复杂度 \(O(n\log n)\)。