第 263 场周赛题解

Q1 2042. 检查句子中的数字是否递增 (opens new window)

模拟。

class Solution5902 {
    fun areNumbersAscending(s: String): Boolean {
        val arr = s.split(" ").map {
            it.toIntOrNull()
        }.filterNotNull()
        for (i in 1 until arr.size) {
            if (arr[i] <= arr[i - 1])
                return false
        }
        return true
    }
}

Q2 2043. 简易银行系统 (opens new window)

无聊的题目...

class Bank(val balance: LongArray) {

    fun transfer(account1: Int, account2: Int, money: Long): Boolean {
        if (account1 - 1 in balance.indices && account2 - 1 in balance.indices) {
            if (balance[account1 - 1] >= money) {
                balance[account1 - 1] -= money
                balance[account2 - 1] += money
                return true
            }
        }
        return false
    }

    fun deposit(account: Int, money: Long): Boolean {
        if (account - 1 in balance.indices) {
            balance[account - 1] += money
            return true
        }
        return false
    }

    fun withdraw(account: Int, money: Long): Boolean {
        if (account - 1 in balance.indices) {
            if (balance[account - 1] >= money) {
                balance[account - 1] -= money
                return true
            }
        }
        return false
    }

}

Q3 2044. 统计按位或能得到最大值的子集数目 (opens new window)

正常暴力即可。$num.length <= 16$就是想让你暴力啊。

class Solution5904 {
    fun countMaxOrSubsets(nums: IntArray): Int {
        val n = nums.size
        var high = -1
        var ans = 0
        for (mask in 0 until (1 shl n)) {
            var cur = 0
            for (i in 0 until n) {
                if (mask and (1 shl i) != 0) {
                    cur = cur or nums[i]
                }
            }
            if (cur > high) {
                high = cur
                ans = 0
            } else if (cur == high) {
                ans++
            }
        }
        return ans
    }
}

Q4 2045. 到达目的地的第二短时间 (opens new window)

$BFS$，由于要找第二长的，需要抛弃下第一的数据。

注意这里每个点可以保留两个时间数据，且两个值不一样（相同的直接抛弃，而不是填充至下一个，这里WA了很久...）

class Solution5905 {
    fun secondMinimum(n: Int, edges: Array<IntArray>, time: Int, change: Int): Int {
        val g = Graph(n)
        edges.forEach {
            g.addEdge(it[0] - 1, it[1] - 1, time)
        }

        val seen = Array(n) { intArrayOf(Int.MAX_VALUE, Int.MAX_VALUE) }

        val pq = PriorityQueue<Pair<Int, Int>>(compareBy { it.second })
        pq.offer(Pair(0, 0))

        var max = -1
        while (pq.isNotEmpty()) {
            val (item, curTime) = pq.poll()
            if (seen[item][1] < curTime) continue

            if (item == n - 1) {
                if (max == -1) {
                    max = curTime
                } else if (curTime != max) {
                    return curTime
                }
            }
            var nextTime = curTime + time
            if ((curTime / change) % 2 != 0) {
                // 不可移动，等待到下次绿灯
                nextTime = (curTime / change + 1) * change + time
            }
            g.adj[item].forEach {
                if (nextTime < seen[it][0]) {
                    pq.offer(Pair(it, nextTime))
                    seen[it][0] = nextTime
                } else if (nextTime > seen[it][0] && nextTime < seen[it][1]) {
                    pq.offer(Pair(it, nextTime))
                    seen[it][1] = nextTime
                }
            }
        }
        return -1
    }
}