周赛368（模拟、前后缀分解、枚举+数学、预处理+划分型DP）

后缀分解、枚举+数学、预处理+划分型DP）"/>

周赛368（模拟、前后缀分解、枚举+数学、预处理+划分型DP）

文章目录

• 周赛368
• • [100106. 元素和最小的山形三元组 I](/)
  • • 模拟
  • [100114. 元素和最小的山形三元组 II](/)
  • • 前后缀分解
  • [100097. 合法分组的最少组数](/)
  • • 枚举 + 脑经急转弯
  • [6920. 得到 K 个半回文串的最少修改次数](/)
  • • 预处理 + 划分型DP

周赛368

100106. 元素和最小的山形三元组 I

简单

给你一个下标从 0 开始的整数数组 nums 。

如果下标三元组 (i, j, k) 满足下述全部条件，则认为它是一个 山形三元组 ：

• i < j < k
• nums[i] < nums[j] 且 nums[k] < nums[j]

请你找出 nums 中 元素和最小 的山形三元组，并返回其 元素和 。如果不存在满足条件的三元组，返回 -1 。

示例 1：

输入：nums = [8,6,1,5,3]
输出：9
解释：三元组 (2, 3, 4) 是一个元素和等于 9 的山形三元组，因为： 
- 2 < 3 < 4
- nums[2] < nums[3] 且 nums[4] < nums[3]
这个三元组的元素和等于 nums[2] + nums[3] + nums[4] = 9 。可以证明不存在元素和小于 9 的山形三元组。

示例 2：

输入：nums = [5,4,8,7,10,2]
输出：13
解释：三元组 (1, 3, 5) 是一个元素和等于 13 的山形三元组，因为： 
- 1 < 3 < 5 
- nums[1] < nums[3] 且 nums[5] < nums[3]
这个三元组的元素和等于 nums[1] + nums[3] + nums[5] = 13 。可以证明不存在元素和小于 13 的山形三元组。

示例 3：

输入：nums = [6,5,4,3,4,5]
输出：-1
解释：可以证明 nums 中不存在山形三元组。

提示：

• 3 <= nums.length <= 50
• 1 <= nums[i] <= 50

模拟

class Solution {public int minimumSum(int[] nums) {int n = nums.length;int res = -1;for(int i = 0; i < n; i++){for(int j = i+1; j < n; j++){for(int k = j+1; k < n; k++){if(nums[i] < nums[j] && nums[k] < nums[j]){if(res != -1)res = Math.min(res, nums[i] + nums[j] + nums[k] );else res = nums[i] + nums[j] + nums[k];}}}}return res;}
}

100114. 元素和最小的山形三元组 II

中等

给你一个下标从 0 开始的整数数组 nums 。

如果下标三元组 (i, j, k) 满足下述全部条件，则认为它是一个 山形三元组 ：

• i < j < k
• nums[i] < nums[j] 且 nums[k] < nums[j]

请你找出 nums 中 元素和最小 的山形三元组，并返回其 元素和 。如果不存在满足条件的三元组，返回 -1 。

示例 1：

输入：nums = [8,6,1,5,3]
输出：9
解释：三元组 (2, 3, 4) 是一个元素和等于 9 的山形三元组，因为： 
- 2 < 3 < 4
- nums[2] < nums[3] 且 nums[4] < nums[3]
这个三元组的元素和等于 nums[2] + nums[3] + nums[4] = 9 。可以证明不存在元素和小于 9 的山形三元组。

示例 2：

输入：nums = [5,4,8,7,10,2]
输出：13
解释：三元组 (1, 3, 5) 是一个元素和等于 13 的山形三元组，因为： 
- 1 < 3 < 5 
- nums[1] < nums[3] 且 nums[5] < nums[3]
这个三元组的元素和等于 nums[1] + nums[3] + nums[5] = 13 。可以证明不存在元素和小于 13 的山形三元组。

示例 3：

输入：nums = [6,5,4,3,4,5]
输出：-1
解释：可以证明 nums 中不存在山形三元组。

提示：

• 3 <= nums.length <= 105
• 1 <= nums[i] <= 108

前后缀分解

class Solution {public int minimumSum(int[] nums) {int n = nums.length;int[] pre = new int[n+1];int[] suf = new int[n+1];pre[0] = Integer.MAX_VALUE;for(int i = 0; i < n; i++){pre[i+1] = Math.min(pre[i], nums[i]);}suf[n] = Integer.MAX_VALUE;for(int i = n-1; i >= 0; i--){suf[i] = Math.min(suf[i+1], nums[i]);}int res = -1;for(int i = 1; i < n-1; i++){if(nums[i] > pre[i] && nums[i] > suf[i+1]){if(res == -1) res = nums[i] + pre[i] + suf[i+1];else res = Math.min(res, nums[i] + pre[i] + suf[i+1]);}}return res;}
}

100097. 合法分组的最少组数

中等

给你一个长度为 n 下标从 0 开始的整数数组 nums 。

我们想将下标进行分组，使得 [0, n - 1] 内所有下标 i 都 恰好 被分到其中一组。

如果以下条件成立，我们说这个分组方案是合法的：

• 对于每个组 g ，同一组内所有下标在 nums 中对应的数值都相等。
• 对于任意两个组 g1 和 g2 ，两个组中 下标数量 的 差值不超过 1 。

请你返回一个整数，表示得到一个合法分组方案的 最少 组数。

示例 1：

输入：nums = [3,2,3,2,3]
输出：2
解释：一个得到 2 个分组的方案如下，中括号内的数字都是下标：
组 1 -> [0,2,4]
组 2 -> [1,3]
所有下标都只属于一个组。
组 1 中，nums[0] == nums[2] == nums[4] ，所有下标对应的数值都相等。
组 2 中，nums[1] == nums[3] ，所有下标对应的数值都相等。
组 1 中下标数目为 3 ，组 2 中下标数目为 2 。
两者之差不超过 1 。
无法得到一个小于 2 组的答案，因为如果只有 1 组，组内所有下标对应的数值都要相等。
所以答案为 2 。

示例 2：

输入：nums = [10,10,10,3,1,1]
输出：4
解释：一个得到 2 个分组的方案如下，中括号内的数字都是下标：
组 1 -> [0]
组 2 -> [1,2]
组 3 -> [3]
组 4 -> [4,5]
分组方案满足题目要求的两个条件。
无法得到一个小于 4 组的答案。
所以答案为 4 。

提示：

• 1 <= nums.length <= 105
• 1 <= nums[i] <= 109

枚举 + 脑经急转弯

/

class Solution {// 假设cnt[x] = 32,k = 10//      可以分为3个组// cnt[x] = 34,多出来的4无法加到其他三个10中// cnt[x] 可以分出多少组？ cnt[x]/(k+1)上取整// a/b上取整 = (a+b-1)/bpublic int minGroupsForValidAssignment(int[] nums) {Map<Integer, Integer> cnt = new HashMap<>();for (int x : nums) {cnt.merge(x, 1, Integer::sum);}int k = nums.length;for (var c : cnt.values()) {k = Math.min(k, c);}for (; ; k--) { // 枚举组内最少k个数字（k 或 k+1个数字）int ans = 0; // 枚举答案for (int c : cnt.values()) {if (c / k < c % k) {ans = 0;break;}ans += (c + k) / (k + 1);}if (ans > 0) {return ans;}}}
}

6920. 得到 K 个半回文串的最少修改次数

困难

给你一个字符串 s 和一个整数 k ，请你将 s 分成 k 个 子字符串 ，使得每个 子字符串 变成 半回文串 需要修改的字符数目最少。

请你返回一个整数，表示需要修改的 最少 字符数目。

注意：

• 如果一个字符串从左往右和从右往左读是一样的，那么它是一个 回文串 。
• 如果长度为 len 的字符串存在一个满足 1 <= d < len 的正整数 d ，len % d == 0 成立且所有对 d 做除法余数相同的下标对应的字符连起来得到的字符串都是 回文串 ，那么我们说这个字符串是 半回文串 。比方说 "aa" ，"aba" ，"adbgad" 和 "abab" 都是 半回文串 ，而 "a" ，"ab" 和 "abca" 不是。
• 子字符串 指的是一个字符串中一段连续的字符序列。

示例 1：

输入：s = "abcac", k = 2
输出：1
解释：我们可以将 s 分成子字符串 "ab" 和 "cac" 。子字符串 "cac" 已经是半回文串。如果我们将 "ab" 变成 "aa" ，它也会变成一个 d = 1 的半回文串。
该方案是将 s 分成 2 个子字符串的前提下，得到 2 个半回文子字符串需要的最少修改次数。所以答案为 1 。

示例 2:

输入：s = "abcdef", k = 2
输出：2
解释：我们可以将 s 分成子字符串 "abc" 和 "def" 。子字符串 "abc" 和 "def" 都需要修改一个字符得到半回文串，所以我们总共需要 2 次字符修改使所有子字符串变成半回文串。
该方案是将 s 分成 2 个子字符串的前提下，得到 2 个半回文子字符串需要的最少修改次数。所以答案为 2 。

示例 3：

输入：s = "aabbaa", k = 3
输出：0
解释：我们可以将 s 分成子字符串 "aa" ，"bb" 和 "aa" 。
字符串 "aa" 和 "bb" 都已经是半回文串了。所以答案为 0 。

提示：

• 2 <= s.length <= 200
• 1 <= k <= s.length / 2
• s 只包含小写英文字母。

预处理 + 划分型DP

/

class Solution {private static final int MX = 201;private static final List<Integer>[] divisors = new ArrayList[MX];static {// 预处理每个数的真因子，时间复杂度 O(MX*logMX)Arrays.setAll(divisors, k -> new ArrayList<>());for (int i = 1; i < MX; i++) {for (int j = i * 2; j < MX; j += i) {divisors[j].add(i);}}}int[][] cache;int[][] modify;public int minimumChanges(String s, int k) {int n = s.length();// modify[i][j] 表示 修改s[i:j+1]的成为半回文串的最少操作次数modify = new int[n-1][n];for(int left = 0; left < n-1; left++){for(int right = left + 1; right < n; right++)modify[left][right] = getModify(s.substring(left, right+1));}// 划分DPcache = new int[k][n];for(int i = 0; i < k; i++){Arrays.fill(cache[i], -1);}return dfs(k-1, n-1);}// 定义 dfs(i, j) 表示在s[:j]中还需要划分i个区间，修改最少次数。public int dfs(int i, int j){if(i == 0){return modify[0][j];}if(cache[i][j] >= 0) return cache[i][j];int res = Integer.MAX_VALUE;for(int L = i * 2; L < j; L++){// 划分区间（L，j）res = Math.min(res, dfs(i-1, L-1) + modify[L][j]);}return cache[i][j] = res;}// 使字符串s成为半回文串的最小修改次数private int getModify(String S){char[] s = S.toCharArray();int n = s.length;int res = n;for(int d : divisors[n]){int cnt = 0;for(int i0 = 0; i0 < d; i0++){ // 枚举所有起点for(int i = i0, j = n - d + i0; i < j; i += d, j -= d){if(s[i] != s[j])cnt += 1;}}res = Math.min(res, cnt);}return res;}
}