fork()==0世界线变动

2518. 好分区的数目

给你一个正整数数组 nums 和一个整数 k 。

分区 的定义是：将数组划分成两个有序的 组 ，并满足每个元素 恰好 存在于 某一个 组中。如果分区中每个组的元素和都大于等于 k ，则认为分区是一个好分区。

返回 不同 的好分区的数目。由于答案可能很大，请返回对 10^9 + 7 取余 后的结果。

如果在两个分区中，存在某个元素 nums[i] 被分在不同的组中，则认为这两个分区不同。

示例 1：

```txt

输入：nums = [1,2,3,4], k = 4

输出：6

解释：好分区的情况是 ([1,2,3], [4]), ([1,3], [2,4]), ([1,4], [2,3]), ([2,3], [1,4]), ([2,4], [1,3]) 和 ([4], [1,2,3]) 。

```

示例 2：

```txt

输入：nums = [3,3,3], k = 4

输出：0

解释：数组中不存在好分区。

```

示例 3：

```txt

输入：nums = [6,6], k = 2

输出：2

解释：可以将 nums[0] 放入第一个分区或第二个分区中。

好分区的情况是 ([6], [6]) 和 ([6], [6]) 。

```

提示：

• 1 <= nums.length, k <= 1000

• 1 <= nums[i] <= 10^9

6364. 无平方子集计数

给你一个正整数数组 nums 。

如果数组 nums 的子集中的元素乘积是一个 无平方因子数 ，则认为该子集是一个 无平方 子集。

无平方因子数 是无法被除 1 之外任何平方数整除的数字。

返回数组 nums 中 无平方 且 非空 的子集数目。因为答案可能很大，返回对 10^9 + 7 取余的结果。

nums 的 非空子集 是可以由删除 nums 中一些元素（可以不删除，但不能全部删除）得到的一个数组。如果构成两个子集时选择删除的下标不同，则认为这两个子集不同。

示例 1：

```txt

输入：nums = [3,4,4,5]

输出：3

解释：示例中有 3 个无平方子集：

• 由第 0 个元素 [3] 组成的子集。其元素的乘积是 3 ，这是一个无平方因子数。

• 由第 3 个元素 [5] 组成的子集。其元素的乘积是 5 ，这是一个无平方因子数。

• 由第 0 个和第 3 个元素 [3,5] 组成的子集。其元素的乘积是 15 ，这是一个无平方因子数。

可以证明给定数组中不存在超过 3 个无平方子集。

```

示例 2：

```txt

输入：nums = [1]

输出：1

解释：示例中有 1 个无平方子集：

• 由第 0 个元素 [1] 组成的子集。其元素的乘积是 1 ，这是一个无平方因子数。

可以证明给定数组中不存在超过 1 个无平方子集。

```

提示：

• 1 <= nums.length <= 1000

• 1 <= nums[i] <= 30

1125. 最小的必要团队

作为项目经理，你规划了一份需求的技能清单 req_skills，并打算从备选人员名单 people 中选出些人组成一个「必要团队」（ 编号为 i 的备选人员 people[i] 含有一份该备选人员掌握的技能列表）。

所谓「必要团队」，就是在这个团队中，对于所需求的技能列表 req_skills 中列出的每项技能，团队中至少有一名成员已经掌握。可以用每个人的编号来表示团队中的成员：

• 例如，团队 team = [0, 1, 3] 表示掌握技能分别为 people[0]，people[1]，和 people[3] 的备选人员。

请你返回 任一 规模最小的必要团队，团队成员用人员编号表示。你可以按 任意顺序 返回答案，题目数据保证答案存在。

示例 1：

```txt

输入：req_skills = ["java","nodejs","reactjs"], people = [["java"],["nodejs"],["nodejs","reactjs"]]

输出：[0,2]

```

示例 2：

```txt

输入：req_skills = ["algorithms","math","java","reactjs","csharp","aws"], people = [["algorithms","math","java"],["algorithms","math","reactjs"],["java","csharp","aws"],["reactjs","csharp"],["csharp","math"],["aws","java"]]

输出：[1,2]

```

提示：

• 1 <= req_skills.length <= 16

• 1 <= req_skills[i].length <= 16

• req_skills[i] 由小写英文字母组成

• req_skills 中的所有字符串 互不相同

• 1 <= people.length <= 60

• 0 <= people[i].length <= 16

• 1 <= people[i][j].length <= 16

• people[i][j] 由小写英文字母组成

• people[i] 中的所有字符串 互不相同

• people[i] 中的每个技能是 req_skills 中的技能

• 题目数据保证「必要团队」一定存在

2585. 获得分数的方法数

考试中有 n 种类型的题目。给你一个整数 target 和一个下标从 0 开始的二维整数数组 types ，其中 types[i] = [counti, marksi] 表示第 i 种类型的题目有 counti 道，每道题目对应 marksi 分。

返回你在考试中恰好得到 target 分的方法数。由于答案可能很大，结果需要对 10^9 +7 取余。

注意，同类型题目无法区分。

• 比如说，如果有 3 道同类型题目，那么解答第 1 和第 2 道题目与解答第 1 和第 3 道题目或者第 2 和第 3 道题目是相同的。

示例 1：

```txt

输入：target = 6, types = [[6,1],[3,2],[2,3]]

输出：7

解释：要获得 6 分，你可以选择以下七种方法之一：

• 解决 6 道第 0 种类型的题目：1 + 1 + 1 + 1 + 1 + 1 = 6

• 解决 4 道第 0 种类型的题目和 1 道第 1 种类型的题目：1 + 1 + 1 + 1 + 2 = 6

• 解决 2 道第 0 种类型的题目和 2 道第 1 种类型的题目：1 + 1 + 2 + 2 = 6

• 解决 3 道第 0 种类型的题目和 1 道第 2 种类型的题目：1 + 1 + 1 + 3 = 6

• 解决 1 道第 0 种类型的题目、1 道第 1 种类型的题目和 1 道第 2 种类型的题目：1 + 2 + 3 = 6

• 解决 3 道第 1 种类型的题目：2 + 2 + 2 = 6

• 解决 2 道第 2 种类型的题目：3 + 3 = 6

```

示例 2：

```txt

输入：target = 5, types = [[50,1],[50,2],[50,5]]

输出：4

解释：要获得 5 分，你可以选择以下四种方法之一：

• 解决 5 道第 0 种类型的题目：1 + 1 + 1 + 1 + 1 = 5

• 解决 3 道第 0 种类型的题目和 1 道第 1 种类型的题目：1 + 1 + 1 + 2 = 5

• 解决 1 道第 0 种类型的题目和 2 道第 1 种类型的题目：1 + 2 + 2 = 5

• 解决 1 道第 2 种类型的题目：5

```

示例 3：

```txt

输入：target = 18, types = [[6,1],[3,2],[2,3]]

输出：1

解释：只有回答所有题目才能获得 18 分。

```

提示：

• 1 <= target <= 1000

• n == types.length

• 1 <= n <= 50

• types[i].length == 2

• 1 <= counti, marksi <= 50

D - Medicines on Grid

E - Minimize Sum of Distances

F - Oddly Similar

G - Max (Sum - Max)

划分数组得到最小的值之和

给你两个数组 nums 和 andValues，长度分别为 n 和 m。

数组的 值 等于该数组的 最后一个 元素。

你需要将 nums 划分为 m 个 不相交的连续 子数组，对于第 ith 个子数组 `[li,

ri]，子数组元素的按位AND运算结果等于andValues[i]，换句话说，对所有的1 <= i <= m，nums[li] &

nums[li + 1] & ... & nums[ri] == andValues[i]，其中&表示按位AND`运算符。

返回将 nums 划分为 m 个子数组所能得到的可能的 最小 子数组 值 之和。如果无法完成这样的划分，则返回 -1 。

示例 1：

输入： nums = [1,4,3,3,2], andValues = [0,3,3,2]

输出： 12

解释：

唯一可能的划分方法为：

1. [1,4] 因为 1 & 4 == 0

2. [3] 因为单元素子数组的按位 AND 结果就是该元素本身

3. [3] 因为单元素子数组的按位 AND 结果就是该元素本身

4. [2] 因为单元素子数组的按位 AND 结果就是该元素本身

这些子数组的值之和为 4 + 3 + 3 + 2 = 12

示例 2：

输入： nums = [2,3,5,7,7,7,5], andValues = [0,7,5]

输出： 17

解释：

划分 nums 的三种方式为：

1. [[2,3,5],[7,7,7],[5]] 其中子数组的值之和为 5 + 7 + 5 = 17

2. [[2,3,5,7],[7,7],[5]] 其中子数组的值之和为 7 + 7 + 5 = 19

3. [[2,3,5,7,7],[7],[5]] 其中子数组的值之和为 7 + 7 + 5 = 19

子数组值之和的最小可能值为 17

示例 3：

输入： nums = [1,2,3,4], andValues = [2]

输出： -1

解释：

整个数组 nums 的按位 AND 结果为 0。由于无法将 nums 划分为单个子数组使得元素的按位 AND 结果为 2，因此返回

-1。

提示：

• 1 <= n == nums.length <= 104

• 1 <= m == andValues.length <= min(n, 10)

• 1 <= nums[i] < 105

• 0 <= andValues[j] < 105

不包含相邻元素的子序列的最大和

给你一个整数数组 nums 和一个二维数组 queries，其中 queries[i] = [posi, xi]。

对于每个查询 i，首先将 nums[posi] 设置为 xi，然后计算查询 i 的答案，该答案为 nums 中 不包含相邻元素

的子序列的 最大 和。

返回所有查询的答案之和。

由于最终答案可能非常大，返回其对 109 + 7 取余 的结果。

子序列 是指从另一个数组中删除一些或不删除元素而不改变剩余元素顺序得到的数组。

示例 1：

输入： nums = [3,5,9], queries = [[1,-2],[0,-3]]

输出： 21

解释：

执行第 1 个查询后，nums = [3,-2,9]，不包含相邻元素的子序列的最大和为 3 + 9 = 12。

执行第 2 个查询后，nums = [-3,-2,9]，不包含相邻元素的子序列的最大和为 9 。

示例 2：

输入： nums = [0,-1], queries = [[0,-5]]

输出： 0

解释：

执行第 1 个查询后，nums = [-5,-1]，不包含相邻元素的子序列的最大和为 0（选择空子序列）。

提示：

• 1 <= nums.length <= 5 * 104

• -105 <= nums[i] <= 105

• 1 <= queries.length <= 5 * 104

• queries[i] == [posi, xi]

• 0 <= posi <= nums.length - 1

• -105 <= xi <= 105