第 233 场周赛题解

Q1 1800. 最大升序子数组和 (opens new window)

题目中要求的是连续的且元素值均为正数，因此直接把符合条件的子数组分别求和，取最大值即可。

class Solution1800 {
    fun maxAscendingSum(nums: IntArray): Int {
        var ans = nums[0]
        var cur = nums[0]
        for (i in 1 until nums.size) {
            if (nums[i] > nums[i - 1]) {
                cur += nums[i]
            } else {
                cur = nums[i]
            }
            ans = maxOf(ans, cur)
        }
        return ans
    }
}

Q2 1801. 积压订单中的订单总数 (opens new window)

没什么难度，但是非常麻烦的题目。直接优先级队列搞。

class Solution1801 {
    fun getNumberOfBacklogOrders(orders: Array<IntArray>): Int {
        val buy = PriorityQueue<IntArray>(compareByDescending { it[0] })
        val sell = PriorityQueue<IntArray>(compareBy { it[0] })
        orders.forEach {
            if (it[2] == 0) {
                buy.offer(it)
            } else {
                sell.offer(it)
            }

            while (sell.isNotEmpty() && buy.isNotEmpty() && sell.peek()[0] <= buy.peek()[0]) {
                val sellItem = sell.poll()
                val buyItem = buy.poll()
                if (sellItem[1] == buyItem[1]) {
                    continue
                } else if (sellItem[1] > buyItem[1]) {
                    sell.offer(intArrayOf(sellItem[0], sellItem[1] - buyItem[1], sellItem[2]))
                } else {
                    buy.offer(intArrayOf(buyItem[0], buyItem[1] - sellItem[1], buyItem[2]))
                }
            }
        }
        val mod = 1000000007L
        var ans = 0L
        buy.forEach {
            ans += it[1]
        }
        sell.forEach {
            ans += it[1]
        }
        return (ans % mod).toInt()
    }
}

Q3 1802. 有界数组中指定下标处的最大值 (opens new window)

直接用二分，就是最开始公式推导很麻烦，浪费了很多时间。

class Solution1802 {
    fun maxValue(n: Int, index: Int, maxSum: Int): Int {
        fun sum(start: Int, count: Int): Long {
            if (count == 0) return 0L
            val minCount = minOf(start, count)
            var sum = start * minCount.toLong() - (minCount - 1) * minCount.toLong() / 2
            if (count > minCount) sum += count - minCount
            return sum
        }

        var l = 1
        var r = maxSum - n + 1
        while (l < r) {
            val mid = l + (r - l + 1) / 2
            val sumLeft = sum(mid - 1, index)
            val sumRight = sum(mid, n - index)
            if (sumLeft + sumRight <= maxSum) l = mid
            else r = mid - 1
        }
        return l
    }
}

Q4 1803. 统计异或值在范围内的数对有多少 (opens new window)

字典树原题 (opens new window)。

class Solution1803 {
    fun countPairs(nums: IntArray, low: Int, high: Int): Int {
        val trie = Trie<Int>()
        var ans = 0
        nums.forEach {
            ans += trie.smaller(it, high + 1)
            ans -= trie.smaller(it, low)
            trie.insertInt(it)
        }
        return ans
    }
}

class Trie<T> {
    class TrieNode<T>(val init: T? = null) {
        val value: T? = init
        val children: ArrayList<TrieNode<T>> = arrayListOf()
        var isEnd = false
        var cnt = 0
    }

    var root = TrieNode<T>()
}

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))
        temp = temp.children.first { it.value == x }
        temp.cnt++
    }
}

fun Trie<Int>.smaller(n: Int, k: Int): Int {
    var count = 0
    var node: Trie.TrieNode<Int>? = this.root
    for (i in 31 downTo 0) {
        if (node == null) {
            return count
        }
        val x: Int = (n shr i) and 1
        val y: Int = (k shr i) and 1
        if (y == 1) {
            if (node.children.firstOrNull { it.value == x } != null) {
                count += node.children.first { it.value == x }.cnt
            }
            node = node.children.firstOrNull { it.value == 1 - x }
        } else {
            node = node.children.firstOrNull { it.value == x }
        }
    }
    return count
}