leetcode 周赛 494

零、背景

这次比赛稍微有点难度。
第三题第一感觉是线性基，但是发现也可以使用背包解决。
第四题很容易想到后缀或或者前缀或，但是需要二分，稍微麻烦一些。

本场题型概览如下。
A 题：贪心。
B 题：贪心。
C 题：背包。
D 题：前缀或二分。

一、构造奇偶一致的数组 I

题意：给一个数组，每个下标选择下面的其中一个操作，问是否可以得到一个新的数组，满足所有值都是奇数或者偶数。
操作1：不变。
操作2：与原数组其他下标的值相减。

思路：固定为 true。

逻辑：假设存在一个奇数，则其他偶数都减去这个奇数，则偶数都会变成奇数，满足要求。

二、构造奇偶一致的数组 II

题意：与题目一一样，操作规则发生变化。
操作1：不变。
操作2：与数组其他下标的值相减，但是减数需要小于被减数，即得到的答案需要是正整数。

思路：贪心

还是题目一的贪心方法，不过需要满足最小的奇数小于最小的偶数，即可把所有数字变成奇数。

可以证明，存在奇数时，无法把奇数变成偶数，因为最大的奇数只有减去奇数才能得到偶数，但是题目限制不能减去自己。

三、达到目标异或值的最少删除次数

题意：给一个数组和 target 目标数字，可以任意移除一些数字，问最少移除多少个数字，才能使得剩余的数字的异或值等于 target。

思路：背包

值域范围是 10^4，可以当做背包，计算得到每个值需要的最小数字。

状态定义：pack[V] 前缀得到值域 V 的最小数字个数，INF 代表没答案。
状态转移方程：pack[V] = min(pack[V], pack[V^v] + 1)

顺序对 V 进行异或，得到的 V^v 没有线性关系，所以每次无法复用原先的背包，需要使用滚动数组。

复杂度：O(n V)

四、统计好子数组

题意：给一个数组，问存在多少个子数组，满足子数组的或值也在子数组中。

思路：后缀或

子数组问题，肯定是枚举左端点或者右端点，判断有多少个满足答案。

假设枚举的是右端点，则基于这个右端点的后缀或值是一个单调不减序列（方向超左）。
由于是或运算，只有某个比特位从 0 变为 1 时后缀或值才会变大。
所以最多变大 31 次。

故可以把这些变化的区间都维护起来，然后分别判断是否存在好数组，以及计算满足好数组的区间即可。

假设已经计算上个位置的所有区间了（最多不超过32个），怎么计算下个位置的所有区间呢？
答案是暴力用下个位置的值与这些区间进行或运算，然后再对区间进行合并即可。
每次暴力计算复杂度 O(32)

有了固定或值的区间，接下来需要判断这个区间是否存在好数组。

这个需要提前预处理所有值对应的下标列表。
假设这个区间的后缀或值都是 V。
这样使用 V 找到下标列表，然后进行二分，判断区间 [l,r] 作为左边界范围，是否存在值 V 对应的下标。

这里需要注意的是，如果存在时，并不是整个 [l,r] 的子数组都是答案。

例如小于等于 r 的最后一个满足的下标是 r-3。
则 [r-2,r] 这些左边界都不是好数组，因为这些子数组中没有元素 V。

所以，正确的二分应该是寻找 [l,r] 内最后一个满足的下标 p， [l,p] 都是答案。
这个可以使用 upper_bound(r)-1 来找到最后一个。

复杂度：O(n log(n) log(n))

优化：既然要找 V 最后出现的位置，循环时直接使用 hash 动态维护这个位置即可。
复杂度：O(n log(n))

五、最后

这次比赛其实挺有难度的。
第四题需要先发现所有后缀或的单调性与变化区间，然后推导出上个位置怎么计算下个位置的区间，最后还需要判断区间的后缀或值是否在子数组中。
说实话，后面两个要求挺高的。

《完》。

-EOF-

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