一、本周周赛总结

• 这场可惜了。
• T1 模拟。
• T2 模拟。
• T3 倒序计算。
• T4 同时限制上下界的数位DP。
  

6462. 最小化字符串长度

6462. 最小化字符串长度

1. 题目描述

2. 思路分析

题意仔细想一下就会发现，其实会将每个字符仅留1个。

3. 代码实现

class Solution:def minimizedStringLength(self, s: str) -> int:return  len(set(s))

6424. 半有序排列

6424. 半有序排列

1. 题目描述

2. 思路分析

• 由于只能相邻交换来移动，因此每次只能移动1步。
• 那么分别找到1和n的位置，计算他们移动距离。
  • 额外的，若1在n的右边，移动路径交叉，那么可以1向左时，n会免费向右一下，因此答案-1。

3. 代码实现

class Solution:def semiOrderedPermutation(self, a: List[int]) -> int:n = len(a)x,y = a.index(1),a.index(n)return x + n-y-1-(x>y)

6472. 查询后矩阵的和

6472. 查询后矩阵的和

1. 题目描述

2. 思路分析

你就记住，最小化最大值=二分、覆盖求整体=逆序

• 逆序处理后，每次格子的贡献是确定的，只需要记录每次操作有多少个格子被修改即可。
• 那么用哈希表储存已被修改的行/列，若这行/列已被改过，那这次操作可以跳过。
  • 否则记录操作这行时，有多少个空位。即 n - len(ys)。

3. 代码实现

class Solution:def matrixSumQueries(self, n: int, queries: List[List[int]]) -> int:ans = 0xs = set()ys = set()for t,i,val in queries[::-1]:          if t == 0:if i not in xs:ans += val * (n-len(ys))xs.add(i)                 else:if i not in ys:ans += val *(n-len(xs))ys.add(i)return ans

6396. 统计整数数目

6396. 统计整数数目

1. 题目描述

2. 思路分析

• 套数位DP板子即可，这题同时限制了上下界，那么不用考虑前边填没填数的事（省去is_num参数）。
• 除了上下界限制，同时传一个s作为数字求和进去。当i遍历到n时，判断方案是否合法，返回1/0。
• 另外中途s已经超过上限的话可以提前退出。

---

• 参见[python刷题模板] 数位DP
• 加餐，同时限制上下界的数位dp1742. 盒子中小球的最大数量

3. 代码实现

MOD = 10**9 + 7
class Solution:def count(self, num1: str, num2: str, min_sum: int, max_sum: int) -> int:m,n = len(num1),len(num2)num1 = '0'*(n-m) + num1@cachedef f(i,s,up_limit,down_limit):if i == n:if   min_sum<=s<=max_sum:return 1else:return 0if s > max_sum:return 0up = int(num2[i]) if up_limit else 9 down = int(num1[i]) if down_limit else 0 ans = 0for j in range(down,up+1):ans += f(i+1,s+j,up_limit and j==up,down_limit and j == down)ans %= MOD return ans return f(0,0,True,True)                       

参考链接