第 241 场周赛题解

Q1 1863. 找出所有子集的异或总和再求和 (opens new window)

上来被$Q1$重击，一直想着怎么数学方法，最后还是暴力能解决...

把$state$遍历，求出所有子集的$xor$，然后直接求和即可。

class Solution1863 {
    fun subsetXORSum(nums: IntArray): Int {
        val n = nums.size
        val arr = IntArray(1 shl n)
        for (i in 0 until (1 shl n)) {
            for (j in 0 until n) {
                if (i and (1 shl j) != 0) {
                    arr[i] = arr[i] xor nums[j]
                }
            }
        }
        return arr.sum()
    }
}

GeeksForGeeks (opens new window)上有$O(n)$级别的数学解法，通过组合分析发现，当前位的$1$ or $0$都会被计算$2^{n-1}$。因此将整体数字求或，然后乘上$2^{n-1}$即可。

class Solution1863 {
    fun subsetXORSum(nums: IntArray): Int {
        var bits = 0
        val n = nums.size
        for (i in 0 until n) bits = bits or nums[i]
        return bits * 2.0.pow(n - 1).toInt()
    }
}

Q2 1864. 构成交替字符串需要的最小交换次数 (opens new window)

这个一直想追求较短的代码书写方式，结果贡献了两个$WA$。

正常考虑$0,1$的数量，然后根据相同及差值小于$1$、大于$1$，分别分析即可。最终返回最小值（注意这里是判断与最终位置的不同点的数量，所以要除2）。

class Solution1864 {
    fun minSwaps(s: String): Int {
        fun check(ch: Char): Int {
            var ans = 0
            for (i in s.indices) {
                if (i % 2 == 0) {
                    if (s[i] != ch) ans++
                } else {
                    if (s[i] == ch) ans++
                }
            }
            return ans
        }

        val a0 = s.count { it == '0' }
        val a1 = s.count { it == '1' }
        if (a0 - a1 > 1 || a0 - a1 < -1) return -1
        var ans0 = Int.MAX_VALUE / 2
        if (a0 - a1 == 1 || a0 == a1) {
            ans0 = check('0')
        }
        var ans1 = Int.MAX_VALUE / 2
        if (a1 - a0 == 1 || a0 == a1) {
            ans1 = check('1')
        }
        return minOf(ans0 / 2, ans1 / 2)
    }
}

Q3 1865. 找出和为指定值的下标对 (opens new window)

没有什么营养的题，正常$a + b$即可。

class FindSumPairs(val nums1: IntArray, val nums2: IntArray) {

    private val map1 = HashMap<Int, Int>()
    private val map2 = HashMap<Int, Int>()

    init {
        nums1.forEach {
            map1[it] = map1.getOrDefault(it, 0) + 1
        }
        nums2.forEach {
            map2[it] = map2.getOrDefault(it, 0) + 1
        }
    }

    fun add(index: Int, `val`: Int) {
        map2[nums2[index]] = map2.getOrDefault(nums2[index], 0) - 1
        nums2[index] += `val`
        map2[nums2[index]] = map2.getOrDefault(nums2[index], 0) + 1
    }

    fun count(tot: Int): Int {
        var ans = 0
        map1.forEach { (v, c) ->
            ans += map2.getOrDefault(tot - v, 0) * c
        }
        return ans
    }

}

Q4 1866. 恰有 K 根木棍可以看到的排列数目 (opens new window)

可以逆向分析，从后向前填充内容。对于当前状态$(n, k)$，若最后一个位置填写剩余部分最大值，那么这里一定能被看到。可以转移到状态$(n-1,k-1)$。若这里填写的不是最大值，则该位置一定不会被看到。且这个位置填写前$n-1$个值的效果一样。因此会增加$(n - 1) * state(n-1,k)$个状态值。

根据上述内容，可以使用$DFS$加记忆化进行处理。

class Solution5762 {
    fun rearrangeSticks(n: Int, k: Int): Int {
        val mod = 1000000007L
        val fac = HashMap<Int, Long>()
        fac[1] = 1L
        for (i in 2..1000) {
            fac[i] = fac[i - 1]!! * i % mod
        }
        val seen = HashMap<String, Long>()
        fun dfs(i: Int, j: Int): Long {
            val key = "$i, $j"
            if (key in seen) return seen[key]!!
            if (i == j) return 1L
            if (j == 1) return fac[i - 1]!!
            var ans = 0L
            ans += dfs(i - 1, j - 1) % mod
            ans += (dfs(i - 1, j) % mod) * (i - 1) % mod
            return ans.also {
                seen[key] = it % mod
            }
        }
        return (dfs(n, k) % (mod)).toInt()
    }
}