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

简单题表示数字

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

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))
}

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

首先判断输入合法性：
- 如果需要放置的球数 k 小于行数 n 和列数 m 的最大值，则无法保证每行每列都有球，输出 -1
构造方案的核心思路：
- 先按对角线放置球（保证覆盖尽可能多的行和列）
- 根据矩阵是"瘦高型"还是"矮胖型"采用不同策略：
当 n >= m 时（瘦高型矩阵）：
- 在位置 (i, i%m) 放置一个球
- 这样可以保证每 m 行形成一个循环
- 总共需要放置 n 个球才能保证每行每列都有球
- 剩余的 k-n 个球放在 (0,0) 位置
当 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]))
}

#牛客春招刷题训练营#

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

爱丽姐真是太好了