赛事活动｜[第366场周赛]喵星人的解题报告

815

2023.10.08

发布于未知归属地

大家好，这里是喵星人的解题报告。
今天的周赛，T3又是偏难的Medium，T4是偏简单的Hard，赛时看AC的人数两题也是差不多。

Python3

class Solution:
    def differenceOfSums(self, n: int, m: int) -> int:
        return sum(i for i in range(1, n + 1) if i % m) - sum(i for i in range(1, n + 1) if i % m == 0)

100085. 最小处理时间
T2读题题，注意到题目要求是每一个核心执行一个任务，即n*4个任务需要给到每一个核心执行，所以贪心即可，把最长执行时间的任务给最早开始的处理器核心。

Python3

class Solution:
    def minProcessingTime(self, processorTime: List[int], tasks: List[int]) -> int:
        # tasks升序排列
        tasks.sort()
        # processor降序排列
        processorTime.sort(reverse = True)
        ans = 0
        for i in range(3, len(tasks), 4):
            ans = max(ans, processorTime[i // 4] + tasks[i])
        return ans

8028. 执行操作使两个字符串相等
T3我用的区间DP解法，整体时间复杂度 $O (n^{2})$ ，赛后金金提示，其实线性DP即可，因为操作两边再操作中间，不可能更优。
我们注意到每次操作会改变s1的两个位置，所以s1和s2不相等的位置数一定要是偶数，否则无解。
求出所有不相等的位置后，如果两个位置j == i + 1，则我们可以用操作二，代价是1，否则我们可以选择使用操作一，代价是x，或者使用j - i次操作二，代价是j - i。
至于整体代价，我们通过区间DP求解。

Python3

class Solution:
    def minOperations(self, s1: str, s2: str, x: int) -> int:
        idx = [i for i in range(len(s1)) if s1[i] != s2[i]]

        if not idx: # s1和s2完全相等
            return 0

        n = len(idx)
        if n & 1:   # 奇数个不相等的位置，无解
            return -1

        dp = [[math.inf] * n for _ in range(n)]
        for i in range(n - 1):
            dp[i][i + 1] = min(x, idx[i + 1] - idx[i])

        for L in range(4, n + 1, 2):
            for i in range(n - L + 1):
                j = i + L - 1
                # 从i到j的操作最小代价，有3种转移方式：
                # 1. 操作i到j - 2的代价，加上操作j - 1到j - 2的代价
                # 2. 或者操作i到i + 1的代价，加上i + 2到j的代价，
                # 3. 或者操作i + 1到j - 1的代价，再加上用操作一处理i和j的代价
                dp[i][j] = min(dp[i][j - 2] + dp[j - 1][j], dp[i][i + 1] + dp[i + 2][j], dp[i + 1][j - 1] + x)
        return dp[0][-1]

100087. 对数组执行操作使平方和最大
T4首先分析操作， $x, y = x & y, x ∣ y$ ， $(x & y) + (x ∣ y) == x + y$ ，所以无论如何操作，数组的总和是不变的。
然后分析如何使平方和最大，假设我们固定和为n的情况下， $n^{2} \geq (n - 1)^{2} + 1^{2} = n^{2} - 2 n + 2$ 。所以我们通过操作能得到越大的数，结果也就越大。
根据上面两个分析，我们可以按位统计所有1的数量，贪心的优先构造最大的数，然后求解。

Python3

class Solution:
    def maxSum(self, nums: List[int], k: int) -> int:
        MOD = 10 ** 9 + 7
        n = len(nums)

        # 先统计数组所有数字在每一个bit位上1的数量
        cnt = [0] * 31
        for x in nums:
            for bit in range(31):
                cnt[bit] += (x >> bit) & 1
        
        ans = 0
        for i in range(k):
            cur = 0
            # 贪心构造当前能得到的最大的数字
            for bit in range(31):
                if cnt[bit]:
                    cur |= 1 << bit
                    cnt[bit] -= 1
            if cur == 0: break
            ans = (ans + cur * cur) % MOD

        return ans

最后，式酱说题解结尾需要配图：