本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2022-03-21 22:48:01

题目大意：

Alice 初始有一个蛋糕，之后将会进行 $n-1$ 次操作。她每次都会选一块蛋糕，设这块蛋糕的大小为 $w$，那么她就将这块蛋糕切成两块大小分别为 $\lfloor \frac{w}{2}\rfloor,\lceil \frac{w}{2} \rceil$ 的蛋糕。给定一个切好的蛋糕序列 $a$，$a_i$ 代表第 $i$ 个蛋糕的重量。问有没有一个初始的蛋糕，使得经过一定的操作可以得到这个蛋糕序列。

题目分析：

必须要知道的：$w = \lfloor \frac{w}{2}\rfloor + \lceil \frac{w}{2} \rceil$
显然，初始的那个蛋糕的重量一定是现在已有的蛋糕重量的总和，记为 $sum$。
可以使用 dfs 来求解。dfs 定义如下：

bool dfs(long long x)

它的参数的意思就是当前切到的蛋糕的大小，首先判断当前蛋糕大小 $x$ 是否出现在给定的蛋糕序列中，如果确实出现，那么返回 1 即可，代表没问题。
然后，判断 $x$ 是否小于等于 $1$，如果是，那么代表无法继续往下分，返回 0，代表不行。
下一步，就是分别 dfs 由当前蛋糕切成的两块蛋糕即可，也就是（$sum2$ 是 $x$ 除以 $2$ 下取整）：

return dfs(sum2+(x&1))&&dfs(sum2);

其实 dfs 的本质就是模拟切的过程，一旦某一个蛋糕不能往下切而且对应不上给定的切完的蛋糕序列，那么给定的序列一定是错的。

注意：

最后的返回部分，要先判断 dfs(sum2+(x&1)) 这个部分的返回值是否为 0，如果是，那么不用执行 dfs(sum2) 这一部分了，不然复杂度爆炸。
当然，写成这样：

return dfs(sum2+(x&1))&&dfs(sum2);

也是可以的，因为 && 运算符的特性，如果前面的返回 0 就不会执行后面的了。
此处感谢 @VinstaG173 大佬。

AC 代码：

#include <bits\/stdc++.h>\/\/
using namespace std;
#define int long long
const int maxn=2e5+5;
int a[maxn];
int t;
int n;
int sum;
map<int,int> im;
bool dfs(int x)
{
    if(im[x])
    {
        im[x]--;
        return 1;
    }
    if(x==1)return 0;
    int sum2=x>>1;
     return dfs(sum2+(x&1))&&dfs(sum2);
}
signed main()
{
    scanf("%lld",&t);
    while(t--)
    {
        sum=0;
        scanf("%lld",&n);
        for(int i=1;i<=n;i++)
        {
            scanf("%lld",&a[i]);
            sum+=a[i];
            im[a[i]]++;
        }
        if(dfs(sum))printf("YES\n");
        else printf("NO\n");
        for(int i=1;i<=n;i++)
        {
            im[a[i]]=0;
        }
    }
    return 0;
}