leetcode 2022年春季个人赛题解

零、背景

今天是 leetcode 2022年春季个人赛。

总共五道题，我做出了前四道，第五题是图论题，我不会，最终排名 85。

实际上，我不仅不会图论，还不会数学几何。

大学参加 ACM 的时候，三个人组成一个团队一起比赛的。

我主要负责基本的数据结构，图论交给了 A 伙伴，数学几何交给了 B 伙伴，所以我就没有花时间去学习这两类算法。

后面有时间了，还是要多做点图论和数学几何的题，把这两类算法知识补回来。

下面来看下比赛的题解吧。

一、宝石补给

题意：给一个数组，然后若干操作。
每个操作是数组中其中一个位置，可以把一半的值加到另外一个位置（自身需要减去这一半值）。
求所有操作执行完后，数组中最大值与最小值的差值。

思路：按照题意进行操作，最后循环求最值相减即可。

二、烹饪料理

题意：有 5 种食材的数量，以及 n 道菜。
每道菜会分别使用5 种食材中的若干数量。
每道菜两个属性：饱腹感 与美味度。
在 饱腹感不小于指定值时，问怎么做菜才能美味度最大。

思路：

一开始看错题了，以为每道菜都可以做无数个，这样就是有限制的背包问题，但是维度太多。

后来发现，每道菜最多只能做一份， 那就简单的暴力枚举即可。

暴力枚举一份菜做与不做，递归求出所有合法情况，求最值。

三、二叉搜索树染色

题意：给一个节点值不重复的二叉树，现在对二叉树进行染色，默认颜色是蓝色。

1）值在 [x, y] 之间的节点，染成蓝色。
2）值在 [x, y] 之间的节点，染成红色。

问一系列染色之后，最终红色节点的个数。

思路：理解题意后，发现与二叉树没关系，只与值有关系。
所以先遍历树，得到所有的值。

之后，就可以是经典的线段树来做了。

由于节点值的范围很大，第一步先离散化到有限的连续区间。
第二步进行线段树区间更新。
最后线段树区间查询即可。

注意事项：由于需要延迟标记，0 代表是否有标记，所以可以使用值 1 代表红色，-1 代表蓝色。

扩展：实际上，这道题也可以使用线段区间的并与删除来解决。
由于之前我在这方面吃过亏，所以就不自己实现了，凡是区间问题，都使用线段树来做，简单点。

四、守护太空城

题意：有连续 n 个宇宙飞船排除一个直线。
现在陨石雨来了，某个时刻陨石会落在某个宇宙飞船上。

保护屏障有三个功能：

1）开启一个宇宙飞船的保护屏障，消耗 2 能量。
2）开启挨着的两个宇宙飞船的联合保护屏障，消耗 3 能量。
3）已开启的保护屏障，多维持一个时刻。

问最终最少消耗多少能量，才能保护飞船不受损。

思路：

一开始完全没思路，感觉状态会爆炸。
但是细看题意，发现数据范围的时间最多是 5，屏障最多也只能两两联合，那就有思路了。

这是典型的状态压缩动态规划题。

我们从后到前，枚举每个飞船在所有时刻开启屏障的情况。

状态定义：f(n, mask2, mask1)
n 代表前 n 个非常。
mask2 代表倒数第二个飞船尚未进行屏障保护的时间状态。
mask1 代表倒数第一个飞船尚未进行屏障保护的时间状态。

最多有 m 个时间，所有一个飞船共有 2^m-1 中保护状态。
例如，比特位值为 1 代表这个位置已经处于安全状态，0代表待处理状态。

我们按时间顺序枚举 mask1 的所有情况。

mask1 分三种情况：

1）第一个待保护的时间，没有陨石到达，则可以不开启屏障。
2）开启单屏障，枚举持续时间，直到下个时间处于保护状态或者时间结束。
3）与 mask2 开启联合屏障，枚举持续时间，直到某个时间处于保护状态或者时间结束。

三种情况最终取最优值即可。

五、夺回据点

题意：给一个图，求一个树，使得树的叶子节点权值和最小。

思路：没学过顶点覆盖，最小割啥的，没思路。

六、最后

这次比赛算是尽力了，最后一题给我多长时间都做不出来吧。

就这样了。

加油，算法人。

《完》

-EOF-

本文公众号：天空的代码世界
个人微信号：tiankonguse
公众号ID：tiankonguse-code