第 274 场周赛题解

Q1 2124. 检查是否所有 A 都在 B 之前 (opens new window)

硬模拟。

class SolutionA {
    fun checkString(s: String): Boolean {
        var meet = false
        s.forEach {
            if (it == 'b') meet = true
            if (it == 'a' && meet) return false
        }
        return true
    }
}

Q2 2125. 银行中的激光束数量 (opens new window)

啥也不是，看题目还以为垂直方向也有啥限制... 一点思考都没有

class SolutionB {
    fun numberOfBeams(bank: Array<String>): Int {
        var lst = 0
        var cur = 0
        var ans = 0
        bank.map { it.count { it == '1' } }.filter { it != 0 }.forEach {
            lst = cur
            cur = it
            ans += lst * cur
        }
        return ans
    }
}

Q3 2126. 摧毁小行星 (opens new window)

直接贪心，这期B、C都过水。

class SolutionC {
    fun asteroidsDestroyed(mass: Int, asteroids: IntArray): Boolean {
        var cur = mass.toLong()
        asteroids.sorted().forEach {
            if (it <= cur) {
                cur += it
            } else {
                return false
            }
        }
        return true
    }
}

Q4 2127. 参加会议的最多员工数 (opens new window)

有意思，学到了新的知识！

每个点仅有一个出度，基环内向树。可参加的员工，要么是基环内向树中的环，要么是互相依赖的双节点及其两侧的最长链的总和。

1. 先将环上的每个点的最长枝求出来，即环向外发射的部分（通过拓扑排序&DP一直把入度为1的都加完，环上的点入度至少为2）
2. DFS求每个点的环，环深度为2，则可+两边的链长。

// 基环内向树
// 最大环 or 最长链
class SolutionD {
    fun maximumInvitations(favorite: IntArray): Int {
        val n = favorite.size
        val g = Graph(n)
        for (i in favorite.indices) {
            // 构造基环内向树
            g.addEdgeOri(favorite[i], i)
        }

        val (branch, isVisited) = g.getBranches()
//        branch.print()
        var ans = 0
        var tmp = 0
        // 计算每一个点作为起点时 环的长度 or 链的长度
        for (i in 0 until n) {
            if (isVisited[i]) continue
            var len = 0
            var u = i
            while (true) {
                val v = favorite[u]
                isVisited[u] = true
                len++
                if (isVisited[v]) break
                u = v
            }
            ans = if (len == 2) {
                // 二元环可以将两侧分支都带上
                tmp += 2 + branch[i] + branch[favorite[i]]
                maxOf(ans, tmp)
            } else {
                maxOf(ans, len)
            }
        }
        return ans
    }
}

// n为包含节点数
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
    }
}

/**
 * 获取基环内向树各枝杈的最大长度
 *
 * @return 基环内向树各点的最大枝长度，属于枝的结点标记为true
 * */
fun Graph.getBranches(): Pair<IntArray, BooleanArray> {
    val indegree = IntArray(n)
    val isVisited = BooleanArray(n)
    val branches = IntArray(n)

    val dep = IntArray(n)

    // 基环内向树，每个点出度为1
    // 统计每个点的入度
    for (i in 0 until n) {
        indegree[i] = adj[i].size
        adj[i].forEach {
            dep[it] = i
        }
    }

    // 拓扑排序，先将入度为0的点入队
    val q: Queue<Int> = LinkedList<Int>()
    for (i in 0 until n) {
        if (indegree[i] == 0) {
            q.offer(i)
            isVisited[i] = true
        }
    }

    while (q.isNotEmpty()) {
        val u = q.poll()
        val v = dep[u]
        branches[v] = maxOf(branches[v], branches[u] + 1)
        if (--indegree[v] == 0) {
            q.offer(v)
            isVisited[v] = true
        }
    }

    return Pair(branches, isVisited)
}