牛客春招刷题训练营-2025.5.5题解

简单题小红结账

初始化数据结构：
- 使用一个大小为 m+1 的数组 s 来记录每个人的转账总额。下标 1 到 m 表示每个人， s[i] 表示第 i 个人需要转账的总金额。
逐张处理账单：
- 对于每张账单：
  - 计算每个人的分摊金额 cost = ⌈c / k⌉，公式为 (c + k - 1) / k（这是向上取整的一种实现方式）。
  - 读取 k-1 个人的编号，并将 cost 累加到对应人的转账金额上。
输出结果：
- 遍历数组 s 中从 1 到 m 的部分，依次输出每个人的转账总额。

package main

import "fmt"

func main() {
	var n, m int
	fmt.Scan(&n, &m)
	s := make([]int, m+1)
	for i := 1; i <= n; i++ {
		var k, c int
		fmt.Scan(&k, &c)
		cost := (c + k - 1) / k
		for j := 1; j <= k-1; j++ {
			var x int
			fmt.Scan(&x)
			s[x] += cost
		}
	}
	for i := 1; i <= m; i++ {
		fmt.Print(s[i], " ")
	}
}

中等题跳跃游戏(一)

初始化动态规划数组

定义一个数组 dp，其中 dp[i] 表示从数组的起始位置（索引 0）出发，能够到达的最远位置。
初始值 dp[0] = a[0]，即从第一个位置出发时能够到达的最远位置就是 a[0]。

动态规划状态转移

遍历数组中的每个位置 i（从 1 开始），更新 dp[i]
- 如果当前的最远可达位置 dp[i-1] 已经大于等于 i，说明我们能够到达位置 i
  - 在这种情况下，更新 dp[i] 为 max(dp[i-1], i + a[i])，即比较之前的最远可达位置和从当前位置 i 能够跳跃到的最远位置。
- 如果 dp[i-1] < i，说明无法到达位置 i，此时也不需要继续计算，因为后续位置也无法到达。

判断结果

最后检查 dp[n-1] 是否大于等于 n-1
- 如果 dp[n-1] >= n-1，说明可以跳到数组的最后一个位置，输出 true。
- 否则，输出 false。

package main

import "fmt"

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func main() {
	var n int
	fmt.Scan(&n)
	a := make([]int, n)
	for i := 0; i < n; i++ {
		fmt.Scan(&a[i])
	}
	dp := make([]int, n)
	dp[0] = a[0]
	for i := 1; i < n; i++ {
		dp[i] = dp[i-1]
		if dp[i] >= i {
			dp[i] = max(dp[i], i+a[i])
		}
	}
	if dp[n-1] >= n-1 {
		fmt.Println("true")
	} else {
		fmt.Println("false")
	}
}

困难题郊区春游

预处理最短路径

使用 Floyd-Warshall 算法计算所有节点之间的最短路径。
- 初始化一个二维数组 d，其中 d[i][j] 表示从节点 i 到节点 j 的最短距离。
- 如果 i = j ，则 d[i][j] = 0；如果 i 和 j 之间没有直接连通，则 d[i][j] = ∞。
- 遍历所有边，更新直接相连节点之间的距离。
- 使用三重循环（Floyd-Warshall 算法的核心部分），逐步更新任意两点之间的最短路径。

状态压缩动态规划

定义状态 dp[mask][i]：
- mask 是一个二进制数，表示当前已经访问的郊区集合。例如，mask = 0101 表示访问了第 1 和第 3 个郊区。
- i 表示当前所在的郊区编号。
- dp[mask][i] 表示在访问了 mask 中的所有郊区，并且最后停留在郊区 ( i ) 时的最小花费。
初始化：
- 对于每个郊区 i ，单独访问它时的花费为 0，即 dp[1<<i][i] = 0。
状态转移：
- 枚举当前的状态 mask 和当前所在的郊区 j 。
- 如果 j 已经被访问过（即 (mask >> j) & 1 == 1），尝试从未访问过的郊区 ( k ) 转移到 ( j )。
- 更新状态：dp[mask | (1<<k)][k] = min(dp[mask | (1<<k)][k], dp[mask][j] + d[v[j]][v[k]])，其中 d[v[j]][v[k]] 是从郊区 ( v[j] ) 到郊区 ( v[k] ) 的最短距离。

最终结果

遍历所有可能的终点 i ，找到访问了所有 r 个郊区后的最小花费：
- ans = min(ans, dp[(1<<r)-1][i])，其中 (1<<r)-1 表示所有郊区都被访问的状态。

package main

import (
	"fmt"
	"math"
)

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func main() {
	var n, m, r int
	fmt.Scan(&n, &m, &r)
	v := make([]int, r)
	for i := 0; i < r; i++ {
		fmt.Scan(&v[i])
	}
	d := make([][]int, n+1)
	for i := 1; i <= n; i++ {
		d[i] = make([]int, n+1)
		for j := 1; j <= n; j++ {
			if i == j {
				d[i][j] = 0
			} else {
				d[i][j] = math.MaxInt
			}
		}
	}
	for i := 0; i < m; i++ {
		var a, b, c int
		fmt.Scan(&a, &b, &c)
		d[a][b] = min(d[a][b], c)
		d[b][a] = min(d[b][a], c)
	}
	for k := 1; k <= n; k++ {
		for i := 1; i <= n; i++ {
			for j := 1; j <= n; j++ {
				if d[i][k] != math.MaxInt && d[k][j] != math.MaxInt {
					d[i][j] = min(d[i][j], d[i][k]+d[k][j])
				}
			}
		}
	}

	dp := make([][]int, 1<<r)
	for i := 1; i < (1 << r); i++ {
		dp[i] = make([]int, r)
		for j := 0; j < r; j++ {
			dp[i][j] = math.MaxInt
		}
	}
	for i := 0; i < r; i++ {
		dp[1<<i][i] = 0
	}
	for i := 1; i < (1<<r)-1; i++ {
		for j := 0; j < r; j++ {
			if (i>>j)&1 == 0 {
				continue
			}
			for k := 0; k < r; k++ {
				if (i>>k)&1 == 0 {
					if d[v[j]][k] != math.MaxInt {
						dp[i|(1<<k)][k] = min(dp[i|(1<<k)][k], dp[i][j]+d[v[j]][v[k]])
					}
				}
			}
		}
	}
	ans := math.MaxInt
	for i := 0; i < r; i++ {
		ans = min(ans, dp[(1<<r)-1][i])
	}
	fmt.Println(ans)
}

#牛客春招刷题训练营#

牛客春招刷题训练营文章被收录于专栏

爱丽姐真是太好了