快半年没有参加 LeetCode 的每周比赛了，感觉已经跟不上节奏了哈。四题用了1个小时，错了一次罚时5分钟，然后就排到350左右了。

第一题Build an Array With Stack Operations

模拟题，用 "Push" 和 "Pop" 构建一个给定的数组。

class Solution:
    def buildArray(self, target: List[int], n: int) -> List[str]:
        ret = []
        cur = 0
        for t in target:
            ret.extend(["Push", "Pop"] * (t - cur - 1))
            ret.append("Push")
            cur = t
        return ret

第二题Count Triplets That Can Form Two Arrays of Equal XOR

给定一个数组 arr，我们定义
sum(i, j) = arr[i] ^ arr[i+1] ^ .. ^ arr[j],
其中 ^ 是位运算 xor。

我们需要找出满足 sum(i, j-1) = sum(j, k) 的三元数组 (i, j, k)。我们要求 i < j <= k。

看了一下数据范围，数组的长度最大只有300。这明显可以暴力搜。因为怕超时，我就直接用 C 写了。

int countTriplets(int* arr, int arrSize){
    int s[301];
    s[0] = 0;
    for (int i = 0; i < arrSize; i ++)
        s[i + 1] = s[i] ^ arr[i];
    int ret = 0;
    for (int i = 0; i < arrSize; i ++) {
        for (int k = i + 1; k < arrSize; k ++) {
            for (int j = i + 1; j <= k; j ++) {
                int a = s[j] ^ s[i];
                int b = s[k+1] ^ s[j];
                ret += a == b;
            }
        }
    }
    return ret;
}

第三题Minimum Time to Collect All Apples in a Tree

在一棵多叉树中的一些节点上有苹果，问从节点0出发收集所有苹果回到节点0所需的最短时间是多少？每条边耗时1个单位的时间。

一开始没有察觉到这是一个多叉树，所以没有想到好的办法。我是做了最后一题回来再提交一次后错了才发现这是多叉树。题解的想法是这样的：对于一个节点，我们递归地算出子树收集所有苹果的时间，如果子树有苹果，结果要加2，这是从节点到子树根节点一个来回的时间。

class Solution:
    def minTime(self, n: int, edges: List[List[int]], hasApple: List[bool]) -> int:

        children = [[] for _ in range(n)]
        for p, c in edges:
            children[p].append(c)

        def collect(root):
            ans = 0
            for child in children[root]:
                t = collect(child)
                ans += t
                if t or hasApple[child]:
                    ans += 2
            return ans

        return collect(0)

第四题Number of Ways of Cutting a Pizza

给定一个2维数组代表一个长方形的 pizza，值为'A'代表该位置有个苹果 (what?)，'.'代表没有。我们现在要切 k-1 刀将 pizza 分成 k 份。我们可以横着切或者竖着切。横着切之后只能切右边那块，竖着切之后只能切下面那块，要求每一块都有苹果。问一共有多少种满足条件的切法，结果 mod 10^9 + 7。

动态规划的题目。我们用 dp(i, j, k) 表示从 i 行，从 j 列开始切，需要切成 k 块的切法。

边界条件 如果 i 或者 j 超出边界，那么就直接返回0。如果 k 是1，我们只需检查剩下的 pizza 里有没有苹果即可。

转移方程 因为可以横着切或者竖着切，我们需要分别考虑这两种情况。竖着切的时候我们枚举切完之后上面那块 pizza 的最后一行序号 ic。若从第 i 到 ic 行有苹果，则

dp(i, j, k) += dp(ic+1, j, k-1)

横着切的想法也是一样的。

为了快速检测某个区域是否有苹果，我预先计算所有左上角区域的和 s。这样我们可以在 O(1) 的时间内算出一个区域的所有数字之和来判断是否有苹果。 

class Solution:
    def ways(self, pizza: List[str], k: int) -> int:
        MOD = 10 ** 9 + 7
        n, m = len(pizza), len(pizza[0])
        s = [[0] * (m + 1) for _ in range(n + 1)]
        for i, row in enumerate(pizza):
            for j, c in enumerate(row):
                s[i][j] = s[i - 1][j] + s[i][j - 1] + (c == 'A') - s[i-1][j-1]
        def get(i, j, x, y):
            return s[x][y] - s[x][j-1] - s[i-1][y] + s[i-1][j-1]

        memo = {}
        def dp(i, j, k):
            if i >= n or j >= m:
                return 0
            if k == 1:
                return 1 if get(i, j, n-1, m-1) > 0 else 0
            if (i, j, k) in memo:
                return memo[i, j, k]
            ans = 0
            for ic in range(i, n):
                if get(i, j, ic, m-1) > 0:
                    ans = (ans + dp(ic+1, j, k-1)) % MOD
            for jc in range(j, m):
                if get(i, j, n-1, jc) > 0:
                    ans = (ans + dp(i, jc+1, k-1)) % MOD
            memo[i, j, k] = ans
            return ans

        return dp(0, 0, k)
leetcode contest