本文主要是介绍【递归+二叉树思想+搜索】 Alice and the Cake题解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
Alice and the Cake题解
AC记录：记录-洛谷
题面翻译（大概就是题目大意）
执行恰好 n − 1 n-1 n−1 次操作，每次操作可以选择当前所有蛋糕中满足其重量 w ⩾ 2 w\geqslant 2 w⩾2 的一块，然后将其分为质量分别为 ⌊ w 2 ⌋ \lfloor\dfrac w2\rfloor ⌊2w⌋ 和 ⌈ w 2 ⌉ \lceil\dfrac w2\rceil ⌈2w⌉ 的两块。
现在，给定执行完所有操作后 n n n 块蛋糕的重量是 a 1 , a 2 ⋯ , a n a_1,a_2\cdots,a_n a1,a2⋯,an，请判断是否存在一个初始蛋糕重量和操作序列使得最终能得到给定的 n n n 块蛋糕。如果能，输出 YES，否则输出 NO。
数据范围：
- t t t 组数据， 1 ⩽ t ⩽ 1 0 4 1\leqslant t\leqslant 10^4 1⩽t⩽104。
- 1 ⩽ n , ∑ n ⩽ 2 × 1 0 5 1\leqslant n,\sum n\leqslant 2\times 10^5 1⩽n,∑n⩽2×105。
- 1 ⩽ a i ⩽ 1 0 9 1\leqslant a_i\leqslant 10^9 1⩽ai⩽109。
Translated by Eason_AC
大致思路
分别递归+搜索 查看左半边蛋糕（左子树）和右半边蛋糕（右子树）是否符合规则。（二叉树+搜索+递归）
小小的代码
solve函数：
void solve() {p.clear();long long int n;cin >> n;long long int x;long long int sum = 0;for(int i = 1; i <= n; i++) {cin >> x;p[x]++;sum += x;}if(dfs(sum))cout << "YES" << endl;elsecout << "NO" << endl;
}
递归
int dfs(long long int s) {if(!s)return 0;if(mp[s]) {mp[s]--;return 1;}return dfs(s / 2) && dfs(s - (s >> 1));
}
寂寞的人唱伤心的歌~
这篇关于【递归+二叉树思想+搜索】 Alice and the Cake题解的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
