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

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

简单题 小欧的括号嵌套

首先打印 r 个左括号 ( 和打印 r 个右括号 ) 保证括号嵌套层数最大值为 r

剩余的 n-r 对括号以 () 形式直接打印保证括号嵌套层数不超过 r

package main

import "fmt"

func main() {
	var n, r int
	fmt.Scan(&n, &r)
	for i := 0; i < r; i++ {
		fmt.Print("(")
	}
	for i := 0; i < r; i++ {
		fmt.Print(")")
	}
	for i := 0; i < n-r; i++ {
		fmt.Print("()")
	}
}

中等题 不相邻取数

1. 状态定义：
   • 定义 dp[i][0] 表示在考虑前 i 个元素时，不选择第 i 个元素的情况下能得到的最大和。
   • 定义 dp[i][1] 表示在考虑前 i 个元素时，选择第 i 个元素的情况下能得到的最大和。
2. 状态转移方程：
   • 如果你不选择第 i 个元素，那么你可以从前 i-1 个元素的最大值中获得结果，即 dp[i][0] = max(dp[i-1][0], dp[i-1][1])。
   • 如果你选择第 i 个元素，那么你不能选择第 i-1 个元素，因此 dp[i][1] = dp[i-1][0] + a[i]。
3. 初始条件：
   • dp[0][0] = 0：没有元素时，不选择任何元素的最大和为 0。
   • dp[0][1] = 0：没有元素时，选择元素的情况不存在，因此也为 0。
4. 最终答案：
   • 最终的答案是 max(dp[n][0], dp[n][1])，表示在考虑所有 n 个元素时，选择或不选择最后一个元素的最大和。

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+1)
	for i := 1; i <= n; i++ {
		fmt.Scan(&a[i])
	}
	dp := make([][2]int, n+1)
	for i := 1; i <= n; i++ {
		dp[i][0] = max(dp[i-1][0], dp[i-1][1])
		dp[i][1] = dp[i-1][0] + a[i]
	}
	fmt.Println(max(dp[n][0], dp[n][1]))
}

困难题 小红的树

• 树的表示：使用邻接表来存储树结构，其中 g[i] 存储节点 i 的所有子节点。
• DFS 遍历：通过深度优先搜索 (DFS) 遍历树，计算每个节点的子树中状态为 'R' 的节点数量。
• 动态规划数组 dp：定义 dp[u]为以节点 u 为根的子树中状态为 'R' 的节点数量。
  • 如果节点 u 的状态是 'R'，则 dp[u] 初始值为 1，否则为 0。
  • 然后递归遍历 u 的所有子节点 v，将子节点的 dp[v] 值累加到 dp[u] 中。
• 查询处理：对于每次查询 x，直接输出 dp[x] 即可。

package main

import "fmt"

func main() {
	var n int
	fmt.Scan(&n)
	g := make([][]int, n+1)
	for i := 0; i <= n; i++ {
		g[i] = make([]int, 0)
	}
	for i := 2; i <= n; i++ {
		var fa int
		fmt.Scan(&fa)
		g[fa] = append(g[fa], i)
	}
	var s string
	fmt.Scan(&s)
	s = " " + s
	dp := make([]int, n+1)
	var dfs func(int)
	dfs = func(u int) {
		if s[u] == 'R' {
			dp[u] = 1
		} else {
			dp[u] = 0
		}
		for _, v := range g[u] {
			dfs(v)
			dp[u] += dp[v]
		}
	}
	dfs(1)

	var q int
	fmt.Scan(&q)
	for i := 0; i < q; i++ {
		var x int
		fmt.Scan(&x)
		fmt.Println(dp[x])
	}
}