力扣杯春赛 – 战队赛 LCCUP’23
符文储备
关键词：贪婪
题目起源：LCP 77. 符文储备 – 力扣（Leetcode）
题目形容
T 贪婪远征队在登程前须要携带一些「符文」，作为后续的冒险储备。runes[i] 示意第 i 枚符文的魔力值。
他们将从中选取若干符文进行携带，并对这些符文进行重新排列，以确保任意相邻的两块符文之间的魔力值相差不超过 1。
请返回他们可能携带的符文 最大数量。
输出：runes = [1,3,5,4,1,7]
输入：3
解释：最佳的抉择计划为[3,5,4]
将其排列为 [3,4,5] 后，任意相邻的两块符文魔力值均不超过 1，携带数量为 3
其余满足条件的计划为 [1,1] 和 [7]，数量均小于 3。因而返回可携带的最大数量 3。输出：runes = [1,1,3,3,2,4]
输入：6
解释：排列为 [1,1,2,3,3,4]，可携带所有的符文数据范畴
1 <= runes.length <= 10^4
0 <= runes[i] <= 10^4问题剖析
为了使得任意一块符文与其四周的魔力差值尽可能小，无妨将符文依照魔力值排序，从排序后的序列中选出满足“任意相邻的两块符文之间的魔力值相差不超过 1”的一段最长子序列，该子序列的长度即为题目要求的“最大数量”。
代码实现
int runeReserve(vector<int> &runes) {int n = runes.size(), res = 0, cur = 0;
// 按魔法值从小到大排序
sort(runes.begin(), runes.end());
// 找出满足条件的最长序列
for (int i = 1; i < n; i++) {if (runes[i] - runes[i - 1] <= 1)cur++;
else res = max(cur, res), cur = 0;
}
res = max(res, cur); // 不要漏掉最初一个子序列
return res + 1;
}工夫复杂度：O(nlog(n))
空间复杂度：O(1)
城墙防线
关键词：二分
题目起源：LCP 78. 城墙防线 – 力扣（Leetcode）
题目形容
T 二分在探险营地间，小扣意外发现了一片城墙陈迹，在摸索期间，却不巧遇到迁徙中的兽群向他迎面冲来。情急之下小扣吹响了他的苍蓝笛，随着笛声响起，陈迹中的城墙逐步产生了横向收缩。
已知 rampart[i] = [x,y] 示意第 i 段城墙的初始所在区间。当城墙产生收缩时，将遵循以下规定：
- 所有的城墙会同时收缩相等的长度；
- 每个城墙能够向左、向右或向两个方向收缩。
小扣为了确保本身的平安，须要在所有城墙均无重叠的状况下，让城墙尽可能的收缩。请返回城墙能够收缩的 最大值。
留神：
- 初始状况下，所有城墙均不重叠，且
rampart中的元素升序排列； - 两侧的城墙能够向外有限收缩。
输出：rampart = [[0,3],[4,5],[7,9]]
输入：3
解释：如下图所示：rampart[0] 向左侧收缩 3 个单位；rampart[2] 向右侧收缩 3 个单位；rampart[1] 向左侧收缩 1 个单位，向右收缩 2 个单位。不存在收缩更多的计划，返回 3。输出：rampart = [[1,2],[5,8],[11,15],[18,25]]
输入：4数据范畴
3 <= rampart.length <= 10^4
rampart[i].length == 2
0 <= rampart[i][0] < rampart[i][1] <= rampart[i+1][0] <= 10^8问题剖析
直观地来看，若收缩长度为 k 时不产生重叠，那么收缩长度为 k - 1 时也不产生重叠，于是发现，k 具备枯燥性，可通过二分来查找满足条件的最大的 k。
设区间距离的总和为 total，则 k 的上限为 0，k 的下限为 total/(n-2)。试想，依照最好的策略收缩，第一个区间必定全副往左边收缩，最初一个区间必定全副往右收缩，那么还剩下两头 n - 1 个区间距离，而还有两头 n - 2 个区间须要收缩，这 n - 2 个区间收缩的总长度必然不能超过区间距离的总和为 total，也即每个区间最多能分到长度为 total/(n-2)的距离。
二分过程中，对 k 查看时，只须要查看两头 n - 2 个区间即可，因为首尾两个区间必定能够满足要求。在查看每个区间的过程中，只须要保护其左侧还剩多少空间，依照左侧尽量填满，左侧不够右侧来凑的策略进行填充。
代码实现
int rampartDefensiveLine(vector<vector<int>> &rampart) {
// 测试数据中的区间已按左边界从小到大排序且不存在区间重叠的状况
auto &v = rampart;
int n = rampart.size(), l = 0, r, mid;
for (int i = 1; i < n; i++)
r += v[i][0] - v[i - 1][1];
r /= n - 2;
// 二分中的查看
auto check = [&](int len) {
// 以后查看的区间左侧的空间
int ls = v[1][0] - v[0][1];
for (int i = 1; i < n - 1; i++) {
// 左侧够：全往左侧收缩
if (ls >= len)ls = v[i + 1][0] - v[i][1];
// 左侧不够：左侧空间用完用右侧的
else ls = v[i + 1][0] - v[i][1] - (len - ls);
// 右侧不够用则无奈实现收缩
if (ls < 0)return false;
}
return true;
};
// 二分答案
while (l < r) {mid = (l + r + 1) >> 1;
if (check(mid))l = mid;
else r = mid - 1;
}
return l;
}工夫复杂度：O(nlog(m/n))，其中，n 为区间数，m 为区间距离总和
空间复杂度：O(1)
提取咒文
关键词：宽度优先
题目起源：LCP 79. 提取咒文 – 力扣（Leetcode）
题目形容
T 宽度优先随着兽群逐步远去，一座大升降机缓缓的从公开升到了远征队背后。借由这台升降机，他们将可能达到地底的永恒至森。
在升降机的操作台上，是一个由魔法符号组成的矩阵，为了便于辨识，咱们用小写字母来示意。matrix[i][j] 示意矩阵第 i 行 j 列的字母。该矩阵上有一个提取安装，能够对所在位置的字母提取。
提取安装初始位于矩阵的左上角 [0,0]，能够通过每次操作挪动到上、下、左、右相邻的 1 格地位中。提取安装每次挪动或每次提取均记为一次操作。
远征队须要依照程序，从矩阵中逐个取出字母以组成 mantra，才可能胜利的启动升降机。请返回他们 起码 须要耗费的操作次数。如果无奈实现提取，返回 -1。
留神：
- 提取安装可对同一地位的字母反复提取，每次提取一个
- 提取字母时，需按词语程序顺次提取
问题剖析
最短路问题个别可采纳 BFS 来求解，因为本题可能会屡次通过同一个地位，因而不能单纯应用地位来示意一个状态，状态还应该蕴含以后曾经提取到多少个字符这一个信息。
于是，可采纳一个三元组 (i,j,k) 来示意一个状态，(i,j,k)示意走到地位 (i,j) 时曾经提取了 k 个字符（留神 k 的含意）。因为 i、j、k 均不超过 100，因而可采纳 i、j、k 别离可用一个 6 位的二进制数来示意，也即 i、j、k 可用一个整数来示意。
代码实现
int extractMantra(vector<string> &matrix, string mantra) {
// 用三元组来示意状态
typedef tuple<int, int, int> tp;
// 往四个方向挪动
int dx[] = {0, 0, -1, 1}, dy[] = {-1, 1, 0, 0};
const int N = 1e2 + 2;
// 示意状态 (i,j,k) 是否曾经呈现过
bool f[N][N][N] = {false};
int m = matrix.size(), n = matrix[0].size(), l = mantra.size() - 1;
// 两个数组模仿队列
bool cur = false, nex = true; // 标记哪个是以后层哪个是下一层
int s[2] = {0}; // 以后层的结点数和下一层的结点数
tp q[2][N * N]; // 以后层的结点和下一层的结点
int step = 0, u, v;
s[cur] = 1, q[cur][0] = {0, 0, 0}, f[0][0][0] = true;
while (s[cur]) {while (s[cur]) {
// 取出队头
auto [i, j, k] = q[cur][--s[cur]];
// 所在位置刚好是以后状态下一个要提取字符
// 既然找到以后状态的下一个要提取的字符，那就没必要持续拓展以后结点了
if (matrix[i][j] == mantra[k]) {if (k == l)return step + 1;
if (!f[i][j][k + 1])
q[nex][s[nex]++] = {i, j, k + 1}, f[i][j][k + 1] = true;
continue; // 没必要持续拓展以后结点了
}
// 拓展以后结点
for (int z = 0; z < 4; z++) {u = i + dx[z], v = j + dy[z];
if (u < 0 || u >= m || v < 0 || v >= n || f[u][v][k])continue;
q[nex][s[nex]++] = {u, v, k}, f[u][v][k] = true;
}
}
// 操作数 +1（不论后面一层的结点是拓展还是提取，操作均 +1）step++, cur = !cur, nex = !nex;
}
return -1;
}在代码中存在两个优化：
- 应用两个数组来模仿队列，两个数组交替应用，节约空间。至于数组的第二维为什么开到 N * N 就够，临时还没有想到比拟好的证实办法。
- 所在位置刚好是以后状态下一个要提取字符，那么间接提取即可，而不用拓展以后结点。间接提取必定比从以后地位往后再找一个地位提取要快或者相等。证实也很简略，假如以后状态为 p，以后状态所在位置恰好是下一个要提取的字符 c，假如从 p 往后能找到一个比 p 更优的状态 q，q 状态所在位置也是字符 c，从 q 提取 c 必定不会比从 p 提取 c 更优，这与假如矛盾。
工夫复杂度：O(mnl)。最坏状况下要遍历所有状态，实际上上述代码运行速度还是蛮快的，200ms 内能跑完所有样例。
空间复杂度：O(mnl)
生物进化录
关键词：深度优先
题目起源：LCP 80. 生物进化录 – 力扣（Leetcode）
题目形容
T 深度优先在永恒之森中，存在着一本生物进化录，以 一个树形构造 记录了所有生物的演化过程。通过察看并整顿了各节点间的关系，parents[i] 示意编号 i 节点的父节点编号(根节点的父节点为 -1)。
为了摸索和记录其中的演变法则，队伍中的炼金术师提出了一种办法，能够以字符串的模式将其复刻下来，规定如下：
- 初始只有一个根节点，示意演变的终点，顺次记录
01字符串中的字符， - 如果记录
0，则在以后节点下增加一个子节点，并将指针指向新增加的子节点； - 如果记录
1，则将指针回退到以后节点的父节点处。
当初须要利用上述的记录办法，复刻下它的演化过程。请返回可能复刻演化过程的字符串中，字典序最小 的 01 字符串。
留神：
- 节点指针最终能够停在任何节点上，不肯定要回到根节点。
输出：parents = [-1,0,0,2]
输入："00110"
解释：树结构如下图所示，共存在 2 种记录计划：。第 1 种计划为：0(记录编号 1 的节点) -> 1(回退至节点 0) -> 0(记录编号 2 的节点) -> 0((记录编号 3 的节点))
第 2 种计划为：0(记录编号 2 的节点) -> 0(记录编号 3 的节点) -> 1(回退至节点 2) -> 1(回退至节点 0) -> 0(记录编号 1 的节点)
返回字典序更小的 "00110"输出：parents = [-1,0,0,1,2,2]
输入："00101100"数据范畴
1 <= parents.length <= 10^4
-1 <= parents[i] < i (即父节点编号小于子节点)问题剖析
对于“树”类的问题，时常和深度优先遍历相干，因为树结构的递归性，面对一个具体的问题时，首先要思考该问题是否也能够递归求解。
在本题中，先解决两个细节。
一是，数据范畴中有“父节点编号小于子节点”，阐明结点 0 就是整棵树的根节点，因为比 0 小的数只有 -1，父结点为 - 1 的结点为根节点。
二是，题目中说“不肯定要回到根节点”，无妨强制回到根节点，回到根节点的成果就是在序列的开端多加了几个 1，最初将这些 1 删除即可，前面会证实这样做并不影响答案。
设根节点为 p，p 的左右孩子结点为 l、r（先假如只有两个孩子），那么，p 树（以 p 为根节点的树）的最小 01 序列是否是由 l 树的最小 01 序列和 r 树的最小 01 序列组成呢？答案是必定的。
首先明确一点，假如先遍历 l 树，必定不会 l 树没遍历完，又回到根节点，再去遍历 r 树，再回到根节点，再遍历完 l 树，这样显著会增大字典序，因为要想减小字典序，就应该尽可能地使序列后面是 0，也即尽可能往下走，所以，必定是遍历完一棵子树再去遍历另一棵子树。
所以。p 树的最小 01 序列必然是如下模式：0+ l 串+ r 串+1。
对于任意一个结点（除整棵树的根节点）都存在一进一出，即从一个结点往下进入该结点，从该点往上进来，所以后面有 1 个 0 开端有一个 1。
那么， l 串 是 l 树的最小 01 序列吗？因为 l 串 越小，0+ l 串 + r 串+1 也就越小，故 p 树的最小 01 序列中的 l 串 必然是 l 树的最小 01 序列， r 串 同理。 l 串 和 r 串，字典序小的在后面。
于是，求 p 树的最小 01 序列可转换为求 l 树的最小 01 序列和求 r 树的最小 01 序列，也即可将原问题转换为两个规模较小的且与原问题类似的且互不相干（影响）的子问题，从而能够递归求解。
当然，须要留神的是，题目并没有说每个结点只有两个子结点，后面只是为了方面形容。
当初，证实后面说的“这样做并不影响答案”，权且将序列开端的间断的一段 1 称为尾 1。
因为要比拟 L 串和 R 串的字典序，设一决胜负的点为 K，可分为如下几种状况（只思考 L 字典序小于 R 串字典序的状况）
-
K 不在 R 串的尾 1，即如下模式，其中 A、B、C、D 别离示意一段
01序列，长度未必雷同L 串 A0C1111 # K 不在 L 串的尾 1 R 串 A1D11 L 串 A1 # K 在 L 串的尾 1 R 串 A11D111显然，去除 LR 的尾 1 后的 LR 的字典序小于去除 RL 的尾 1 后的 RL 的字典序，只管 LR 的可能会更长，但 LR 和 RL 的决胜点在“A”后一个地位就确定了，与尾 1 无关。顺带说一句，尾 1 局部的前一个数必然不是 1。
-
K 在 R 串的尾 1 局部，即如下模式，
L 串 A101111111111 # K 不在 L 串的尾 1 R 串 A11111 L 串 A1111 # K 在 L 串的尾 1 R 串 A111111显然，也有，去除 LR 的尾 1 后的 LR 的字典序小于去除 RL 的尾 1 后的 RL 的字典序。
综上，若有 L 串字典序小于 R 串字典序成立，则必有（去尾 1）LR 串字典序小于（去尾 1）RL 串字典序，也即，在比拟 L、R 串时，L、R 带着尾 1 是不影响后果的。
代码实现
const int N = 1e4 + 5;
int h[N], e[N], ne[N], c[N], idx;
void add(int a, int b) {c[a]++, e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
string evolutionaryRecord(vector<int> &parents) {memset(h, -1, sizeof h);
// 构建邻接表
int n = parents.size();
for (int i = 1; i < n; i++)add(parents[i], i);
function<string(int)> dfs = [&](int u) {
// 叶子结点：一进一出
if (h[u]==-1)return string("01");
// 非叶子结点：一进 + 遍历子树 + 一出
// 子树的 01 序列
int k = 0;
string s];
for (int i = h[u]; ~i; i = ne[i])
s[k++] = dfs(e[i]);
// 子树 01 序列按字典序排列
sort(s, s + k);
// 拼接
string r = "0";
for (int i = 0; i < k; i++)r.append(s[i]);
r.append("1");
return r;
};
// dfs
string res = dfs(0);
// 去除首位 0 和尾部 1
n = res.size();
while (res[--n] == '1');
return res.substr(1, n);
}工夫复杂度：介于 O(n2)和 O(nlog(n))之间
空间复杂度：O(n)
与非的谜题
关键词：线段树、位运算
题目起源：LCP 81. 与非的谜题 – 力扣（Leetcode）
题目形容
T 线段树
T 位运算在永恒之森中，封存着无关万灵之树线索的卷轴，只有探险队通过最初的考验，便能够获取返回万灵之树的线索。
探险队须要从一段一直变动的谜题数组中找到最终的明码，初始的谜题为长度为 n 的数组 arr（下标从 0 开始），数组中的数字代表了 k 位二进制数。
破解谜题的过程中，须要应用 与非（NAND） 运算形式，operations[i] = [type,x,y] 示意第 i 次进行的谜题操作信息：
- 若
type = 0，示意批改操作，将谜题数组中下标x的数字变动为y； -
若
type = 1，示意运算操作，将数字y进行x*n次「与非」操作，第i次与非操作为y = y NAND arr[i%n]；运算操作后果即：
y NAND arr[0%n] NAND arr[1%n] NAND arr[2%n] ... NAND arr[(x*n-1)%n]
最初，将所有运算操作的后果按程序逐个进行 异或（XOR）运算，从而失去最终解开封印的明码。请返回最终解开封印的明码。
「与非」（NAND）的操作为：先进行 与 操作，后进行 非 操作。
输出:
k = 3
arr = [1,2]
operations = [[1,2,3],[0,0,3],[1,2,2]]
输入: 2输出:
k = 4
arr = [4,6,4,7,10,9,11]
operations = [[1,5,7],[1,7,14],[0,6,7],[1,6,5]]
输入: 9数据范畴
1 <= arr.length, operations.length <= 10^4
1 <= k <= 30
0 <= arr[i] < 2^k
若 type = 0，0 <= x < arr.length 且 0 <= y < 2^k
若 type = 1，1 <= x < 10^9 且 0 <= y < 2^k
保障存在 type = 1 的操作问题剖析
初看，存在单点批改和区间查问，大略和树状数组、线段树无关。
因为 NAND 运算不满足结合律，所以，没有[i..j]NAND 值 =[i..k]NAND 值 NAND[k+1..j]NAND 值成立，也即不能单纯保护某段区间的 NAND 值。
y NAND arr[0] NAND ... NAND arr[n-1]可看做 y 从数组穿过，但穿过 a[i]后的值与后面的 a[j]都有关系，其中 j
保护 0 从 [i..k] 穿过后的值 l[0]，1 从 [i..k] 穿过后的值 l[1]，对于区间 [k+1..j] 同理，得 r[0]和 r[1]，于是，0 从区间 [i..j] 穿过后的值就为 r[l[0]]，0 从区间 [i..j] 穿过后的值就为 r[l[1]]。因为 y 有 k 位，因而，须要保护 0 从区间 [i..j] 的第 0 位穿过后的值，从区间 [i..j] 的第 1 位穿过后的值，…，1 同理。
对于 0 / 1 穿过区间 [i..j] 后的值，可应用线段树来保护。
- 执行批改操作时，所有蕴含批改点的区间保护的值均须要批改（从新计算）
- 执行查问操作时，只须要查问 0 / 1 穿过区间 [0..n-1] 后的值即可，能够省略查问函数。
因为须要屡次穿过区间，须要对穿过次数进行分类探讨，设穿过次数为 x，当初先只看一位二进制 y，假如其穿过 1 次后变成 y1，穿过 2 次后变成 y1，则有
- 若 x =1，那么后果就为 y1；
- 若 y1=y，也即穿 1 次后不变，能够设想失去，无论穿过多少次都是不变的，于是后果仍为 y1
- 若 y2=y1，阐明，从 y1 开始，无论穿过多少次仍为 y1，于是后果为 y1
- 否则，阐明 y1!=y，y2！=y1，又因为取值只有 0 和 1，所以是 01 交替呈现，若 x 为奇数，则后果为 y1，若 x 为偶数，则后果为 y（不变），且 y 和 y1 不同（一个 0，一个 1），于是后果可写作 y^(x&1)
代码实现
const int N = 1e4 + 5;
struct Node {int l, r, f[2];
} tr[N << 2];
int *a, M, K; // 数组 mask K
/**
* 更新节点信息
*/
void pushup(int u) {auto &t = tr[u].f, &l = tr[u << 1].f, &r = tr[u << 1 | 1].f;
t[0] = 0, t[1] = 0;
for (int i = 0; i < K; i++) {// &(1<<i)示意只看以后第 i 位（倒数）t[0] |= r[l[0] >> i & 1] & (1 << i);
t[1] |= r[l[1] >> i & 1] & (1 << i);
}
}
/**
* 建设线段树
*/
void build(int u, int l, int r) {tr[u] = {l, r};
// 叶子节点
if (l == r) {tr[u].f[0] = M, tr[u].f[1] = ~*(a + l);
return;
}
// 递归创立节点
int mid = (l + r) >> 1;
build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
// 更新节点 u 的 f
pushup(u);
}
/**
* 批改操作
*/
void modify(int u, int x, int v) {
// 找到批改地位（叶子结点只批改 1 即可）if (tr[u].l == x && tr[u].r == x)tr[u].f[1] = ~v;
else {
// 去左区间或者右区间找
int mid = (tr[u].l + tr[u].r) >> 1;
if (x <= mid)modify(u << 1, x, v);
else modify(u << 1 | 1, x, v);
// 更新节点 u 的 f
pushup(u);
}
}
int getNandResult(int k, vector<int> &arr, vector<vector<int>> &operations) {int n = arr.size(), res = 0;
a = &arr[0], M = (1 << k) - 1, K = k;
// 建设线段树
build(1, 0, n - 1);
// 执行操作
int r, y, t;
for (auto &op: operations) {
// 运算操作
if (op[0]) {for (int i = 0; i < K; i++) {y = op[2] >> i & 1;
// 先穿过一次
t = tr[1].f[y] >> i & 1;
// 若只穿过 1 次，则取穿过 1 次的后果
// 若穿过 1 次的后果与原来雷同，则不管穿过多少次，都会与原来雷同，故取穿过 1 次的后果
// 若穿过 2 次的后果与穿过 1 次的后果雷同，则再往后穿，后果与第一次也雷同，故取穿过 1 次的后果
// 以上条件由上到下优先级顺次升高
// 否则，阐明原来与第一次后果不同，第一次与第二次不同，也即 01 交替
// 若为偶数次，则放弃不变，若为奇数次，则与第一次雷同
if (op[1] != 1 && t != y && (tr[1].f[t] >> i & 1) != t)
// t = op[1] & 1 ? t : y;
t = y ^ (op[1] & 1);
res ^= t << i;
}
}
// 批改操作
else modify(1, op[1], op[2]);
}
return res;
}工夫复杂度：O(log(n) + m(k+log(n) ) ) ≈ O(mk)
空间复杂度：O(n)
万灵之树
关键词：深度优先、动静布局、状态压缩、数学
题目起源：LCP 82. 万灵之树 – 力扣（Leetcode）
题目形容
T 深度优先
T 动静布局
T 状态压缩
T 数学探险家小扣终于来到了万灵之树前，挑战最初的谜题。
已知小扣领有足够数量的链接节点和 n 颗幻境宝石，gem[i] 示意第 i 颗宝石的数值。当初小扣须要应用这些链接节点和宝石组合成一颗二叉树，其组装规定为：
- 链接节点将作为二叉树中的非叶子节点，且每个链接节点必须领有
2个子节点； - 幻境宝石将作为二叉树中的叶子节点，所有的幻境宝石都必须被应用。
能量首先进入根节点，而后将按如下规定进行挪动和记录：
-
若能量首次达到该节点时：
- 记录数字
1； - 若该节点为叶节点，将额定记录该叶节点的数值；
- 记录数字
- 若存在未达到的子节点，则选取未达到的一个子节点（优先选取左子节点）进入；
- 若无子节点或所有子节点均达到过，此时记录
9，并回到以后节点的父节点（若存在）。
如果最终记下的数依序连接成一个整数 num，满足 num mod p= target，则视为解开谜题。
请问有多少种二叉树的组装计划，能够使得最终记录下的数字能够解开谜题
留神：
- 两棵构造不同的二叉树，作为不同的组装计划
- 两棵构造雷同的二叉树且存在某个雷同地位处的宝石编号不同，也作为不同的组装计划
- 可能存在数值雷同的两颗宝石
输出：gem = [2,3]
p = 100000007
target = 11391299
输入：1输出：gem = [3,21,3]
p = 7
target = 5
输入：4数据范畴
1 <= gem.length <= 9
0 <= gem[i] <= 10^9
1 <= p <= 10^9，保障
p 为素数。0 <= target < p
存在 2 组 gem.length == 9 的用例问题剖析
参考大佬题解：hqztrue