leetcode 第 393 场算法比赛

零、背景

这次比赛题目不难，不过代码量大一些。
比赛的时候，leetcode 网站挂了，另外，我最后一题被卡内存了，算法没修改，都是数组的定义的调整，优化了几个小时，最后才通过。

A: 模拟题，我通过从大到小来枚举判断，会变得简单一些。
B: 素数，套模版即可。
C: 容斥，套模版即可。
D: 动态规划+二分查找+线段树，代码量比较大。

排名：无
代码地址： https://github.com/tiankonguse/leetcode-solutions/tree/master/contest/3/393

一、替换字符可以得到的最晚时间

题意：给一个时间字符串，某些位置是问号，问最大的合法时间。

思路1：依次判断每一位的最大合法值，代码量比较大。

思路2：依次从大到小枚举小时和分钟，判断是否匹配，找到匹配的第一个值即可。

二、单面值组合的第 K 小金额

题意：给一个数组，问素数值的最大间距。

思路：找到最前面和最后面的素数，求差即可。

素数模板: https://github.com/tiankonguse/leetcode-solutions/blob/master/doc/prime.cpp

三、单面值组合的第 K 小金额

题意：给 n 个数字，问第 k 个可以整除某个数字的值。

思路：容斥原理。
复杂度：O(2^n)

优化：如果一个数字是另一个数字的倍数，较大的显然没啥用。
消除多余的倍数，数字可以从 25 个降低到 11 个。

容斥模板：https://github.com/tiankonguse/leetcode-solutions/blob/master/doc/rongchi.cpp

四、划分数组得到最小的值之和

题意：给一个数组，问是否可以将数组拆分为 m 个连续子数组，每个子数组所有元素与运算后与目标数组值一致。
如果可以，求子数组最后一个值之和的最小值。

思路：很容易想到动态规划。

状态定义：dp(n,m) 前 n 个数组分成 m 个子数组的最优解。
状态转移方程：dp(n,m) = min(dp(i,m-1)+val[i+1,n]), 1<=i<=n
复杂度：O(m*n^2)

固定后缀位置的数组，前面加的元素越多，与运算的结果越小。
所以，状态转移的这些所有数组，可以分为连续的三部分[0,a,b,n]：

1）[b+1,n],与运算的结果比目标值的 bit 1 多，需要继续在前面添加元素。
2）[a,b],与运算的结果与目标值相等
3）[0,a-1] 与运算的结果某些位是0，目标值是1，不满足要求。

根据题目要求，只有第二部分才是合法的状态。
这里可以通过二分来快速找到第二部分的边界，复杂度O(log(n))。

接下来需要计算出这个区间内所有子状态的最小值答案。
区间最值，典型的线段树查询问题。
所以状态值可以储存在线段树中，复杂度O(log(n))

其实还有一个小问题：二分的时候，怎么判断一个值处于哪一区间呢？
这需要分析最后一个数字与目标值所有 Bit 的关系。

分为四种情况：

目标值为 0，后缀值为 0：所有前缀都合法
目标值为 0，后缀值为 1：需要找到一个0，0 前面的所有子数组都合法
目标值为 1，后缀值为 0：没有答案
目标值为 1，后缀值为 1：需要找到一个0， 0 后面的所有子数组都合法

根据上面的四种情况，可以发现，两种情况可以直接得到结果，两种情况需要判断子数组中是否有0。
所以需要预处理出每个bit位的前缀数组中 0 的个数，然后通过区间求差，即可判断区间内是否有 0 值。

综合复杂度：O(n * m * log(n) * log(V))

线段树模板： https://github.com/tiankonguse/leetcode-solutions/blob/master/doc/seg.cpp

五、最后

这次比赛最后一题是好题，但是数据有问题，被卡内存和卡常数了。

我把线段树模版中无关的储存全部删除，long 全部换成 int, vector 全部换成数组，最后才通过。

《完》

-EOF-

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