第 257 场周赛题解

Q1 1995. 统计特殊四元组 (opens new window)

无。

class Solution5863 {
    fun countQuadruplets(nums: IntArray): Int {
        var ans = 0
        for (i in nums.indices) {
            for (j in i + 1 until nums.size) {
                for (k in j + 1 until nums.size) {
                    for (l in k + 1 until nums.size) {
                        if (nums[i] + nums[j] + nums[k] == nums[l])
                            ans++
                    }
                }
            }
        }
        return ans
    }
}

Q2 1996. 游戏中弱角色的数量 (opens new window)

按攻击降序，防御升序进行排序。若防御小于前值，则之前一定有攻击大于当前值。（攻击跟我一样，防御大于我的都在我后面，所以不用考虑攻击相等的情况）。

class Solution5864 {
    fun numberOfWeakCharacters(properties: Array<IntArray>): Int {
        val st = properties.sortedWith(compareBy({ -it[0] }, { it[1] }))
        var ans = 0
        var maxDef = st[0][1]
        for (i in 1 until st.size) {
            if (st[i][1] < maxDef)
                ans++
            maxDef = maxOf(maxDef, st[i][1])
        }
        return ans
    }
}

Q3 1997. 访问完所有房间的第一天 (opens new window)

这题主要理解题意。首先注意条件$0 <= next[i] <= i$，则访问只会往回走，想往前走走到$i+1$，只能依靠重复走到$i$。

若每次都被传送到$0$处，则相当于完全走两次$dp[i - 1]$，传送到较靠后的位置，可以节省$dp[nextVisit[i - 1]]$的路程。

class Solution5865 {
    fun firstDayBeenInAllRooms(nextVisit: IntArray): Int {
        val mod = 1000000007L
        val n = nextVisit.size
        val dp = LongArray(n) { 0 }
        for (i in 1 until n) {
            dp[i] = (2 * dp[i - 1] - dp[nextVisit[i - 1]] + 2 + mod) % mod
        }
        return dp.last().toInt()
    }
}

Q4 1998. 数组的最大公因数排序 (opens new window)

并查集处理，由于值得范围较大，需要预处理有相同因数的数字，提前$union$。

// 被多次计算数组的max搞超时了... 提前存一份就行... 这数据...

class Solution5866 {
    fun gcdSort(nums: IntArray): Boolean {
        val st = nums.sorted()
        val max = nums.maxOrNull()!!
//        val max = nums.max()!!
        val ufs = UFS(max + 1)
        val meet = BooleanArray(max + 1)
        st.forEach {
            meet[it] = true
        }
        for (i in 2..max) {
            var j = i
            while (j <= max) {
                if (meet[j])
                    ufs.union(i, j)
                j += i
            }
        }
        for (i in st.indices) {
            if (nums[i] != st[i]) {
                if (ufs.find(nums[i]) != ufs.find(st[i])) return false
            }
        }
        return true
    }
}