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

活动地址： 牛客春招刷题训练营 - 编程打卡活动

简单题 表示数字

1. 读取输入字符串
2. 遍历字符串中的每个字符：
   • 当遇到数字时：
     • 如果是数字序列的开始，先添加一个 * 符号
     • 然后添加这个数字
   • 当遇到非数字时：
     • 如果之前有数字序列，在数字序列末尾添加 * 并将整个序列加入结果
     • 添加当前非数字字符
3. 最后如果还有未处理的数字序列，添加结尾的 * 并加入结果
4. 输出最终的字符串

package main

import "fmt"

func main() {
	var s string
	fmt.Scan(&s)
	var ss, digits []rune
	for _, c := range s {
		if c >= '0' && c <= '9' {
			if len(digits) == 0 {
				digits = append(digits, '*')
			}
			digits = append(digits, c)
		} else {
			if len(digits) > 0 {
				digits = append(digits, '*')
				ss = append(ss, digits...)
				digits = nil
			}
			ss = append(ss, c)
		}
	}
	if len(digits) > 0 {
		digits = append(digits, '*')
		ss = append(ss, digits...)
	}
	fmt.Println(string(ss))
}

中等题 球格模型（简单版）

1. 首先判断输入合法性：

   • 如果需要放置的球数 k 小于行数 n 和列数 m 的最大值，则无法保证每行每列都有球，输出 -1

2. 构造方案的核心思路：

   • 先按对角线放置球（保证覆盖尽可能多的行和列）
   • 根据矩阵是"瘦高型"还是"矮胖型"采用不同策略：

3. 当 n >= m 时（瘦高型矩阵）：

   • 在位置 (i, i%m) 放置一个球
   • 这样可以保证每 m 行形成一个循环
   • 总共需要放置 n 个球才能保证每行每列都有球
   • 剩余的 k-n 个球放在 (0,0) 位置

4. 当 n < m 时（矮胖型矩阵）：

   • 在位置 (i%n, i) 放置一个球
   • 这样可以保证每 n 列形成一个循环
   • 总共需要放置 m 个球才能保证每行每列都有球
   • 剩余的 k-m 个球放在 (0,0) 位置

这样构造的好处是：

• 保证了每行每列至少有一个球
• 满足了总共放置 k 个球的要求
• 所有多余的球都集中在一个位置，不影响其他位置

package main

import "fmt"

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

func main() {
	var n, m, k int
	fmt.Scan(&n, &m, &k)
	if max(n, m) > k {
		fmt.Println(-1)
		return
	}
	a := make([][]int, n)
	for i := 0; i < n; i++ {
		a[i] = make([]int, m)
	}
	if n >= m {
		for i := 0; i < n; i++ {
			a[i][i%m] = 1
		}
		a[0][0] += k - n
	} else {
		for i := 0; i < m; i++ {
			a[i%n][i] = 1
		}
		a[0][0] += k - m
	}
	for i := 0; i < n; i++ {
		for j := 0; j < m; j++ {
			fmt.Print(a[i][j], " ")
		}
		fmt.Println()
	}
}

困难题 【模板】01背包

1. 定义状态

dp[i][j] 表示：前 i 个物品中选，恰好放进一个容量为 j 的背包里，所能获得的最大价值。

2. 初始化

​ • dp[0][0] = 0表示前 0 个物品，容量为 0 时，价值为 0。

​ • 其余所有 dp[i][j] 初始设为 math.MinInt（一个极小值），表示不可达。

3. 状态转移

遍历每个物品 i，每个容量 j，转移分为两种情况：

• 不选第 i 个物品：

dp[i][j] = dp[i-1][j]

• 选第 i 个物品（前提是当前容量 j >= v[i]）：

dp[i][j] = max(dp[i-1][j], dp[i-1][j-v[i]] + w[i])

4. 答案获取

• 遍历 dp[n][j] 中所有容量 j，取最大值就是背包能装的最大价值。
• dp[n][m] 就是若背包恰好装满m容量的最大价值。

package main

import (
	"fmt"
	"math"
)

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

func main() {
	var n, m int
	fmt.Scan(&n, &m)
	w := make([]int, n+1)
	v := make([]int, n+1)
	for i := 1; i <= n; i++ {
		fmt.Scan(&v[i], &w[i])
	}

	dp := make([][]int, n+1)
	for i := range dp {
		dp[i] = make([]int, m+1)
		for j := range dp[i] {
			dp[i][j] = math.MinInt
		}
	}
	dp[0][0] = 0
	for i := 1; i <= n; i++ {
		for j := 0; j <= m; j++ {
			if j < v[i] {
				dp[i][j] = dp[i-1][j]
			} else {
				dp[i][j] = max(dp[i-1][j], dp[i-1][j-v[i]]+w[i])
			}
		}
	}
	ans := 0
	for j := 0; j <= m; j++ {
		ans = max(ans, dp[n][j])
	}
	fmt.Println(ans)
	fmt.Println(max(0, dp[n][m]))
}