fork()==0世界线变动

6365. 最少翻转操作数

给你一个整数 n 和一个在范围 [0, n - 1] 以内的整数 p ，它们表示一个长度为 n 且下标从 0 开始的数组 arr ，数组中除了下标为 p 处是 1 以外，其他所有数都是 0 。

同时给你一个整数数组 banned ，它包含数组中的一些位置。banned 中第 i 个位置表示 arr[banned[i]] = 0 ，题目保证 banned[i] != p 。

你可以对 arr 进行 若干次 操作。一次操作中，你选择大小为 k 的一个 子数组 ，并将它 翻转 。在任何一次翻转操作后，你都需要确保 arr 中唯一的 1 不会到达任何 banned 中的位置。换句话说，arr[banned[i]] 始终 保持 0 。

请你返回一个数组 ans ，对于 [0, n - 1] 之间的任意下标 i ，ans[i] 是将 1 放到位置 i 处的 最少 翻转操作次数，如果无法放到位置 i 处，此数为 -1 。

• 子数组 指的是一个数组里一段连续 非空 的元素序列。

• 对于所有的 i ，ans[i] 相互之间独立计算。

• 将一个数组中的元素 翻转 指的是将数组中的值变成 相反顺序 。

示例 1：

```txt

输入：n = 4, p = 0, banned = [1,2], k = 4

输出：[0,-1,-1,1]

解释：k = 4，所以只有一种可行的翻转操作，就是将整个数组翻转。一开始 1 在位置 0 处，所以将它翻转到位置 0 处需要的操作数为 0 。

我们不能将 1 翻转到 banned 中的位置，所以位置 1 和 2 处的答案都是 -1 。

通过一次翻转操作，可以将 1 放到位置 3 处，所以位置 3 的答案是 1 。

```

示例 2：

```txt

输入：n = 5, p = 0, banned = [2,4], k = 3

输出：[0,-1,-1,-1,-1]

解释：这个例子中 1 一开始在位置 0 处，所以此下标的答案为 0 。

翻转的子数组长度为 k = 3 ，1 此时在位置 0 处，所以我们可以翻转子数组 [0, 2]，但翻转后的下标 2 在 banned 中，所以不能执行此操作。

由于 1 没法离开位置 0 ，所以其他位置的答案都是 -1 。

```

示例 3：

```txt

输入：n = 4, p = 2, banned = [0,1,3], k = 1

输出：[-1,-1,0,-1]

解释：这个例子中，我们只能对长度为 1 的子数组执行翻转操作，所以 1 无法离开初始位置。

```

提示：

• 1 <= n <= 10^5

• 0 <= p <= n - 1

• 0 <= banned.length <= n - 1

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

• 1 <= k <= n 

• banned[i] != p

• banned 中的值 互不相同 。

1617. 统计子树中城市之间最大距离

给你 n 个城市，编号为从 1 到 n 。同时给你一个大小为 n-1 的数组 edges ，其中 edges[i] = [ui, vi] 表示城市 ui 和 vi 之间有一条双向边。题目保证任意城市之间只有唯一的一条路径。换句话说，所有城市形成了一棵 树 。

一棵 子树 是城市的一个子集，且子集中任意城市之间可以通过子集中的其他城市和边到达。两个子树被认为不一样的条件是至少有一个城市在其中一棵子树中存在，但在另一棵子树中不存在。

对于 d 从 1 到 n-1 ，请你找到城市间 最大距离 恰好为 d 的所有子树数目。

请你返回一个大小为 n-1 的数组，其中第 d 个元素（下标从 1 开始）是城市间 最大距离 恰好等于 d 的子树数目。

请注意，两个城市间距离定义为它们之间需要经过的边的数目。

示例 1：

```txt

输入：n = 4, edges = [[1,2],[2,3],[2,4]]

输出：[3,4,0]

解释：

子树 {1,2}, {2,3} 和 {2,4} 最大距离都是 1 。

子树 {1,2,3}, {1,2,4}, {2,3,4} 和 {1,2,3,4} 最大距离都为 2 。

不存在城市间最大距离为 3 的子树。

```

示例 2：

```txt

输入：n = 2, edges = [[1,2]]

输出：[1]

```

示例 3：

```txt

输入：n = 3, edges = [[1,2],[2,3]]

输出：[2,1]

```

提示：

• 2 <= n <= 15

• edges.length == n-1

• edges[i].length == 2

• 1 <= ui, vi <= n

• 题目保证 (ui, vi) 所表示的边互不相同。

6353. 网格图中最少访问的格子数

给你一个下标从 0 开始的 m x n 整数矩阵 grid 。你一开始的位置在 左上角 格子 (0, 0) 。

当你在格子 (i, j) 的时候，你可以移动到以下格子之一：

• 满足 j < k <= grid[i][j] + j 的格子 (i, k) （向右移动），或者

• 满足 i < k <= grid[i][j] + i 的格子 (k, j) （向下移动）。

请你返回到达 右下角 格子 (m - 1, n - 1) 需要经过的最少移动格子数，如果无法到达右下角格子，请你返回 -1 。

示例 1：

```txt

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

输出：4

解释：上图展示了到达右下角格子经过的 4 个格子。

```

示例 2：

```txt

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

输出：3

解释：上图展示了到达右下角格子经过的 3 个格子。

```

示例 3：

```txt

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

输出：-1

解释：无法到达右下角格子。

```

提示：

• m == grid.length

• n == grid[i].length

• 1 <= m, n <= 10^5

• 1 <= m * n <= 10^5

• 0 <= grid[i][j] < m * n

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

864. 获取所有钥匙的最短路径

给定一个二维网格 grid ，其中：

• '.' 代表一个空房间

• '#' 代表一堵墙

• '@' 是起点

• 小写字母代表钥匙

• 大写字母代表锁

我们从起点开始出发，一次移动是指向四个基本方向之一行走一个单位空间。我们不能在网格外面行走，也无法穿过一堵墙。如果途经一个钥匙，我们就把它捡起来。除非我们手里有对应的钥匙，否则无法通过锁。

假设 k 为 钥匙/锁 的个数，且满足 1 <= k <= 6，字母表中的前 k 个字母在网格中都有自己对应的一个小写和一个大写字母。换言之，每个锁有唯一对应的钥匙，每个钥匙也有唯一对应的锁。另外，代表钥匙和锁的字母互为大小写并按字母顺序排列。

返回获取所有钥匙所需要的移动的最少次数。如果无法获取所有钥匙，返回 -1 。

示例 1：

```txt

输入：grid = ["@.a.#","###.#","b.A.B"]

输出：8

解释：目标是获得所有钥匙，而不是打开所有锁。

```

示例 2：

```txt

输入：grid = ["@..aA","..B#.","....b"]

输出：6

```

示例 3:

```txt

输入: grid = ["@Aa"]

输出: -1

```

提示：

• m == grid.length

• n == grid[i].length

• 1 <= m, n <= 30

• grid[i][j] 只含有 '.', '#', '@', 'a'-``'f``' 以及 'A'-'F'

• 钥匙的数目范围是 [1, 6] 

• 每个钥匙都对应一个 不同 的字母

• 每个钥匙正好打开一个对应的锁

2867. 统计树中的合法路径数目

给你一棵 n 个节点的无向树，节点编号为 1 到 n 。给你一个整数 n 和一个长度为 n - 1 的二维整数数组 edges ，其中 edges[i] = [ui, vi] 表示节点 ui 和 vi 在树中有一条边。

请你返回树中的 合法路径数目 。

如果在节点 a 到节点 b 之间 恰好有一个 节点的编号是质数，那么我们称路径 (a, b) 是 合法的 。

注意：

• 路径 (a, b) 指的是一条从节点 a 开始到节点 b 结束的一个节点序列，序列中的节点 互不相同 ，且相邻节点之间在树上有一条边。

• 路径 (a, b) 和路径 (b, a) 视为 同一条 路径，且只计入答案 一次 。

示例 1：

```txt

输入：n = 5, edges = [[1,2],[1,3],[2,4],[2,5]]

输出：4

解释：恰好有一个质数编号的节点路径有：

• (1, 2) 因为路径 1 到 2 只包含一个质数 2 。

• (1, 3) 因为路径 1 到 3 只包含一个质数 3 。

• (1, 4) 因为路径 1 到 4 只包含一个质数 2 。

• (2, 4) 因为路径 2 到 4 只包含一个质数 2 。

只有 4 条合法路径。

```

示例 2：

```txt

输入：n = 6, edges = [[1,2],[1,3],[2,4],[3,5],[3,6]]

输出：6

解释：恰好有一个质数编号的节点路径有：

• (1, 2) 因为路径 1 到 2 只包含一个质数 2 。

• (1, 3) 因为路径 1 到 3 只包含一个质数 3 。

• (1, 4) 因为路径 1 到 4 只包含一个质数 2 。

• (1, 6) 因为路径 1 到 6 只包含一个质数 3 。

• (2, 4) 因为路径 2 到 4 只包含一个质数 2 。

• (3, 6) 因为路径 3 到 6 只包含一个质数 3 。

只有 6 条合法路径。

```

提示：

• 1 <= n <= 10^5

• edges.length == n - 1

• edges[i].length == 2

• 1 <= ui, vi <= n

• 输入保证 edges 形成一棵合法的树。

1240. 铺瓷砖

你是一位施工队的工长，根据设计师的要求准备为一套设计风格独特的房子进行室内装修。

房子的客厅大小为 n x m，为保持极简的风格，需要使用尽可能少的 正方形 瓷砖来铺盖地面。

假设正方形瓷砖的规格不限，边长都是整数。

请你帮设计师计算一下，最少需要用到多少块方形瓷砖？

示例 1：

```txt

输入：n = 2, m = 3

输出：3

解释：3 块地砖就可以铺满卧室。

 2 块 1x1 地砖 1 块 2x2 地砖

```

示例 2：

```txt

输入：n = 5, m = 8

输出：5

```

示例 3：

```txt

输入：n = 11, m = 13

输出：6

```

提示：

• 1 <= n <= 13

• 1 <= m <= 13

2851. 字符串转换

You are given two strings s and t of equal length n. You can perform the following operation on the string s:

• Remove a suffix of s of length l where 0 < l < n and append it at the start of s.

  For example, let s = 'abcd' then in one operation you can remove the suffix 'cd' and append it in front of s making s = 'cdab'.

You are also given an integer k. Return the number of ways in which s can be transformed into t in exactly k operations.

Since the answer can be large, return it modulo 10^9 + 7.

Example 1:

```txt

Input: s = "abcd", t = "cdab", k = 2

Output: 2

Explanation:

First way:

In first operation, choose suffix from index = 3, so resulting s = "dabc".

In second operation, choose suffix from index = 3, so resulting s = "cdab".

Second way:

In first operation, choose suffix from index = 1, so resulting s = "bcda".

In second operation, choose suffix from index = 1, so resulting s = "cdab".

```

Example 2:

```txt

Input: s = "ababab", t = "ababab", k = 1

Output: 2

Explanation:

First way:

Choose suffix from index = 2, so resulting s = "ababab".

Second way:

Choose suffix from index = 4, so resulting s = "ababab".

```

Constraints:

• 2 <= s.length <= 5 * 10^5

• 1 <= k <= 10^15

• s.length == t.length

• s and t consist of only lowercase English alphabets.