Leetcode Weekly Contest 188

A. Build an Array With Stack Operations

随时保持栈内元素与最终结果的前辍一致即可。

给定数组arr，求有多少个i, j, k，满足xorsum(arr[i...j-1]) == xorsum(arr[j...k])。

首先，如果xorsum(arr[i....k]) == 0，则对于任意j，必有xorsum(arr[i...j-1]) == xorsum(arr[j...k])。

所以只需要判断有多少xorsum(arr[i...k]) == 0即可。

如果一棵子树有苹果，那么我们一定要访问这棵子树的根，并且会从子树的根返回整棵树的根。

所以我们计算有X个子树有苹果，最终的结果就是X - 1。

方形批萨饼可以横着切或者竖着切，每一刀切完之后的上半部分或者左边部分会交给客户，剩下的部分可以接着切。

问有多少种切法，可以让每一片饼都有一个苹果。

每一刀切完后，我们都可以用剩下的饼的左上角坐标标记当前的状态。所以dp[y][x]=k代表当前剩余饼的左上角坐标为(y, x)时，已经分给k个用户包含至少一个苹果的饼。