第 280 场周赛题解 (opens new window)

Q1 2169. 得到 0 的操作数 (opens new window)

硬模拟，可以用%运算加快。

class SolutionA {
    fun countOperations(num1: Int, num2: Int): Int {
        var a = num1
        var b = num2
        var ans = 0
        while (a != 0 && b != 0) {
            if (a >= b) a -= b
            else b -= a
            ans ++
        }
        return ans
    }
}

Q2 2170. 使数组变成交替数组的最少操作数 (opens new window)

最小替换好写，就是非要交替... 必须奇偶都保留最大和次大，然后再判断... 麻烦...

class SolutionB {
    fun minimumOperations(nums: IntArray): Int {
        val mapA = HashMap<Int, Int>()
        val mapB = HashMap<Int, Int>()
        for (i in nums.indices) {
            if (i % 2 == 0) {
                mapA[nums[i]] = mapA.getOrDefault(nums[i], 0) + 1
            } else {
                mapB[nums[i]] = mapB.getOrDefault(nums[i], 0) + 1
            }
        }

        var a0 = Pair(-1, 0)
        var a1 = Pair(-1, 0)
        mapA.forEach { t, u ->
            if (u > a0.second) {
                a1 = a0
                a0 = Pair(t, u)
            } else if (u > a1.second) {
                a1 = Pair(t, u)
            }
        }
        var b0 = Pair(-1, 0)
        var b1 = Pair(-1, 0)
        mapB.forEach { t, u ->
            if (u > b0.second) {
                b1 = b0
                b0 = Pair(t, u)
            } else if (u > b1.second) {
                b1 = Pair(t, u)
            }
        }

        var ans = nums.size
        if (a0.first != b0.first) {
            ans -= a0.second
            ans -= b0.second
        } else {
            ans = minOf(ans - a1.second - b0.second, ans - a0.second - b1.second)
        }
        return ans
    }
}

Q3 2171. 拿出最少数目的魔法豆 (opens new window)

排序之后，右侧的所有值变成与当前值一样时的总和，左侧全部丢弃，当前值不变。此时的总和与原本的总和差，就是要拿出的数目。求最小值即可。

又被Long坑了一次... 算原始和的时候记着了，下面算乘法的时候又漏了...

class SolutionC {
    fun minimumRemoval(beans: IntArray): Long {
        var sum = 0L
        beans.forEach {
            sum += it
        }
        beans.sort()
        var ans = sum
        for (i in beans.indices) {
            ans = minOf(ans, sum - (beans.size - i).toLong() * beans[i])
        }
        return ans
    }
}

Q4 2172. 数组的最大与和 (opens new window)

简单的状态压缩，差2min没AC... DFS需要很多细节优化（记忆化的Key用String就超时了... 换成3进制Int就过了...）。

以后尽量用DP来处理！

class SolutionD {
    fun maximumANDSum(nums: IntArray, numSlots: Int): Int {
        var ans = 0
        val dp = IntArray(1 shl numSlots * 2)
        for (i in dp.indices) {
            val c = Integer.bitCount(i)
            if (c >= nums.size) continue
            for (j in 0 until numSlots * 2) {
                if (i and (1 shl j) == 0) {
                    val k = i or (1 shl j)
                    dp[k] = maxOf(dp[k], dp[i] + ((j / 2 + 1) and nums[c]))
                    ans = maxOf(ans, dp[k])
                }
            }
        }
        return ans
    }
}