力扣第 165 场双周赛

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

3678. 大于平均值的最小未出现正整数 - 力扣（LeetCode） ​

题目类型 ​

#遍历 #哈希

解题思路 ​

参考：这道题很简单！

示例代码 ​

python
class Solution:
    def smallestAbsent(self, nums: List[int]) -> int:
        vis = set(nums)
        ans = max(sum(nums) // len(nums) + 1, 1)
        while ans in vis:
            ans += 1
        return ans

3679. 使库存平衡的最少丢弃次数 - 力扣（LeetCode） ​

题目类型 ​

#哈希 #定长滑窗

解题思路 ​

参考：定长滑动窗口（Python/Java/C++/Go）

示例代码 ​

python
class Solution:
    def minArrivalsToDiscard(self, arrivals: List[int], w: int, m: int) -> int:
        cnt = defaultdict(int)
        ans = 0
        for i, x in enumerate(arrivals):
            if cnt[x] == m:
                arrivals[i] = 0
                ans += 1
            else:
                cnt[x] += 1

            l = i + 1 - w
            if l >= 0:
                cnt[arrivals[l]] -= 1
        return ans

3680. 生成赛程 - 力扣（LeetCode） ​

题目类型 ​

#构造

解题思路 ​

按差值 d = 1, 2, …, n - 1， 能够构造所有比赛组合，除 d = 1 和 d = n - 2 外，枚举构造即可满足条件。主要考虑两种特殊情况的连接方式。

方法一

当 n 为偶数时，会出现连续参赛队伍出现，如 d = 1 时，排列可以为 (0, 1), (2, 3), (4, 5), (1, 2), (3, 4), (5, 0)，但是与 d = 2 直接连接不满足条件，0 连续出现，可以交换 (3, 4) 和 (5, 0)。

另外考虑 d = n - 1 时的排序，由于 d = n - 2 最后一项为 (n - 1, n - 3)，故考虑从奇数队伍开始错开，如 (1, 0)。同理直接连接也不满足条件，如 (1, 0), (3, 2), (5, 4), (0, 5), (2, 1), (4, 3，同理交换 (3, 2) 和 (5, 4) 以满足条件。

方法二

让 d = 1 和 d = n - 1 的比赛组合排列，需要错开枚举开始的队伍，如 d = 1 从 0 开始，d = n - 1 从 n - 1 开始，就能够完美满足条件，最后将构造的排列接到 d = n - 2 后即可。

参考：构造题（Python/Java/C++/Go）

示例代码 ​

python
class Solution:
    def generateSchedule(self, n: int) -> List[List[int]]:
        if n <= 4:
            return []
        ans = []
        for i in range(0, n, 2):
            ans.append((i, (i + 1) % n))
        for i in range(1, n, 2):
            ans.append((i, (i + 1) % n))
        if n % 2 == 0:
            ans[-1], ans[-2] = ans[-2], ans[-1]

        for d in range(2, n - 1):
            for i in range(n):
                ans.append((i, (i + d) % n))

        for i in range(1, n, 2):
            ans.append((i, (i - 1) % n))
        if n % 2 == 0:
            ans[-1], ans[-2] = ans[-2], ans[-1]
        for i in range(0, n, 2):
            ans.append((i, (i - 1) % n))

        return ans
python
class Solution:
    def generateSchedule(self, n: int) -> List[List[int]]:
        if n <= 4:
            return []

        ans = []
        for d in range(2, n - 1):
            for i in range(n):
                ans.append((i, (i + d) % n))
        for i in range(n):
            ans.append((i, (i + 1) % n))
            ans.append(((i - 1) % n, (i - 2) % n))
        return ans

3681. 子序列最大 XOR 值 - 力扣（LeetCode） ​

题目类型 ​

#线性基 #位运算 #数学

解题思路 ​

题意简化，计算数组中一个子序列异或和的最大值，直接套用模板即可。

参考：【模板】线性基（Python/Java/C++/Go）

示例代码 ​

python
class Solution:
    def maxXorSubsequences(self, nums: List[int]) -> int:
        xb = XorBasis(32)
        ans = max(nums)
        for x in nums:
            xb.insert(x)
            ans = max(ans, xb.max_xor())
        return ans
py
class XorBasis:
    # n 为值域最大值 U 的二进制长度，例如 U=1e9 时 n=30
    def __init__(self, n: int):
        self.b = [0] * n

    def insert(self, x: int) -> None:
        b = self.b
        # 从高到低遍历，保证计算 max_xor 的时候，参与 XOR 的基的最高位（或者说二进制长度）是互不相同的
        for i in range(len(b) - 1, -1, -1):
            if (x >> i):  # 由于大于 i 的位都被我们异或成了 0，所以 x >> i 的结果只能是 0 或 1
                if b[i] == 0:  # x 和之前的基是线性无关的
                    b[i] = x  # 新增一个基，最高位为 i
                    return
                x ^= b[i]  # 保证每个基的二进制长度互不相同
        # 正常循环结束，此时 x=0，说明一开始的 x 可以被已有基表出，不是一个线性无关基

    def max_xor(self) -> int:
        b = self.b
        res = 0
        # 从高到低贪心：越高的位，越必须是 1
        # 由于每个位的基至多一个，所以每个位只需考虑异或一个基，若能变大，则异或之
        for i in range(len(b) - 1, -1, -1):
            if res ^ b[i] > res:  # 手写 max 更快
                res ^= b[i]
        return res
Codeforces Round 1051 (Div. 2)
力扣第 467 场周赛