fork()==0世界线变动

1760. 袋子里最少数目的球

给你一个整数数组 nums ，其中 nums[i] 表示第 i 个袋子里球的数目。同时给你一个整数 maxOperations 。

你可以进行如下操作至多 maxOperations 次：

• 选择任意一个袋子，并将袋子里的球分到 2 个新的袋子中，每个袋子里都有 正整数 个球。

  • 比方说，一个袋子里有 5 个球，你可以把它们分到两个新袋子里，分别有 1 个和 4 个球，或者分别有 2 个和 3 个球。

你的开销是单个袋子里球数目的 最大值 ，你想要 最小化 开销。

请你返回进行上述操作后的最小开销。

示例 1：

```txt

输入：nums = [9], maxOperations = 2

输出：3

解释：

• 将装有 9 个球的袋子分成装有 6 个和 3 个球的袋子。[9] -> [6,3] 。

• 将装有 6 个球的袋子分成装有 3 个和 3 个球的袋子。[6,3] -> [3,3,3] 。

装有最多球的袋子里装有 3 个球，所以开销为 3 并返回 3 。

```

示例 2：

```txt

输入：nums = [2,4,8,2], maxOperations = 4

输出：2

解释：

• 将装有 8 个球的袋子分成装有 4 个和 4 个球的袋子。[2,4,8,2] -> [2,4,4,4,2] 。

• 将装有 4 个球的袋子分成装有 2 个和 2 个球的袋子。[2,4,4,4,2] -> [2,2,2,4,4,2] 。

• 将装有 4 个球的袋子分成装有 2 个和 2 个球的袋子。[2,2,2,4,4,2] -> [2,2,2,2,2,4,2] 。

• 将装有 4 个球的袋子分成装有 2 个和 2 个球的袋子。[2,2,2,2,2,4,2] -> [2,2,2,2,2,2,2,2] 。

装有最多球的袋子里装有 2 个球，所以开销为 2 并返回 2 。

```

示例 3：

```txt

输入：nums = [7,17], maxOperations = 2

输出：7

```

提示：

• 1 <= nums.length <= 10^5

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

1889. 装包裹的最小浪费空间

给你 n 个包裹，你需要把它们装在箱子里，每个箱子装一个包裹。总共有 m 个供应商提供 不同尺寸 的箱子（每个规格都有无数个箱子）。如果一个包裹的尺寸 小于等于 一个箱子的尺寸，那么这个包裹就可以放入这个箱子之中。

包裹的尺寸用一个整数数组 packages 表示，其中 packages[i] 是第 i 个包裹的尺寸。供应商用二维数组 boxes 表示，其中 boxes[j] 是第 j 个供应商提供的所有箱子尺寸的数组。

你想要选择 一个供应商 并只使用该供应商提供的箱子，使得 总浪费空间最小 。对于每个装了包裹的箱子，我们定义 浪费的 空间等于 箱子的尺寸 - 包裹的尺寸 。总浪费空间 为 所有 箱子中浪费空间的总和。

• 比方说，如果你想要用尺寸数组为 [4,8] 的箱子装下尺寸为 [2,3,5] 的包裹，你可以将尺寸为 2 和 3 的两个包裹装入两个尺寸为 4 的箱子中，同时把尺寸为 5 的包裹装入尺寸为 8 的箱子中。总浪费空间为 (4-2) + (4-3) + (8-5) = 6 。

请你选择 最优 箱子供应商，使得 总浪费空间最小 。如果 无法 将所有包裹放入箱子中，请你返回 -1 。由于答案可能会 很大 ，请返回它对 10^9 + 7 取余 的结果。

示例 1：

```txt

输入：packages = [2,3,5], boxes = [[4,8],[2,8]]

输出：6

解释：选择第一个供应商最优，用两个尺寸为 4 的箱子和一个尺寸为 8 的箱子。

总浪费空间为 (4-2) + (4-3) + (8-5) = 6 。

```

示例 2：

```txt

输入：packages = [2,3,5], boxes = [[1,4],[2,3],[3,4]]

输出：-1

解释：没有箱子能装下尺寸为 5 的包裹。

```

示例 3：

```txt

输入：packages = [3,5,8,10,11,12], boxes = [[12],[11,9],[10,5,14]]

输出：9

解释：选择第三个供应商最优，用两个尺寸为 5 的箱子，两个尺寸为 10 的箱子和两个尺寸为 14 的箱子。

总浪费空间为 (5-3) + (5-5) + (10-8) + (10-10) + (14-11) + (14-12) = 9 。

```

提示：

• n == packages.length

• m == boxes.length

• 1 <= n <= 10^5

• 1 <= m <= 10^5

• 1 <= packages[i] <= 10^5

• 1 <= boxes[j].length <= 10^5

• 1 <= boxes[j][k] <= 10^5

• sum(boxes[j].length) <= 10^5

• boxes[j] 中的元素 互不相同 。

2258. 逃离火灾

给你一个下标从 0 开始大小为 m x n 的二维整数数组 grid ，它表示一个网格图。每个格子为下面 3 个值之一：

• 0 表示草地。

• 1 表示着火的格子。

• 2 表示一座墙，你跟火都不能通过这个格子。

一开始你在最左上角的格子 (0, 0) ，你想要到达最右下角的安全屋格子 (m - 1, n - 1) 。每一分钟，你可以移动到 相邻 的草地格子。每次你移动 之后 ，着火的格子会扩散到所有不是墙的 相邻 格子。

请你返回你在初始位置可以停留的 最多 分钟数，且停留完这段时间后你还能安全到达安全屋。如果无法实现，请你返回 -1 。如果不管你在初始位置停留多久，你 总是 能到达安全屋，请你返回 10^9 。

注意，如果你到达安全屋后，火马上到了安全屋，这视为你能够安全到达安全屋。

如果两个格子有共同边，那么它们为 相邻 格子。

示例 1：

```txt

输入：grid = [[0,2,0,0,0,0,0],[0,0,0,2,2,1,0],[0,2,0,0,1,2,0],[0,0,2,2,2,0,2],[0,0,0,0,0,0,0]]

输出：3

解释：上图展示了你在初始位置停留 3 分钟后的情形。

你仍然可以安全到达安全屋。

停留超过 3 分钟会让你无法安全到达安全屋。

```

示例 2：

```txt

输入：grid = [[0,0,0,0],[0,1,2,0],[0,2,0,0]]

输出：-1

解释：上图展示了你马上开始朝安全屋移动的情形。

火会蔓延到你可以移动的所有格子，所以无法安全到达安全屋。

所以返回 -1 。

```

示例 3：

```txt

输入：grid = [[0,0,0],[2,2,0],[1,2,0]]

输出：1000000000

解释：上图展示了初始网格图。

注意，由于火被墙围了起来，所以无论如何你都能安全到达安全屋。

所以返回 109 。

```

提示：

• m == grid.length

• n == grid[i].length

• 2 <= m, n <= 300

• 4 <= m * n <= 2 * 10^4

• grid[i][j] 是 0 ，1 或者 2 。

• grid[0][0] == grid[m - 1][n - 1] == 0

2939. 最大异或乘积

给你三个整数 a ，b 和 n ，请你返回 (a XOR x) * (b XOR x) 的 最大值 且 x 需要满足 0 <= x < 2^n。

由于答案可能会很大，返回它对 10^9 + 7 取余 后的结果。

注意，XOR 是按位异或操作。

示例 1：

```txt

输入：a = 12, b = 5, n = 4

输出：98

解释：当 x = 2 时，(a XOR x) = 14 且 (b XOR x) = 7 。所以，(a XOR x) * (b XOR x) = 98 。

98 是所有满足 0 <= x < 2n 中 (a XOR x) * (b XOR x) 的最大值。

```

示例 2：

```txt

输入：a = 6, b = 7 , n = 5

输出：930

解释：当 x = 25 时，(a XOR x) = 31 且 (b XOR x) = 30 。所以，(a XOR x) * (b XOR x) = 930 。

930 是所有满足 0 <= x < 2n 中 (a XOR x) * (b XOR x) 的最大值。

```

示例 3：

```txt

输入：a = 1, b = 6, n = 3

输出：12

解释： 当 x = 5 时，(a XOR x) = 4 且 (b XOR x) = 3 。所以，(a XOR x) * (b XOR x) = 12 。

12 是所有满足 0 <= x < 2n 中 (a XOR x) * (b XOR x) 的最大值。

```

提示：

• 0 <= a, b < 2^50

• 0 <= n <= 50

2791. 树中可以形成回文的路径数

给你一棵 树（即，一个连通、无向且无环的图），根 节点为 0 ，由编号从 0 到 n - 1 的 n 个节点组成。这棵树用一个长度为 n 、下标从 0 开始的数组 parent 表示，其中 parent[i] 为节点 i 的父节点，由于节点 0 为根节点，所以 parent[0] == -1 。

另给你一个长度为 n 的字符串 s ，其中 s[i] 是分配给 i 和 parent[i] 之间的边的字符。s[0] 可以忽略。

找出满足 u < v ，且从 u 到 v 的路径上分配的字符可以 重新排列 形成 回文 的所有节点对 (u, v) ，并返回节点对的数目。

如果一个字符串正着读和反着读都相同，那么这个字符串就是一个 回文 。

示例 1：

```txt

输入：parent = [-1,0,0,1,1,2], s = "acaabc"

输出：8

解释：符合题目要求的节点对分别是：

• (0,1)、(0,2)、(1,3)、(1,4) 和 (2,5) ，路径上只有一个字符，满足回文定义。

• (2,3)，路径上字符形成的字符串是 "aca" ，满足回文定义。

• (1,5)，路径上字符形成的字符串是 "cac" ，满足回文定义。

• (3,5)，路径上字符形成的字符串是 "acac" ，可以重排形成回文 "acca" 。

```

示例 2：

```txt

输入：parent = [-1,0,0,0,0], s = "aaaaa"

输出：10

解释：任何满足 u < v 的节点对 (u,v) 都符合题目要求。

```

提示：

• n == parent.length == s.length

• 1 <= n <= 10^5

• 对于所有 i >= 1 ，0 <= parent[i] <= n - 1 均成立

• parent[0] == -1

• parent 表示一棵有效的树

• s 仅由小写英文字母组成

3022. 给定操作次数内使剩余元素的或值最小

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

一次操作中，你可以选择 nums 中满足 0 <= i < nums.length - 1 的一个下标 i ，并将 nums[i] 和 nums[i + 1] 替换为数字 nums[i] & nums[i + 1] ，其中 & 表示按位 AND 操作。

请你返回 至多 k 次操作以内，使 nums 中所有剩余元素按位 OR 结果的 最小值 。

示例 1：

```txt

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

输出：3

解释：执行以下操作：

1. 将 nums[0] 和 nums[1] 替换为 (nums[0] & nums[1]) ，得到 nums 为 [1,3,2,7] 。

2. 将 nums[2] 和 nums[3] 替换为 (nums[2] & nums[3]) ，得到 nums 为 [1,3,2] 。

最终数组的按位或值为 3 。

3 是 k 次操作以内，可以得到的剩余元素的最小按位或值。

```

示例 2：

```txt

输入：nums = [7,3,15,14,2,8], k = 4

输出：2

解释：执行以下操作：

1. 将 nums[0] 和 nums[1] 替换为 (nums[0] & nums[1]) ，得到 nums 为 [3,15,14,2,8] 。

2. 将 nums[0] 和 nums[1] 替换为 (nums[0] & nums[1]) ，得到 nums 为 [3,14,2,8] 。

3. 将 nums[0] 和 nums[1] 替换为 (nums[0] & nums[1]) ，得到 nums 为 [2,2,8] 。

4. 将 nums[1] 和 nums[2] 替换为 (nums[1] & nums[2]) ，得到 nums 为 [2,0] 。

最终数组的按位或值为 2 。

2 是 k 次操作以内，可以得到的剩余元素的最小按位或值。

```

示例 3：

```txt

输入：nums = [10,7,10,3,9,14,9,4], k = 1

输出：15

解释：不执行任何操作，nums 的按位或值为 15 。

15 是 k 次操作以内，可以得到的剩余元素的最小按位或值。

```

提示：

• 1 <= nums.length <= 10^5

• 0 <= nums[i] < 2^30

• 0 <= k < nums.length

2836. 在传球游戏中最大化函数值

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

总共有 n 名玩家，玩家 编号 互不相同，且为 [0, n - 1] 中的整数。这些玩家玩一个传球游戏，receiver[i] 表示编号为 i 的玩家会传球给编号为 receiver[i] 的玩家。玩家可以传球给自己，也就是说 receiver[i] 可能等于 i 。

你需要从 n 名玩家中选择一名玩家作为游戏开始时唯一手中有球的玩家，球会被传 恰好 k 次。

如果选择编号为 x 的玩家作为开始玩家，定义函数 f(x) 表示从编号为 x 的玩家开始，k 次传球内所有接触过球玩家的编号之 和 ，如果有玩家多次触球，则 累加多次 。换句话说， f(x) = x + receiver[x] + receiver[receiver[x]] + ... + receiver^(k)[x] 。

你的任务时选择开始玩家 x ，目的是 最大化 f(x) 。

请你返回函数的 最大值 。

注意：receiver 可能含有重复元素。

示例 1：

传递次数

传球者编号

接球者编号

x + 所有接球者编号

2

1

2

1

3

2

1

0

3

3

0

2

5

4

2

1

6

```txt

输入：receiver = [2,0,1], k = 4

输出：6

解释：上表展示了从编号为 x = 2 开始的游戏过程。

从表中可知，f(2) 等于 6 。

6 是能得到最大的函数值。

所以输出为 6 。

```

示例 2：

传递次数

传球者编号

接球者编号

x + 所有接球者编号

4

1

4

3

7

2

3

2

9

3

2

1

10

```txt

输入：receiver = [1,1,1,2,3], k = 3

输出：10

解释：上表展示了从编号为 x = 4 开始的游戏过程。

从表中可知，f(4) 等于 10 。

10 是能得到最大的函数值。

所以输出为 10 。

```

提示：

• 1 <= receiver.length == n <= 10^5

• 0 <= receiver[i] <= n - 1

• 1 <= k <= 10^10