第 266 场周赛题解

Q1 2062. 统计字符串中的元音子字符串 (opens new window)

有$O(n)$的双指针写法，不过看数据范围，直接暴力即可。

class Solution2062 {
    fun countVowelSubstrings(word: String): Int {
        var ans = 0
        val arr = arrayOf('a', 'e', 'i', 'o', 'u')
        for (i in 0 until word.length) {
            for (j in i..word.length) {
                val sub = word.substring(i, j)
                if (arr.all { it in sub } && sub.all { it in arr }) {
                    ans++
                }
            }
        }
        return ans
    }
}

Q2 2063. 所有子字符串中的元音 (opens new window)

包含当前字符的次数，左侧（包含自己）的个数 * 右侧字符的个数。

class Solution2063 {
    fun countVowels(word: String): Long {
        val arr = arrayOf('a', 'e', 'i', 'o', 'u')
        var ans = 0L
        val n = word.length
        for (i in word.indices) {
            if (word[i] in arr) {
                ans += (i + 1).toLong() * (n - i)
            }
        }
        return ans
    }
}

Q3 2064. 分配给商店的最多商品的最小值 (opens new window)

二分处理，和运输船之类的题目类似，正向不好处理，但给一个值进行验证可以在${O(n)}$时间内判定。

class Solution2064 {
    fun minimizedMaximum(n: Int, quantities: IntArray): Int {
        fun check(mid: Int): Boolean {
            val add = quantities.map { (it - 1) / mid + 1 }.sum()
            return add <= n
        }

        var left = 0
        var right = quantities.maxOrNull()!!
        while (left + 1 < right) {
            val mid = (left + right).ushr(1)
            when {
                check(mid) -> right = mid
                else -> left = mid
            }
        }
        return when {
            check(right) -> right
            else -> left
        }
    }
}

Q4 2065. 最大化一张图中的路径价值 (opens new window)

手速场，结果手速快了，反而WA了...

注意的是遇到过的点，可以再走，只是不再加值。$seen$数组用IntArray，之前用BooleanArray结果WA了。

class Solution2065 {
    fun maximalPathQuality(values: IntArray, edges: Array<IntArray>, maxTime: Int): Int {
        // IntArray nextPoint, cost
        val map = HashMap<Int, ArrayList<IntArray>>()
        for (i in edges.indices) {
            map[edges[i][0]] = map.getOrDefault(edges[i][0], arrayListOf())
            map[edges[i][0]]!!.add(intArrayOf(edges[i][1], edges[i][2]))
            map[edges[i][1]] = map.getOrDefault(edges[i][1], arrayListOf())
            map[edges[i][1]]!!.add(intArrayOf(edges[i][0], edges[i][2]))
        }

        var ans = values[0]
        fun dfs(cur: Int, cost: Int, value: Int, seen: IntArray) {
            if (cost > maxTime) return
            if (cur == 0) ans = maxOf(ans, value)
            map[cur]?.forEach {
                seen[it[0]]++
                val nextValue = if (seen[it[0]] != 1) value else value + values[it[0]]
                dfs(it[0], cost + it[1], nextValue, seen)
                seen[it[0]]--
            }
        }

        dfs(0, 0, 0, IntArray(values.size))
        return ans
    }
}