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

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

简单题 游游的整数切割

要想使得前后两部分相加为偶数，我们可以看这两部分的个位相加结果是否为偶数。因为后半部分的个位一定是该字符串的最后一位，我们只要枚举前半部分的个位位置判断这两部分的个位相加是否为偶数即可。

package main

import "fmt"

func main() {
	var s string
	fmt.Scan(&s)
	ans := 0
	for i := 0; i < len(s)-1; i++ {
		if ((s[i]-'0')+(s[len(s)-1]-'0'))%2 == 0 {
			ans++
		}
	}
	fmt.Println(ans)
}

中等题 矩阵的最小路径和

1. 初始化二维数组：
   • 创建一个与输入矩阵 a 大小相同的二维数组 dp ，用于存储到达每个位置的最小路径和。
   • dp[i][j] 表示从起点 (0, 0) 到达位置 (i, j) 的最小路径和。
2. 边界条件：
   • 起点的路径和就是它本身的值，即 dp[0][0] = a[0][0]。
   • 对于第一行和第一列，由于只能从左边或上边到达，因此可以直接累加：
     • 第一行：dp[0][j] = dp[0][j-1] + a[0][j]
     • 第一列：dp[i][0] = dp[i-1][0] + a[i][0]
3. 状态转移方程：
   • 对于其他位置 (i, j)，可以从上方 (i-1, j) 或左方 (i, j-1) 移动过来，选择其中路径和较小的那个，并加上当前的值 a[i][j] 。
   • 状态转移方程为： dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + a[i][j]
4. 结果：
   • 最终的结果存储在 dp[n-1][m-1] 中，表示从左上角到右下角的最小路径和。

package main

import "fmt"

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

func main() {
	var n, m int
	fmt.Scan(&n, &m)
	a := make([][]int, n)
	dp := make([][]int, n)
	for i := 0; i < n; i++ {
		a[i] = make([]int, m)
		dp[i] = make([]int, m)
		for j := 0; j < m; j++ {
			fmt.Scan(&a[i][j])
		}
	}

	for i := 0; i < n; i++ {
		for j := 0; j < m; j++ {
			if i == 0 && j == 0 {
				dp[i][j] = a[i][j]
			} else if i == 0 {
				dp[i][j] = dp[i][j-1] + a[i][j]
			} else if j == 0 {
				dp[i][j] = dp[i-1][j] + a[i][j]
			} else {
				dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + a[i][j]
			}
		}
	}
	fmt.Println(dp[n-1][m-1])
}

困难题 旅游

这题可以将题目转换为给定一棵包含 n 个节点的树，每个节点可以选择被“选中”或“不选中”。目标是从树中选出一些节点，使得满足以下条件的情况下，选中的节点数最多：

1. 如果某个节点被选中，则它的直接子节点不能被选中。
2. 如果某个节点没有被选中，则它的子节点可以选择被选中或不选中。

这个问题可以通过树形DP来解决，主要思想是通过递归遍历树的结构，并在每个节点上维护两种状态：

1. 状态定义：
   • dp[u][0]：表示以节点 u 为根的子树中，节点 u 不选中时，最多能选中的节点数。
   • dp[u][1]：表示以节点 u 为根的子树中，节点 u 选中时，最多能选中的节点数。
2. 状态转移方程：
   • 如果节点 u 不选中，则其子节点 v 可以选择被选中或不选中，取两者的最大值：
   • 如果节点 u 被选中，则其所有子节点 v 都不能被选中：
3. 初始化：
   • 对于叶子节点（没有子节点的节点），dp[u][0] = 0，dp[u][1] = 1。
4. 递归实现：
   • 使用深度优先搜索（DFS）从根节点 s 开始遍历整棵树，在回溯的过程中更新每个节点的 dp 值。
5. 结果：
   • 最终答案为 dp[s][1]，即从起点 s 出发，节点 s 被选中时的最大选中节点数。

package main

import "fmt"

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

func main() {
	var n, s int
	fmt.Scan(&n, &s)
	g := make([][]int, n+1)
	for i := 0; i <= n; i++ {
		g[i] = make([]int, 0)
	}
	for i := 0; i < n-1; i++ {
		var u, v int
		fmt.Scan(&u, &v)
		g[u] = append(g[u], v)
		g[v] = append(g[v], u)
	}
	dp := make([][2]int, n+1)

	var dfs func(int, int)
	dfs = func(u, fa int) {
		dp[u][1], dp[u][0] = 1, 0
		for _, v := range g[u] {
			if v == fa {
				continue
			}
			dfs(v, u)
			dp[u][0] += max(dp[v][0], dp[v][1])
			dp[u][1] += dp[v][0]
		}
	}
	dfs(s, 0)
	fmt.Println(dp[s][1])
}