CF1654C题解

__vector__ · 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;
}