第 231 场周赛题解

Q1 1784. 检查二进制字符串字段 (opens new window)

感觉题目翻译的有歧义，反正题意就是所有的$1$都要挨在一起，不能用$0$隔开。

class Solution1784 {
    fun checkOnesSegment(s: String): Boolean {
        val l = s.indexOfFirst { it == '1' }
        val r = s.indexOfLast { it == '1' }
        return (l..r).all { s[it] == '1' }
    }
}

Q2 1785. 构成特定和需要添加的最少元素 (opens new window)

这题恶心在要用$Long$转一下，不然会溢出... WA了一次...

还有就是一个向上取整的小技巧，加一个$limit - 1$之后再除以$limit$。

import kotlin.math.abs

class Solution5698 {
    fun minElements(nums: IntArray, limit: Int, goal: Int): Int {
        var sum: Long = 0
        val g = goal.toLong()
        nums.forEach {
            sum += it
        }
        return ((abs(sum - g) + limit - 1) / limit).toInt()
    }
}

Q3 1786. 从第一个节点出发到最后一个节点的受限路径数 (opens new window)

这道题比较绕，前后分成两个部分。

1. 首先通过$Dijkstra$计算出各个节点距离最后一个点的距离（这里要注意使用堆优化的，如果开$O(n^2)$的对于Kotlin会爆内存...
2. $DFS$求解出从起始节点到终止节点有多少路径（这里也可以用上述结果排序后$DP$求解）

class Solution1786 {
    fun countRestrictedPaths(n: Int, edges: Array<IntArray>): Int {
        val mod = 1000000007L
        val graph = Graph(n + 1)
        edges.forEach {
            graph.addEdge(it[0], it[1], it[2])
        }
        val dis = graph.dijkstra(n)
        val seen = HashMap<Int, Long>()
        fun dfs(node: Int): Long {
            if (node in seen) return seen[node]!!
            if (node == 0) return 0L
            if (node == n) return 1L
            var ans = 0L
            graph.adj[node].forEach {
                if (dis[it] < dis[node]) {
                    ans += dfs(it)
                    ans %= mod
                }
            }
            return ans.also {
                seen[node] = it
            }
        }
        return (dfs(1) % mod).toInt()
    }
}

class Graph(val n: Int) {

    // 图中边（可以有方向）
    var adj: Array<LinkedList<Int>> = Array(n) { LinkedList<Int>() }

    // 图中边的权重（可以有方向）
    val weight = HashMap<Int, HashMap<Int, Int>>()

    init {
        for (i in 0 until n) {
            weight[i] = hashMapOf()
        }
    }

    fun addEdgeOri(i: Int, j: Int, w: Int = 0) {
        adj[i].add(j)
        weight[i]!![j] = w
    }

    fun addEdge(i: Int, j: Int, w: Int = 0) {
        // Add w to v's list.
        adj[i].add(j)
        // Add v to w's list
        adj[j].add(i)
        weight[i]!![j] = w
        weight[j]!![i] = w
    }
}

/**
 * 堆优化Dijkstra 单源最短路径
 * @param source 源点(0..n-1)
 * */
fun Graph.dijkstra(source: Int): IntArray {
    // 距离source的最短路径
    val ans = IntArray(n) { Int.MAX_VALUE / 2 }
    val pq = PriorityQueue<Pair<Int, Int>>(compareBy { it.second })
    pq.offer(Pair(source, 0))
    while (pq.isNotEmpty()) {
        val (item, dis) = pq.poll()
        if (ans[item] <= dis) continue
        ans[item] = dis
        this.adj[item].forEach {
            if (ans[it] >= Int.MAX_VALUE / 2)
                pq.offer(Pair(it, dis + weight[item]!![it]!!))
        }
    }
    return ans
}

Q4 1787. 使所有区间的异或结果为零 (opens new window)

本题非常有意思，又涨知识了！

假设列表为${a_1,a_2,a_3,b_1,b_2,b_3,c_1,c_2,c_3}$，我们可知要修改的最终状态为使得$a_1\oplus a_2\oplus a_3 == 0$ && $a_2\oplus a_3\oplus b_1 == 0$。根据异或的运算规则可知，$a_1 == b_1$，轮询推导后会发现$a_1 == b_1 == c_1$，$a_2 == b_2 == c_2$...

这样我们只需要求出一组的解即可，即一份$a_1、b_1、c_1$。

看数据范围为$0 < nums[i] < 2^{10}$，通过异或规则可知，无论怎么异或都不会超出这个范围。

下面需要使用$DP$来求解。

1. 首先将$n$个数字按$k$的余数分组，即一组内的数字最终要变成同一个数。（这里要注意，可能存在非整除的情况，每一组的个数不一定相同）
2. $dp[n][m]$代表，选择完前$n+1$个数，使得总异或值为$m$的最小代价
3. $dp[k - 1][0]$即最终所求答案

关于状态转移方程，当前$index$若为$0$，则总异或值就是自己的值，只需要计算该组不是该值的数量

$$dp[0][j] = group[0].sum() - group[0][j]$$

若当前$index$不为$0$，需要利用前项数据来计算，而无法直接计算$dp[i][j]$

$$dp[i][pre \oplus key] = min \left\{dp[i][pre \oplus key] group[i].sum() - group[i][key]\right\}$$

通过上述公式可以看出，若$key$不在当前纵列当中，则遍历的值都是相同的，可以降低时间复杂度。

每向后遍历一个数字时，先将$dp[i]$的值都用$min\left\{dp[i - 1]\right\} + group[i].sum()$填充，代表当前列的值随意改，肯定能保证得出任意异或值的结果。通过这个方法可以将时间复杂度从$O(k * 1024^2)$ 降低为 $O(k * 1024)$。

class Solution1787 {
    fun minChanges(nums: IntArray, k: Int): Int {
        val group = Array<HashMap<Int, Int>>(k) { hashMapOf() }
        for (i in nums.indices) {
            val value = nums[i]
            group[i % k][value] = group[i % k].getOrDefault(value, 0) + 1
        }
        val max = 1024
        val dp = Array<IntArray>(k) { IntArray(max) }
        for (i in 0 until k) {
            val sum = group[i].values.sum()
            if (i == 0) {
                for (j in 0 until max) {
                    dp[i][j] = sum - group[i].getOrDefault(j, 0)
                }
            } else {
                dp[i].fill(dp[i - 1].min()!! + sum)
                group[i].forEach { (key, value) ->
                    for (pre in 0 until max) {
                        dp[i][pre xor key] = minOf(dp[i][pre xor key], dp[i - 1][pre] + sum - value)
                    }
                }
            }
        }
        return dp[k - 1][0]
    }
}