写在前面：

本次题感觉总体都有ACM的味道了，个人感觉难度极高…

强烈建议自己先考虑一下，然后再看题解

题目一：

题目链接： https://leetcode-cn.com/contest/season/2020-spring/problems/qi-wang-ge-shu-tong-ji/

解题思路：

通过分析题目发现，不同分数的简历之间是不会互相影响的，所以原问题等同于n个数字全排列之后，有多少元素还在原位置

设这个随机变量为，对于，如果第i个元素还在原位，则，否则

对于每一个元素，随机排序后还在原位的概率为。由于期望的可加性，可以得到如下的式子：

由结果可知，最终与n无关，所以我们只需要计算有多少个不重复的数字就可以了

利用hash的性质，统计有多少不相同的数字，再返回hash表中key的个数

时间复杂度：O(N)

代码实现：

 class Solution:     def expectNumber(self, scores: List[int]) -> int:         return len(set(scores))

题目二：

题目链接： https://leetcode-cn.com/contest/season/2020-spring/problems/xiao-zhang-shua-ti-ji-hua/

解题思路：

二分查找

初始的left = 0, right = 所有时间之和，然后开始二分查找

每次取mid之后，mid是每一天的做题时间。然后根据mid，判断当前被分成几天完成

如果大于m天，说明需要调大mid，则更新left = mid + 1

如果小于等于m天，说明需要调小mid，则更新right = mid

关于求助功能的体现，在代码注释中有详细解释

代码实现：

 class Solution:     def minTime(self, time: List[int], m: int) -> int:         def check(mid, time, m):             # 根据当前mid天数,计算出需要的总天数             use_day = 1             # 当前序列需要使用的天数             total_time = 0             # 当前序列中的最大耗时             max_time = time[0]             for t in time[1:]:                 # 因为是可以求助的,所以可以每组中多一道题                 # 所以从1开始遍历,并且更新当前题组total_time时,排除掉耗时最高的一个                 if total_time + min(max_time, t) <= mid:                     # 更新当前题组的总耗时,加上当前值和最大值中更小的一个                     # 最终达到目的：题组中的最大耗时,使用求助功能解答                     total_time += min(max_time, t)                     max_time = max(max_time, t)                 else:                     # 排除掉最大耗时,当前题组也超过mid限制的天数了                     # 此时更新当前需要天数use_day += 1                     # 并重置题组所需天数和最高耗时                     use_day += 1                     total_time = 0                     max_time = t              return use_day <= m          # 初始化最小值为0,最大值为时间总和         left, right = 0, sum(time)         while left < right:             mid = (left + right) >> 1             if check(mid, time, m):                 # 总耗时天数 <= m，想要增大总耗时,通过调小right调小mid                 right = mid             else:                 # 总耗时天数 > m，想要减小总耗时,通过增大left增大mid                 left = mid + 1          return left

题目三：

题目链接： https://leetcode-cn.com/contest/season/2020-spring/problems/xun-bao/

解题思路：

事实上，我们的走法只有这么几种：

1. 从S走向O，取石头
2. 从O走向M，踩机关
3. 从M走向O，再次取石头
4. 从M走向T，所有机关都已经触发，走向终点

BFS：

对于所有的S、M、O和T，不论我们做什么操作（触发机关、搬运石头），互相之间的连通性是不会变化的

所以在开始的时候，对每一个特殊点都进行一次BFS，搜索当前点到其他点的最短距离，之后就不需要再去搜索了

状态压缩DP：

在最开始，我们一定是从S点开始，经过一个O点搬一块石头，再到达一个M点触发机关。所以我们先枚举S通过某个O到达每一个M的最短距离（S -> O -> M），这样我们就首先得到了按照游戏规则的S到每一个M的最短距离

接下来，按照游戏规则，我们需要从某个M出发，到达O搬运一块石头，再到达其他未出发机关的M点（M -> O -> M’），和计算S -> O -> M的逻辑相同，我们需要枚举出所有M -> O -> M’的最短距离，就得到了按照游戏规则的每一个M到达其他M的最短距离

而M到T的距离，之前在BFS的时候已经计算出来了

这样，我们就将已知条件转换为了：

1. 按照游戏规则，S到达每一个M的最短距离
2. 按照游戏规则，M到达每一个M‘的最短距离
3. 每一个M到达T的最短距离

这样就是一个经典的状压DP问题了

令dp[s][i]表示在第i个机关，总触发状态为s的最小步数（s是一个状态的bitmap），那么枚举当前没有触发的机关j，状态转移公式为：

其中为之前预处理出的所有特殊点之间的最小距离

复杂度分析：

• BFS时间复杂度，其中m为M点的数目，o为O点的数目，S为迷宫面积
• dp时间复杂度为

代码实现：

 import queue class Solution:     def bfs(self, maze):         """         以迷宫maze中的每个特殊点为中心,BFS搜索到其他所有特殊点的最近距离         Args:             maze : 原始迷宫信息         Returns:             total_dis_info : 按照special_point中的顺序,保存每个点到其余点的最近距离.如果要获取第i个点到第j个点的最近距离,可以直接使用total_dis_info[i][j]获取             tag : 保存每个类型的点,在special_point中的索引值,同时也是total_dis_info中的索引值         """         # 迷宫的高和宽         height, width = len(maze), len(maze[0])         # 特殊点位置信息         special_point = []         for i in range(height):             for j in range(width):                 if maze[i][j] in ['S', 'T', 'M', 'O']:                     special_point.append((i, j, maze[i][j]))          # 按照special_point中的顺序,保存每个点到其余点的最近距离         # 如果要获取第i个点到第j个点的最近距离,可以直接使用total_dis_info[i][j]获取         total_dis_info = []         # 保存每个类型的点,在special_point中的索引值         # 这个索引值,同时也是在total_dis_info中的索引值         tag = collections.defaultdict(list)         # 以每个特殊点为中心，开始BFS搜索其他特殊点的最短距离         for idx, (x, y, point_type) in enumerate(special_point):             q = queue.Queue()             dis = [[float('inf') for i in range(width)] for j in range(height)]             dis[x][y] = 0             q.put((x, y))             while not q.empty():                 curr_x, curr_y = q.get()                 # BFS时搜索的的方向                 # 按照数组顺序，分别为：向下、向右、向上、向左                 for x_move, y_move in [[0, 1], [1, 0], [0, -1], [-1, 0]]:                     nxt_x = curr_x + x_move                     nxt_y = curr_y + y_move                     if nxt_x < 0 or nxt_x >= height or nxt_y < 0 or nxt_y >= width:                         # 超出边界                         continue                     elif maze[nxt_x][nxt_y] == '#':                         # 不可通行                         continue                      if dis[nxt_x][nxt_y] > dis[curr_x][curr_y] + 1:                         # 如果nxt_x,nxt_y的位置之前没搜索到,当前距离应该是无穷大                         # 或者之前搜索到nxt_x,nxt_y的位置,并且距离比本次搜索的距离要大                         # 则更新nxt_x,nxt_y和原始x,y的最近距离为当前距离 + 1                         # 并将nxt_x,nxt_y加入队列，继续搜索                         dis[nxt_x][nxt_y] = dis[curr_x][curr_y] + 1                         q.put((nxt_x, nxt_y))              # 当前点到其他所有特殊点,按照保存在special_point中的顺序的最小距离             curr_dis_info = []             for i, j, _ in special_point:                 curr_dis_info.append(dis[i][j])              #加入到结果集中             total_dis_info.append(curr_dis_info)             tag[point_type].append(idx)          return total_dis_info, tag      def state_compression_dp(self, total_dis_info, tag):         """         状态压缩DP处理         Args:             total_dis_info : BFS的距离信息             tag : 每个特殊点的索引序列         Returns:             最终步数结果         """         m_num = len(tag['M'])         o_num = len(tag['O'])         s_idx = tag['S'][0]         t_idx = tag['T'][0]         dp = [[float('inf') for i in range(m_num)] for j in range(1 << m_num)]         # 处理S -> O -> M的最短距离         for i in range(m_num):             m_idx = tag['M'][i]             # s移位后,dp[s][i]表示的是每个M到自己的距离             self_idx = 1 << i             for j in range(o_num):                 o_idx = tag['O'][j]                 # 更新每个M到自己的距离,为S开始,经过每个O,到自己的最小距离                 dp[self_idx][i] = min(dp[self_idx][i], total_dis_info[s_idx][o_idx] + total_dis_info[o_idx][m_idx])          # 预处理M -> O -> M的距离         m_2_m_dis = [[float('inf') for i in range(m_num)] for j in range(m_num)]         for i in range(m_num):             m_idx1 = tag['M'][i]             for j in range(m_num):                 m_idx2 = tag['M'][j]                 for k in range(o_num):                     o_idx = tag['O'][k]                     # 获取每个M,经过O,到达其他M的最短距离                     m_2_m_dis[i][j] = min(m_2_m_dis[i][j], total_dis_info[m_idx1][o_idx] + total_dis_info[o_idx][m_idx2])          # 状态压缩DP         for s in range(1 << m_num):             for j in range(m_num):                 if s & (1 << j) == 0:                     continue                 for k in range(m_num):                     if s & (1 << k) != 0:                         continue                     ns = s | (1 << k)                     dp[ns][k] = min(dp[ns][k], dp[s][j] + m_2_m_dis[j][k])          ans = float('inf')         fs = (1 << m_num) - 1         for j in range(m_num):             m_idx = tag['M'][j]             ans = min(ans, dp[fs][j] + total_dis_info[m_idx][t_idx])          return -1 if ans == float('inf') else ans      def minimalSteps(self, maze: List[str]) -> int:         """         根据输入的迷宫，计算一共需要多少步，才能在触发所有机关后，从起点走向终点         Args:             maze : m * n的迷宫矩阵         Returns:             需要的步数         """         total_dis_info, tag = self.bfs(maze)         if 'M' not in tag:             # 如果没有机关,则直接返回起点到终点的最近距离             # 因为S和T有且只有1个,所以直接获取相应的第一个             s_idx = tag['S'][0]             t_idx = tag['T'][0]             # 如果起点无法到达终点,则返回-1; 否则返回起点到终点的最近距离total_dis_info[s_idx][t_idx]             return -1 if float('inf') == total_dis_info[s_idx][t_idx] else total_dis_info[s_idx][t_idx]          return self.state_compression_dp(total_dis_info, tag)

题目四：

题目链接： https://leetcode-cn.com/contest/season/2020-spring/problems/qie-fen-shu-zu/

题目五：

（上图：A->B->C 右转； 下图：D->E->F 左转）

题目链接： https://leetcode-cn.com/contest/season/2020-spring/problems/you-le-yuan-de-mi-gong/

题目六：

题目链接： https://leetcode-cn.com/contest/season/2020-spring/problems/you-le-yuan-de-you-lan-ji-hua/