fork()==0世界线变动

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

物块放置查询

有一条无限长的数轴，原点在 0 处，沿着 x 轴 正 方向无限延伸。

给你一个二维数组 queries ，它包含两种操作：

1. 操作类型 1 ：queries[i] = [1, x] 。在距离原点 x 处建一个障碍物。数据保证当操作执行的时候，位置 x 处 没有 任何障碍物。

2. 操作类型 2 ：queries[i] = [2, x, sz] 。判断在数轴范围 [0, x] 内是否可以放置一个长度为 sz 的物块，这个物块需要 完全 放置在范围 [0, x] 内。如果物块与任何障碍物有重合，那么这个物块 不能 被放置，但物块可以与障碍物刚好接触。注意，你只是进行查询，并 不是 真的放置这个物块。每个查询都是相互独立的。

请你返回一个 boolean 数组results ，如果第 i 个操作类型 2 的操作你可以放置物块，那么 results[i] 为

true ，否则为 false 。

示例 1：

输入： queries = [[1,2],[2,3,3],[2,3,1],[2,2,2]]

输出：[false,true,true]

解释：

查询 0 ，在 x = 2 处放置一个障碍物。在 x = 3 之前任何大小不超过 2 的物块都可以被放置。

示例 2：

输入： queries = [[1,7],[2,7,6],[1,2],[2,7,5],[2,7,6]]

输出：[true,true,false]

解释：

• 查询 0 在 x = 7 处放置一个障碍物。在 x = 7 之前任何大小不超过 7 的物块都可以被放置。

• 查询 2 在 x = 2 处放置一个障碍物。现在，在 x = 7 之前任何大小不超过 5 的物块可以被放置，x = 2 之前任何大小不超过 2 的物块可以被放置。

提示：

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

• 2 <= queries[i].length <= 3

• 1 <= queries[i][0] <= 2

• 1 <= x, sz <= min(5 * 104, 3 * queries.length)

• 输入保证操作 1 中，x 处不会有障碍物。

• 输入保证至少有一个操作类型 2 。