力扣第 468 场周赛

775
Contest
LeetCode
本文最后更新于 3 分钟前，文中所描述的信息可能已发生改变。

3688. 偶数的按位或运算 - 力扣（LeetCode） ​

题目类型 ​

#遍历

解题思路 ​

参考：这道题很简单！

示例代码 ​

python
class Solution:
    def evenNumberBitwiseORs(self, nums: List[int]) -> int:
        ans = 0
        for x in nums:
            if x % 2 == 0:
                ans |= x
        return ans

3689. 最大子数组总值 I - 力扣（LeetCode） ​

题目类型 ​

#脑经急转弯

解题思路 ​

参考：这道题很简单！

示例代码 ​

python
class Solution:
    def maxTotalValue(self, nums: List[int], k: int) -> int:
        return (max(nums) - min(nums)) * k

3690. 拆分合并数组 - 力扣（LeetCode） ​

题目类型 ​

#哈希 #BFS

解题思路 ​

根据数据范围，至多有  6!=720  个不同的排列，这很小，考虑暴力。

参考：BFS + 暴力枚举（Python/Java/C++/Go）

示例代码 ​

python
class Solution:
    def minSplitMerge(self, nums1: List[int], nums2: List[int]) -> int:
        n = len(nums1)
        memo = {tuple(nums1)}
        q = [nums1]
        for ans in count(0):
            tmp = q
            q = []
            for nums in tmp:
                if nums == nums2:
                    return ans
                for i in range(n):
                    for j in range(i + 1, n + 1):
                        m = j - i
                        a = nums[: i] + nums[j:]
                        for k in range(n - m + 2):
                            if k == i:
                                continue
                            b = a[: k] + nums[i: j] + a[k: ]
                            c = tuple(b)
                            if c not in memo:
                                memo.add(c)
                                q.append(b)

3691. 最大子数组总值 II - 力扣（LeetCode） ​

题目类型 ​

#堆 #线段树 #ST表

解题思路 ​

数组的最值一定被子数组包含，所以可以从数组到子数组进行枚举，同时使用数据结构计算子数组最值之差，并采用堆维护当前最大值。

参考：ST 表 + 最大堆（Python/Java/C++/Go）

示例代码 ​

python
class Solution:
    def maxTotalValue(self, nums: List[int], k: int) -> int:
        n = len(nums)
        h = []
        mxt = SparseTable(nums, max)
        mnt = SparseTable(nums, min)

        def query(l: int, r: int) -> int:
            return mxt.query(l, r) - mnt.query(l, r)

        for i in range(n):
            heappush(h, (-query(i, n - 1), i, n - 1))

        ans = 0
        while k:
            k -= 1
            x, l, r = heappop(h)
            ans -= x
            if l == r:
                continue
            s = query(l, r - 1)
            heappush(h, (-s, l, r - 1))
        return ans
python
min = lambda a, b: b if b < a else a
max = lambda a, b: b if b > a else a

def op(a: Tuple[int, int], b: Tuple[int, int]) -> Tuple[int, int]:
    return min(a[0], b[0]), max(a[1], b[1])

class ST:
    def __init__(self, a: List[int]):
        n = len(a)
        sz = n.bit_length()
        st = [[None] * sz for _ in range(n)]
        for i, x in enumerate(a):
            st[i][0] = (x, x)
        for j in range(1, sz):
            for i in range(n - (1 << j) + 1):
                st[i][j] = op(st[i][j - 1], st[i + (1 << (j - 1))][j - 1])
        self.st = st

    # [l, r) 左闭右开
    def query(self, l: int, r: int) -> int:
        k = (r - l).bit_length() - 1
        mn, mx = op(self.st[l][k], self.st[r - (1 << k)][k])
        return mx - mn


class Solution:
    def maxTotalValue(self, nums: List[int], k: int) -> int:
        n = len(nums)
        st = ST(nums)
        h = [(-st.query(i, n), i, n) for i in range(n)]
        heapify(h)

        ans = 0
        for _ in range(k):
            x, l, r = h[0]
            if x == 0:
                break
            ans -= x
            heapreplace(h, (-st.query(l, r - 1), l, r - 1))
        return ans
py
from functools import reduce
from math import lcm, gcd
from operator import or_, and_


class SparseTable:
    def __init__(self, lst, fun):
        """static range queries can be performed as long as the range_merge_to_disjoint fun satisfies monotonicity"""
        n = len(lst)
        self.bit = [0] * (n + 1)
        self.fun = fun
        self.n = n
        for i in range(2, n + 1):
            self.bit[i] = self.bit[i >> 1] + 1
        for i in range(n+1):
            assert self.bit[i] == (i.bit_length() - 1 if i else i.bit_length())
        self.st = [[0] * n for _ in range(self.bit[-1] + 1)]
        self.st[0] = lst
        for i in range(1, self.bit[-1] + 1):
            for j in range(n - (1 << i) + 1):
                self.st[i][j] = fun(self.st[i - 1][j], self.st[i - 1][j + (1 << (i - 1))])

    def query(self, left, right):
        """index start from 0"""
        assert 0 <= left <= right < self.n
        pos = self.bit[right - left + 1]
        return self.fun(self.st[pos][left], self.st[pos][right - (1 << pos) + 1])

    def bisect_right(self, left, val, initial):
        """index start from 0"""
        assert 0 <= left < self.n
        # find the max right such that st.query(left, right) >= val
        pos = left
        pre = initial  # 0 or (1<<32)-1
        for x in range(self.bit[-1], -1, -1):
            if pos + (1 << x) - 1 < self.n and self.fun(self.st[x][pos], pre) >= val: # can by any of >= > <= <
                pre = self.fun(self.st[x][pos], pre)
                pos += (1 << x)
        # may be pos=left and st.query(left, left) < val
        if pos > left:
            pos -= 1
        else:
            pre = self.st[0][left]
        assert left <= pos < self.n
        return pos, pre

    def bisect_right_length(self, left):
        """index start from 0"""
        assert 0 <= left < self.n
        # find the max right such that st.query(left, right) < right-left+1
        pos = left
        pre = 0
        for x in range(self.bit[-1], -1, -1):
            if pos + (1 << x) - 1 < self.n and self.fun(self.st[x][pos], pre) > pos + (1 << x) - left:
                pre = self.fun(self.st[x][pos], pre)
                pos += (1 << x)
        if pos == left and self.st[0][pos] == 1:
            return True, pos
        if pos < self.n and self.fun(pre, self.st[0][pos]) == pos + 1 - left:
            return True, pos
        return False, pos
力扣第 166 场双周赛
Codeforces Round 1051 (Div. 2)