一、本周周赛总结

• 国庆补班没打，午休时VP了一下，打的也不好。
• T4虽然是套路DP，但卡了半天，DP还是短板啊。

二、 [Easy] 6201. 找出前缀异或的原始数组

链接: 6201. 找出前缀异或的原始数组

1. 题目描述

2. 思路分析

• 给出前缀和找原数组，那么求差分数组即可。
• python3.10之后可以pairwise一行搞定，VP时没想那么多。

3. 代码实现

class Solution:def findArray(self, pref: List[int]) -> List[int]:n = len(pref)arr = [pref[0]]*nfor i in range(1,n):arr[i] = pref[i]^pref[i-1]return arr

三、[Easy] 6200. 处理用时最长的那个任务的员工

链接: 6200. 处理用时最长的那个任务的员工

1. 题目描述

2. 思路分析

• 题面是真滴长！
• 还读错一次题，幸好case没过。
• 实际是看最长的那个任务谁干的，pairwise即可。

3. 代码实现

class Solution:def hardestWorker(self, n: int, logs: List[List[int]]) -> int:        s = 0mx = -1ans = inffor i,lv in logs:t= lv - sif t > mx:ans = imx = tif t == mx:ans = min(ans,i)s = lvreturn ans

四、[Medium] 6202. 使用机器人打印字典序最小的字符串

链接: 6202. 使用机器人打印字典序最小的字符串

1. 题目描述

2. 思路分析

• 本题是经典贪心：求字典序最小的出栈序列。
• 用贪心栈解决。
• 顺序遍历原数据，对每个字符压栈。
• 考虑栈顶字符c在后续的情况，设后续串中最小字符是m，那么有两种情况：
• 1. 如果c>m,那么显然优先出m才是最优解。这样的话继续向后遍历到m出m，途径的字符全部压栈即可。
• 2. 如果c<=m,那么可以直接出c，因为后续不会有更优解。
• 以上对栈顶的操作应该while做。

---

• 如何判断后续元素的最小值呢。
• 正常操作是DP预处理每个位置后续的最小值,倒序dp,f[i] = min(s[i],f[i+1]) ,初始f[n] = 'z’即可。
• 这样f[i]代表s[i:]中的最小值，求第i个位置之后的最小值就是f[i+1].
• 这题由于值域比较小26，VP时也没多想，直接用Counter+双指针做了。
• Counter的好处是省一点内存，坏处是比较麻烦，因为要字符转下标；而且双指针比较烧脑。

3. 代码实现

dp预处理

class Solution:def robotWithString(self, s: str) -> str:n = len(s)f = ['z']*(n+1)  # 每个字符后边最小的字符是谁for i in range(n-1,-1,-1):f[i]  = min(s[i],f[i+1])ans = []      st = []for i,c in enumerate(s):st.append(c)while st and st[-1] <= f[i+1]:ans.append(st.pop())ans.extend(st[::-1])return ''.join(ans)

counter预处理

class Solution:def robotWithString(self, s: str) -> str:cnt = [0]*26for c in s:cnt[ord(c)-ord('a')] += 1ans = []j = 0st = []for c in s:while j < 26 and cnt[j]==0:j+=1while st and ord(st[-1]) <= j+ord('a'):ans.append(st.pop())if ord(c) == j + ord('a'):ans.append(c)else:st.append(c)cnt[ord(c)-ord('a')] -= 1j = 0ans.extend(st[::-1])return ''.join(ans)

五、[Hard] 6203. 矩阵中和能被 K 整除的路径

链接: 6203. 矩阵中和能被 K 整除的路径

1. 题目描述

2. 思路分析

• 压轴了一道套路DP，在事先读过题面的情况下，还是卡了20min，感觉自己真的蠢。
• 读错一次题，幸好case没过。。题目要求了起点终点，因此路径数直接转移即可，没有中途点作为终点起点的情况。
• 看到m*n<=5e4本来觉得记忆化搜索过不了的，于是还是写了代码较多的DP，没想到力扣对py还是很友好，加个cache_clear就能过。下次写记忆化建议无脑加clear（或看看数据量）。
• 这里提一嘴，由于py的默认栈深限制是1000，对于这题显然过不了，力扣应该是修改了栈深参数，我通过print(sys.getrecursionlimit())在本题验证了一下，结果是550000。
• 在别的平台上，如果手动开到这么大，应该会爆MLE，力扣400兆左右的内存是允许的。。但无脑cache显然也是MLE了，在lccn上显示的是超时实际是个bug，同样的代码在lcus上显示的是MLE。

---

• 回到这题，每个位置显然只能从左或者上转移而来，这题要对k整除，也就是对k取模是0，那么如果终点是x,显然转移来的位置（左和上）需要的当前状态是(k-x)%x。
• 因此我们的状态应该占个维度，即当前和对k取模都能是多少，实际本题路径坐标已经有两维了，因此总共是三维。
• 转移：f[i][j][v] = f[i-1][j][(v-grid[i][j])%k) +f[i][j-1][(v-grid[i][j])%k)
• 初始：f[0][0][grid[0][0]%k] = 1,其他是0
• ans:f[m-1][n-1][0]

3. 代码实现

记忆化搜索+cache_clear

class Solution:def numberOfPaths(self, grid: List[List[int]], k: int) -> int:MOD = 10**9+7m,n = len(grid),len(grid[0])@cachedef f(i,j,mod):if i == j == 0:return int(grid[0][0]%k == mod%k)ans = 0if i:ans += f(i-1,j,(mod-grid[i][j])%k)if j :ans += f(i,j-1,(mod-grid[i][j])%k)return ans%MODans = f(m-1,n-1,k)f.cache_clear()# print(sys.getrecursionlimit())return ans

滚动优化DP

class Solution:def numberOfPaths(self, grid: List[List[int]], k: int) -> int:MOD = 10**9+7m,n = len(grid),len(grid[0])f = [[0]*k for _ in range(n)] f[0][grid[0][0]%k] = 1for i in range(m):g = ff = [[0]*k for _ in range(n)] for j in range(n):if i == j == 0:f[0][grid[0][0]%k]=1continuefor x in range(k):if i:f[j][x] += g[j][(x-grid[i][j])%k]if j:f[j][x] += f[j-1][(x-grid[i][j])%k]f[j][x]%=MOD                                   return f[-1][0]%MOD            

朴素DP

class Solution:def numberOfPaths(self, grid: List[List[int]], k: int) -> int:MOD = 10**9+7m,n = len(grid),len(grid[0])f = [[[0]*k for _ in range(n)] for _ in range(m)]f[0][0][grid[0][0]%k] = 1for i in range(m):for j in range(n):if i == j == 0:continuefor x in range(k):if 0<=i-1<m and 0<=j<n:f[i][j][x] += f[i-1][j][(x-grid[i][j])%k]if 0<=i<m and 0<=j-1<n:f[i][j][x] += f[i][j-1][(x-grid[i][j])%k]f[i][j][x]%=MODreturn f[-1][-1][0]%MOD