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

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

简单题 小欧的奇数

要解决这个问题，首先需要理解奇数和偶数的基本性质。具体来说，我们需要知道：

• 奇数 + 奇数 = 偶数
• 偶数 + 偶数 = 偶数
• 奇数 + 偶数 = 奇数

为了使三个数的和为奇数，有以下几种可能的情况：

1. 三个数全是奇数（奇数 + 奇数 + 奇数 = 奇数）。
2. 两个偶数加一个奇数（偶数 + 偶数 + 奇数 = 奇数）。

因此，问题可以转化为：统计数组中奇数和偶数的数量，然后判断是否满足上述两种情况之一。

解题步骤：

1. 统计奇数和偶数的数量：遍历数组，分别计算奇数和偶数的数量。
2. 判断条件：
   • 如果奇数的数量大于等于3，则可以选择三个奇数，其和必定是奇数。
   • 如果奇数的数量至少为1，并且偶数的数量至少为2，则可以选择两个偶数和一个奇数，其和也是奇数。
3. 输出结果：如果满足上述任一条件，输出"YES"；否则输出"NO"。

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：一套系统最多能拦截多少导弹

• 这实际上是一个 最长非递增子序列 的问题。
• 系统拦截导弹时，要求后一发炮弹的高度不能高于前一发。因此，我们需要找到导弹高度数组中的最长非递增子序列（即从左到右，高度不递增的最长子序列）。
• 动态规划的状态转移方程：
  • 定义 f1[i] 表示以第 i 枚导弹结尾的最长非递增子序列长度。
  • 转移方程为：f1[i] = max(f1[i], f1[j] + 1)，其中 j < i 且 h[j] >= h[i]。
• 最终结果是 max(f1[i])，即 f1 数组中的最大值。

问题 2：最少需要配备多少套系统

• 这实际上是一个 最长递增子序列 的问题。
• 每套系统只能拦截非递增高度的导弹，因此如果有递增高度的导弹出现，则需要额外的系统来处理它们。
• 根据 Dilworth 定理，最少系统数量等于导弹高度数组的最长递增子序列的长度。
• 动态规划的状态转移方程：
  • 定义 f2[i] 表示以第 i 枚导弹结尾的最长递增子序列长度。
  • 转移方程为：f2[i] = max(f2[i], f2[j] + 1)，其中 j < i 且 h[j] < h[i]。
• 最终结果是 max(f2[i])，即 f2 数组中的最大值。

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

	f1 := make([]int, n)
	f2 := make([]int, n)
	ans, res := 0, 0

	for i := 0; i < n; i++ {
		f1[i] = 1
		f2[i] = 1
		for j := 0; j < i; j++ {
			if h[j] >= h[i] {
				f1[i] = max(f1[i], f1[j]+1)
			} else {
				f2[i] = max(f2[i], f2[j]+1)
			}
		}
		ans = max(ans, f1[i])
		res = max(res, f2[i])
	}
	fmt.Println(ans)
	fmt.Println(res)
}

困难题 红和蓝

• 由每个红点周围有且仅有一个红点，每个蓝点周围有且仅有一个蓝点可得，如果叶子结点为一种颜色时，它的周围只有其父亲结点，所以父亲结点和它同色。
• 根据上述我们可以进行dfs，从下到上两两配对，存在一个没有与之配对的结点说明不存在此解
• 配对完成后在进行一遍dfs经行染色，如果是匹配的染同一颜色，否则染不同颜色。

package main

import "fmt"

func main() {
	var n int
	fmt.Scan(&n)

	col := make([]int, n+1)
	f := make([]int, n+1)
	g := make([][]int, n+1)

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

	var dfs1, dfs2 func(int, int)
	dfs1 = func(u, fa int) {
		for _, v := range g[u] {
			if v == fa {
				continue
			}
			dfs1(v, u)
			if f[u] == 0 && f[v] == 0 {
				f[u] = v
				f[v] = u
			}
		}
	}

	dfs1(1, 0)

	for i := 1; i <= n; i++ {
		if f[i] == 0 {
			fmt.Println("-1")
			return
		}
	}

	dfs2 = func(u, fa int) {
		for _, v := range g[u] {
			if v == fa {
				continue
			}
			if f[u] == v {
				col[v] = col[u]
			} else {
				col[v] = col[u] ^ 1
			}
			dfs2(v, u)
		}
	}

	col[1] = 1
	dfs2(1, 0)

	for i := 1; i <= n; i++ {
		if col[i] == 1 {
			fmt.Print("R")
		} else {
			fmt.Print("B")
		}
	}
}