第 250 场周赛题解

Q1 1935. 可以输入的最大单词数 (opens new window)

直接算就行，这就是$Kotlin$舒服的地方。

class Solution5161 {
    fun canBeTypedWords(text: String, brokenLetters: String): Int {
        return text.split(" ").count {
            it.all { it !in brokenLetters }
        }
    }
}

Q2 1936. 新增的最少台阶数 (opens new window)

算两个间距之间的差，再除$dist$。注意刚好整除的情况需要额外减一，直接通过原值减一来实现...

class Solution5814 {
    fun addRungs(rungs: IntArray, dist: Int): Int {
        var cur = 0
        var ans = 0
        for (rung in rungs) {
            ans += (rung - cur - 1) / dist
            cur = rung
        }
        return ans
    }
}

Q3 1937. 扣分后的最大得分 (opens new window)

比赛时直接$DFS$生做，时间复杂度是$O(m * m * n)$，会超时...

需要把第二层的计算时间复杂度压缩。利用左侧、右侧的性质，把上一行从左看、从右看的最大值列出来，然后每一个位置都取其最大值。

之前有题目也是利用左右两边开始的数组，可惜比赛时没想到... 吸取教训！

class Solution5815 {
    // 左侧、右侧数组
    fun maxPoints(points: Array<IntArray>): Long {
        val n = points.size
        val m = points[0].size

        var dp = points[0].map { it.toLong() }.toLongArray()
        for (i in 1 until n) {
            val next = LongArray(m)
            // 左侧最大值
            var lmax = 0L
            for (j in 0 until m) {
                lmax = maxOf(lmax - 1, dp[j])
                next[j] = maxOf(next[j], lmax)
            }
            // 右侧最大值
            var rmax = 0L
            for (j in m - 1 downTo 0) {
                rmax = maxOf(rmax - 1, dp[j])
                next[j] = maxOf(next[j], rmax)
            }
            for (j in 0 until m) {
                next[j] += points[i][j].toLong()
            }
            dp = next
        }

        return dp.max()!!
    }
}

Q4 1938. 查询最大基因差 (opens new window)

这道题很可惜了，题目一眼就看出来是用字典树+离线算法... 可惜之前没有处理字典树的删除操作... 结果每次新建树，会超时...

这次把字典树的删除操作补上，每一位记录当前的$cnt$值。新增的时候$cnt$加1，删除的时候$cnt$减一，然后进行$maxXor$判断的时候，该节点是否存在依赖其$cnt$是否为0。

class Solution5816 {
    fun maxGeneticDifference(parents: IntArray, queries: Array<IntArray>): IntArray {
        val map = HashMap<Int, ArrayList<Int>>()
        for (i in parents.indices) {
            map[parents[i]] = map.getOrDefault(parents[i], arrayListOf())
            map[parents[i]]!!.add(i)
        }

        val queryMap = HashMap<Int, ArrayList<Pair<Int, Int>>>()
        for (i in queries.indices) {
            queryMap[queries[i][0]] = queryMap.getOrDefault(queries[i][0], arrayListOf())
            queryMap[queries[i][0]]!!.add(Pair(queries[i][1], i))
        }

        val ans = IntArray(queries.size)

        fun dfs(cur: Int, trie: Trie<Int>) {
            queryMap[cur]?.forEach {
                ans[it.second] = trie.maxXor(it.first)
            }
            map[cur]?.forEach {
                trie.insertInt(it)
                dfs(it, trie)
                trie.removeInt(it)
            }
        }

        dfs(-1, Trie<Int>())

        return ans
    }
}

class Trie<T> {
    /**
     * @param cnt 记录当前点的值，用于Remove操作
     * */
    class TrieNode<T>(val init: T? = null, var cnt: Int = 0) {
        val value: T? = init
        val children: ArrayList<TrieNode<T>> = arrayListOf()
        var isEnd = false
    }

    var root = TrieNode<T>()

    /**
     * insert value
     * */
    fun insert(value: Array<T>) {
        fun dfs(node: TrieNode<T>, depth: Int) {
            if (depth == value.size) node.isEnd = true
            if (depth !in value.indices) return
            if (!node.children.map { it.value }.contains(value[depth])) {
                node.children.add(TrieNode<T>(value[depth]))
            }
            val next = node.children.first { it.value == value[depth] }
            dfs(next, depth + 1)
        }
        dfs(root, 0)
    }

    fun <T> search(target: Array<T>): Boolean {
        fun <T> dfs(node: TrieNode<T>, i: Int): Boolean {
            if (i in target.indices) {
                if (target[i] != node.value)
                    return false
            }
            if (i == target.lastIndex) return node.isEnd
            node.children.forEach {
                if (dfs(it, i + 1)) {
                    return true
                }
            }
            return false
        }
        return dfs(root, -1)
    }
}

fun Trie<Int>.removeInt(n: Int) {
    var temp = this.root
    for (i in 31 downTo 0) {
        val x: Int = (n shr i) and 1
        val item = temp.children.first { it.value == x }
        item.cnt--
        temp = item
    }
}

fun Trie<Int>.insertInt(n: Int) {
    var temp = this.root
    for (i in 31 downTo 0) {
        val x: Int = (n shr i) and 1
        val item = temp.children.firstOrNull { it.value == x }
        if (item == null)
            temp.children.add(Trie.TrieNode(x, 1))
        else
            item.cnt++
        temp = temp.children.first { it.value == x }
    }
}

/**
 * https://www.geeksforgeeks.org/maximum-possible-xor-every-element-array-another-array/
 * */
fun Trie<Int>.maxXor(key: Int): Int {
    if (root.children.isEmpty()) return -1
    var temp = root
    var cur = 0
    for (i in 31 downTo 0) {
        cur *= 2
        val curBit = (key and (1 shl i)).let { if (it > 0) 1 else 0 }
        temp = if (temp.children.firstOrNull { it.value == 1 - curBit && it.cnt != 0 } != null)
            temp.children.first { it.value == 1 - curBit && it.cnt != 0 }
        else
            temp.children.first { it.value == curBit && it.cnt != 0 }
        cur += curBit xor temp.value!!
    }
    return cur
}