本篇博文对 2020 年 9 月 12 号的乐扣杯个人竞赛进行题解。

1. 速算机器人

题目：https://leetcode-cn.com/problems/nGK0Fy/

白给题

class Solution:
    def calculate(self, s: str) -> int:
        x, y = 1, 0
        for ch in s:
            if ch == 'A':
                x = 2 * x + y
            elif ch == 'B':
                y = 2 * y + x
        return x + y

2. 早餐组合

题目：https://leetcode-cn.com/problems/2vYnGI/

先按照价格排序，然后组合即可。复杂度 $O(n \lg n)$。

import bisect

class Solution:
    def breakfastNumber(self, staple: List[int], drinks: List[int], x: int) -> int:
        staple.sort()
        drinks.sort()
        #
        count = 0
        for i, money in enumerate(staple):
            if money >= x:
                break
            # find out how much drinks can he has
            available = bisect.bisect_right(drinks, x - money)
            count = (count + available) % 1000000007

        return count

这里由于存在排序，所以后面我直接用二分查找了，否则可以双指针进一步减少复杂度。

另外考虑到价格的分布范围，其实可以用桶排序达到 $O(\max(price) + \max(count))$ 复杂度。

3. 秋叶收藏集

题目：https://leetcode-cn.com/problems/UlBDOe/

思路

首先用 $0$ 代表红叶，$1$ 代表黄叶，我们需要将数组变为 $00000111100000$ 形式。

定义 $dp[i][state]$ 为，当计算到下标为 $i$ 、状态为 $state$ 的时候所需要的最小步数。定义状态： $$state=\left\{ \begin{aligned} 0, & 0\cdots \text{形式}\\ 1, & 0\cdots 1\cdots \text{形式}\\ 2, & 0\cdots 1\cdots 0\cdots \text{形式}\\ \end{aligned} \right.$$ 可以写出转移方程：

state \ num	0	1
0	$dp[i-1][0]$	$dp[i-1][0]+1$
1	$\min(dp[i-1][0],dp[i-1][1])+1$	$\min(dp[i-1][0],dp[i-1][1])$
2	$\min(dp[i-1][1],dp[i-1][2])$	$\min(dp[i-1][1],dp[i-1][2])+1$

需要注意边界条件。

class Solution:
    def minimumOperations(self, leaves: str) -> int:
        inf = float('inf')
        dp = [inf, inf, inf]

        for i, ch in enumerate(leaves):
            if ch == 'r':
                dp = [dp[0], min(dp[0], dp[1]) + 1, min(dp[1], dp[2])]
                if i == 0:
                    dp[0] = 0
            else:
                dp = [dp[0] + 1, min(dp[0], dp[1]), min(dp[1], dp[2]) + 1]
                if i == 0:
                    dp[0] = 1

        return dp[2]

这里 Python 耗时较多（800ms），Rust 同样算法需要 8ms 左右。

4. 快速公交

题目：https://leetcode-cn.com/problems/meChtZ/

这道题需要用从顶到底的递归算法。

use std::collections::HashMap;

struct CostInfo {
    pub inc: i64,
    pub dec: i64,
    pub jump: Vec<i32>,
    pub cost: Vec<i32>,
}

impl Solution {
    fn cost_to(target: i32, memo: &mut HashMap<i32, i64>, costinfo: &CostInfo) -> i64 {
        if target <= 0 {
            return 0;
        }
        if memo.contains_key(&target) {
            return memo[&target];
        }
        let mut cost: i64 = target as i64 * costinfo.inc;
        for (&times, &jump_cost) in costinfo.jump.iter().zip(costinfo.cost.iter()) {
            // 跳到 target 之前，再 inc
            cost = cost.min(
                Self::cost_to(target / times, memo, costinfo)
                    + jump_cost as i64
                    + (target % times) as i64 * costinfo.inc,
            );
            // 跳到 target 之后，再 dec
            if target > 1 && target % times > 0 {
                cost = cost.min(
                    Self::cost_to(target / times + 1, memo, costinfo)
                        + jump_cost as i64
                        + (times - target % times) as i64 * costinfo.dec,
                )
            }
        }
        memo.insert(target, cost);
        cost
    }

    #[allow(unused)]
    pub fn bus_rapid_transit(
        target: i32,
        inc: i32,
        dec: i32,
        jump: Vec<i32>,
        cost: Vec<i32>,
    ) -> i32 {
        let mut memo = HashMap::new();
        let costinfo = CostInfo {
            inc: inc as i64,
            dec: dec as i64,
            jump,
            cost,
        };
        (Self::cost_to(target, &mut memo, &costinfo) % 1_000_000_007) as i32
    }
}

复杂度分析：

本题复杂度分析比较困难。

如果不做记忆化递归，复杂度为：主函数调用了一次 cost_to(target)，每一次 cost_to(target) 的时间复杂度为 $T(n) = m \cdot T(n/2) + O(m)$ （假设全部 $jump$ 都是 $2$，$m$ 是公交数量）

根据公式，我们可以得到 $$T(n)=\Theta\left(n ^ {\log_2{m}}\right)$$ 对于本道题的数据，$m \le 10$，于是 $T(n) \le O(n^{\log_2{10}})=O(n^{3.01})$。

做了记忆化递归之后，显然 $T(n) \le O(n) $，综合有： $$T(n)=\min(O(n),O(n^{\log_{j}{m}}))$$ 其中，$j$ 是最小的 $jump$ 数量，$m$ 是公交数量。

5. 追逐游戏

题目：https://leetcode-cn.com/problems/Za25hA/

这道题我还剩下一部分没想出来，先说一下现在的思路。

由于这是一个连通图而且有 $n$ 个点，$n$ 条边，显然就是一个树+一条额外的边构成了一个环。如果只是简单的树，逃跑者一定会输，因此需要逃到环上。只要逃跑者在被捉住之前逃跑到环上，就可以永远不被追上。

算法大致步骤：

1. 类似拓扑排序的方法，找到所有环上的点并加入一个哈希集合中。

2. 利用宽度优先搜索，搜索逃跑者和捕捉者离环上最近的一个点和其距离，记为 $p_a, l_a$ （捕捉者）和 $p_b, l_b$ （逃跑者）。

3. 利用宽度优先搜索，找到 $p_a$ 和 $p_b$ 之间最短的距离，记为 $dist_{ab}$。

   ​ 3.1 如果 $l_b \ge dist_ab + l_a$，那么捕捉者一定会抓到逃跑者。否则逃跑者可以逃走。

4. 计算如果逃不走时的最长逃跑时间。