(资料图片)

最小化字符串长度

【哈希表】根据题意，只要有重复字母就会一直操作，所以最后每种出现过的字母只会出现一次。

半有序排列

【分类讨论 + 公式】找到初始时1和n的下标idx_1和idx_n，如果idx_1q，则1和n分别移动到数组两端的过程中会相遇相当于只操作了一次就让两个数都向左向右移动了一步，操作次数要在刚才的情况上减一。

查询后矩阵的和

【倒序模拟】如果对同一行（列）反复操作，那么只有最后一次对这行（列）的操作会记入答案，所以考虑倒序处理。用两个集合vis[0]和vis[1]来记录已经被修改过的行和列。如果当前查询涉及的行或列尚未被遍历过，那么我们可以将结果累加上该行/列对应的元素个数并乘以val的值，即ans += (n - len(vis[type ^ 1])) * val，其中type ^ 1是01转换。

统计整数数目

【数位 DP】题目要求在给定范围内，位数数字之和在[min_sum,max_sum]之间的所有整数的个数。首先定义状态，用f(i,sm,is_limit)表示当前处理到第i位数字，位数数字之和为sm，是否达到上限的状态（即是否和上界num2相同）。由于题目要求在[num1,num2]区间内进行计算，所以最终结果ans=f(num2)-f(num1)+flag，其中flag用于判断num1的位数数字之和是否在[min_sum,max_sum]之间。接下来，逐个地处理num1和num2中每一位数字，并记录每一位数字对答案的影响，从而递归地求解状态f(i,sm,is_limit)。在递归求解时，需要考虑当前位数字是否已经达到上限，以及当前位数字的取值范围是否满足条件。

关键词：

(责任编辑：黄俊飞)

全球微速讯：复盘｜第348场周赛

时间：2023-06-04 19:50:53来源 : 哔哩哔哩

最小化字符串长度

推荐内容