第 231 场周赛题解
第 231 场周赛题解
Q1 1784. 检查二进制字符串字段
感觉题目翻译的有歧义,反正题意就是所有的$1$都要挨在一起,不能用$0$隔开。
class Solution1784 {
fun checkOnesSegment(s: String): Boolean {
val l = s.indexOfFirst { it == '1' }
val r = s.indexOfLast { it == '1' }
return (l..r).all { s[it] == '1' }
}
}
Q2 1785. 构成特定和需要添加的最少元素
这题恶心在要用$Long$转一下,不然会溢出... WA了一次...
还有就是一个向上取整的小技巧,加一个$limit - 1$之后再除以$limit$。
import kotlin.math.abs
class Solution5698 {
fun minElements(nums: IntArray, limit: Int, goal: Int): Int {
var sum: Long = 0
val g = goal.toLong()
nums.forEach {
sum += it
}
return ((abs(sum - g) + limit - 1) / limit).toInt()
}
}
Q3 1786. 从第一个节点出发到最后一个节点的受限路径数
这道题比较绕,前后分成两个部分。
- 首先通过$Dijkstra$计算出各个节点距离最后一个点的距离(这里要注意使用堆优化的,如果开$O(n^2)$的对于Kotlin会爆内存...
- $DFS$求解出从起始节点到终止节点有多少路径(这里也可以用上述结果排序后$DP$求解)
class Solution1786 {
fun countRestrictedPaths(n: Int, edges: Array<IntArray>): Int {
val mod = 1000000007L
val graph = Graph(n + 1)
edges.forEach {
graph.addEdge(it[0], it[1], it[2])
}
val dis = graph.dijkstra(n)
val seen = HashMap<Int, Long>()
fun dfs(node: Int): Long {
if (node in seen) return seen[node]!!
if (node == 0) return 0L
if (node == n) return 1L
var ans = 0L
graph.adj[node].forEach {
if (dis[it] < dis[node]) {
ans += dfs(it)
ans %= mod
}
}
return ans.also {
seen[node] = it
}
}
return (dfs(1) % mod).toInt()
}
}
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
}
}
/**
* 堆优化Dijkstra 单源最短路径
* @param source 源点(0..n-1)
* */
fun Graph.dijkstra(source: Int): IntArray {
// 距离source的最短路径
val ans = IntArray(n) { Int.MAX_VALUE / 2 }
val pq = PriorityQueue<Pair<Int, Int>>(compareBy { it.second })
pq.offer(Pair(source, 0))
while (pq.isNotEmpty()) {
val (item, dis) = pq.poll()
if (ans[item] <= dis) continue
ans[item] = dis
this.adj[item].forEach {
if (ans[it] >= Int.MAX_VALUE / 2)
pq.offer(Pair(it, dis + weight[item]!![it]!!))
}
}
return ans
}
Q4 1787. 使所有区间的异或结果为零
本题非常有意思,又涨知识了!
假设列表为${a_1,a_2,a_3,b_1,b_2,b_3,c_1,c_2,c_3}$,我们可知要修改的最终状态为使得$a_1\oplus a_2\oplus a_3 == 0$ && $a_2\oplus a_3\oplus b_1 == 0$。根据异或的运算规则可知,$a_1 == b_1$,轮询推导后会发现$a_1 == b_1 == c_1$,$a_2 == b_2 == c_2$...
这样我们只需要求出一组的解即可,即一份$a_1、b_1、c_1$。
看数据范围为$0 < nums[i] < 2^{10}$,通过异或规则可知,无论怎么异或都不会超出这个范围。
下面需要使用$DP$来求解。
- 首先将$n$个数字按$k$的余数分组,即一组内的数字最终要变成同一个数。(这里要注意,可能存在非整除的情况,每一组的个数不一定相同)
- $dp[n][m]$代表,选择完前$n+1$个数,使得总异或值为$m$的最小代价
- $dp[k - 1][0]$即最终所求答案
关于状态转移方程,当前$index$若为$0$,则总异或值就是自己的值,只需要计算该组不是该值的数量 $$ dp[0][j] = group[0].sum() - group[0][j] $$ 若当前$index$不为$0$,需要利用前项数据来计算,而无法直接计算$dp[i][j]$ $$ dp[i][pre \oplus key] = min \left{dp[i][pre \oplus key] group[i].sum() - group[i][key]\right} $$ 通过上述公式可以看出,若$key$不在当前纵列当中,则遍历的值都是相同的,可以降低时间复杂度。
每向后遍历一个数字时,先将$dp[i]$的值都用$min\left{dp[i - 1]\right} + group[i].sum()$填充,代表当前列的值随意改,肯定能保证得出任意异或值的结果。通过这个方法可以将时间复杂度从$O(k * 1024^2)$ 降低为 $O(k * 1024)$。
class Solution1787 {
fun minChanges(nums: IntArray, k: Int): Int {
val group = Array<HashMap<Int, Int>>(k) { hashMapOf() }
for (i in nums.indices) {
val value = nums[i]
group[i % k][value] = group[i % k].getOrDefault(value, 0) + 1
}
val max = 1024
val dp = Array<IntArray>(k) { IntArray(max) }
for (i in 0 until k) {
val sum = group[i].values.sum()
if (i == 0) {
for (j in 0 until max) {
dp[i][j] = sum - group[i].getOrDefault(j, 0)
}
} else {
dp[i].fill(dp[i - 1].min()!! + sum)
group[i].forEach { (key, value) ->
for (pre in 0 until max) {
dp[i][pre xor key] = minOf(dp[i][pre xor key], dp[i - 1][pre] + sum - value)
}
}
}
}
return dp[k - 1][0]
}
}