leetcode 2023 春季团队赛题解

零、背景

这次比赛是和同事我们两个人一起打的。

总共 6 道题，最终做出 5 道题，排名 52。

比赛经过如下：

赛前，和同事约定，同事做 1、3、5题，我做 2、4、6题。

A：同事 3:50 做出来了。

B：我 12:00 做出来了。

C：同事感觉跑最短路可能会超时，说想用 SPFA 试一下，让我一起看下。
我看后发现确实可能会超时，但是我看了提的难度是 Medium，猜测直接暴力做就可以通过。
本来我想写暴力程序的，同事说他在写 SPFA 了，我可以先做下一题。
于是这道题就交给同事了，1:11:25 通过。

D：这道题我看了发现不难，准备敲代码时和同事去看 C 题去了。后来又回来敲代码，1:03:11 通过。

E：由于同事还在做第 C 题，于是我做这个奇数题。
通过纸上画图，找出了规律，发现可以使用线段树来做，2:12:57 通过。

F：同事 1:11:25 通过 C 后就开始做这道题了。
同事写了一个暴力，发现 9 跑不出来。
赛后研究第一名的代码，最终理解了大概思路：需要折办预处理+暴力来做才行。
感觉最后一题的难度与前五题相差很大，再给我们一个小时，我们也做不出来。

代码地址：
https://github.com/tiankonguse/leetcode-solutions/tree/master/other/season/2023-spring/term

下面看下这六道题的题解吧。

一、符文储备

题意：给一个数组，问最多可以选多少个元素，可以使得重排序后，相邻元素的差值不大于 1。

思路：经典的最简单的动态规划题。

先排序，然后循环跑一遍状态转移即可。

状态转移方程：如果当前值与上个值差值不大于1，则当前值的统计值在上个统计值的基础上加 1，否则当前值的统计值重置为 1。

二、城墙防线

思路：给一些无交集的区间，每个区间可以向两侧延伸。
每个区间向两侧延伸的总长度都为 k。
求最大的 K，使得区间无交集。

思路：既然是求最大值，显然是二分 k 了。
确定 K 后，贪心扫描判断是否合法。

三、提取咒文

题意：给一个字符串矩阵和一个路径字符串。
在矩阵上求一个路径，使得路径为输入的路径字符串，但是路径的代价最小。
代价：从一个坐标移动到另外一个坐标的代价是曼哈顿距离，选择字母的代价是 1。

思路：起初想的是记录每个字符的坐标集合，求出从一个字母到另外一个字母的集合叉积，感觉会超时。

赛后看了第一名的代码，发现可以构造一个三维的图，然后 BFS 求最短路即可。
三维图解释：每一层是一个矩阵，匹配一个字母进入下一层矩阵；同一层矩阵内通过上下所有来 BFS 遍历矩阵。
复杂度：O(100^3)

四、生物进化录

题意：给一个有根树，从根节点遍历树时，进入儿子记录为0，返回父节点记录为1，遍历完后可以得到一个遍历序列。
求字典序最小的遍历序列。

思路：由于进入儿子得到一个0，可以证明，访问的第一个儿子肯定是子树高度最高的儿子，这样连续的 0 最多。

当然，我直接暴力计算出所有子树的答案，进行排序，从而计算出当前树的答案。

五、与非的谜题

题意：给一个数组，有两个操作。
操作1：修改数组某个下标的值。
操作2：数字 y 与整个数组进行 NAND 操作，进行 x 次，求之后的值。
NAND 操作：与操作后取非。

思路：先分析 NAND 操作，如下：

0 NAND 0 = 1
0 NAND 1 = 1
1 NAND 0 = 1
1 NAND 1 = 0

根据上面的运算性质，可以得到个规律：

为了简化，a NAND b NAND c 记为 abc

规律1：01 前面有其他数字时，答案固定为 0。

01 = 1
x01 = 0
xx01 = 0
xxx01 = 0

规律2：01前面有数字时，后面有连续若干个 1，答案与 1 的奇偶性有关。

x01=0
x011=1
x0111=0
x01111=1

规律3：01前面没有数字时，答案与规律2类似，但是答案相反。

01 = 1
011 = 0
0111 = 1
01111 = 0

规律4：全是 1 时，答案与 1 的奇偶性相关。

1 = 1
11 = 0
111 = 1
1111 = 0

有了上面这四个规律，就可以使用线段树或者树状数组做这道题了。

答案告诉我们，数字的二进制位数是 K 位，所以可以维护 K 个树状数组，分别记录每个数字每一位的二进制值。

修改操作时，先删除对应的旧值（K 个树状数组对应位置全部置0），然后设置新值。

询问操作时，K 位分别计算。
对于每一位，先查询树状数组是否是全 1 或者全 0，是了直接套用上面统计的规律计算出答案。
如果同时存在 0 与 1，二分求出最大的区间 [l, n]，使得这个区间都是 1。
这样就可以统计出 0 后面有多少个 1 了，套用上面统计的规律即可。

六、万灵之树

题意：n 个宝石当做二叉树的叶子节点，n-1个石头当做二叉树的非叶子节点，求满足要求的二叉树的访问序列的取模值等指定值的个数。

思路：二叉树的个数是卡特兰数，同事计算有 f(9)=1450 种。
宝石的顺序是排列组合，共有 A(9)=362880
暴力计算的复杂度就是 f(9)*A(9)=5*10^8，显然会超时。

针对这个结局，我和同事都没有啥好的方法。
我一直在想，能不能通过状态压缩，减少重复状态，但是没想到啥好的方法。

赛后看了第一名的代码，很巧妙，通过折半计算的方法来压缩状态，然后使用折半来搜索，从而把复杂度降下来。

例如通过将 5 以内的子树答案都暴力计算出来，这样的宝石有 A(9,5)种。
对于每种，计算所有卡特兰数 f(5)。
综合复杂度就是A(9,5) * f(5)，共有 211680 个状态值。

之后还是对 f(9)*A(9) 进行暴力搜索，不过一旦搜索到 5 以内，即快速查询离线计算好的答案。

由于每次有一半的数据都是计算好的，所以复杂度粗略估计是开一个根号，所以就不会超时了。

复杂度应该比根号大，你能计算出具体的复杂度吗？

七、最后

回头看下这次比赛。
第三题想到三维图的话就很简单，不然的话会有点难。
第四题我是暴力储存所有儿子答案排序的，竟然没超时。
第五题维护 k 个树状数组。
第六题暴力会超时，折半储存折半搜索，很有启发性的一种算法。

你参加这次比赛了吗？
做出了几道题？
都是怎么做的？
有遇到什么问题吗？

《完》

-EOF-

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