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

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

简单题 ranko的手表

1. getTimeList 函数实现：

• 遍历所有可能的时间（00:00 到 23:59）
• 使用 checkTime 辅助函数检查时间是否匹配模式
• 将匹配的时间转换为分钟数（i*60+j）存入结果数组

2. 主函数实现：

• 读取两个时间字符串 op 和 ed
• 分别获取两个时间字符串可能表示的所有时间点列表
• 通过两层循环遍历所有可能的时间组合
• 只考虑第二个时间大于第一个时间的情况
• 记录最小时间差和最大时间差

package main

import "fmt"

func getTimeList(s string) []int {
	res := make([]int, 0)
	checkTime := func(s1, s2 string) bool {
		for i := 0; i < len(s1); i++ {
			if s1[i] != '?' && s1[i] != s2[i] {
				return false
			}
		}
		return true
	}
	for i := 0; i < 24; i++ {
		for j := 0; j < 60; j++ {
			time := fmt.Sprintf("%02d:%02d", i, j)
			if checkTime(s, time) {
				res = append(res, i*60+j)
			}
		}
	}
	return res
}

func main() {
	var op, ed string
	fmt.Scan(&op, &ed)
	t1s := getTimeList(op)
	t2s := getTimeList(ed)
	minTime := 24 * 60
	maxTime := 0
	for _, t1 := range t1s {
		for _, t2 := range t2s {
			if t2 <= t1 {
				continue
			}
			if t2-t1 < minTime {
				minTime = t2 - t1
			}
			if t2-t1 > maxTime {
				maxTime = t2 - t1
			}
		}
	}
	fmt.Println(minTime, maxTime)
}

中等题 跳台阶

代码实现的思路：

1. 当 n=1 时，只有一种跳法
2. 当 n=2 时，有两种跳法（一次跳一阶或一次跳两阶）
3. 当 n>2 时，第n阶台阶的跳法可以从以下两种情况得到：
   • 从第(n-1)阶跳1阶上来
   • 从第(n-2)阶跳2阶上来
4. 因此得出递推公式：f(n) = f(n-1) + f(n-2)

我们可以优化上面递推公式的空间

• 使用两个变量 a 和 b 来保存当前状态和前一个状态
• 通过循环来累积计算每一步的结果
• 使用并行赋值来优化空间复杂度

package main

func jumpFloor(n int) int {
	a, b := 1, 1
	for i := 2; i <= n; i++ {
		a, b = b, a+b
	}
	return b
}

困难题 [CQOI2007]涂色PAINT

由于每次操作是对一个区间进行染色，我们可以使用区间DP来解决该问题。

定义状态：

• dp(l, r) 表示将区间 [l, r] 染色成目标颜色所需的最少染色次数

我们对 dp(l, r) 进行如下分类讨论：

• 情况 1：l == r

  • 仅有一个格子时，只需要染色一次即可。
  • 状态转移：

• 情况 2：s[l] == s[r]

  • 当区间两端颜色相同时，可以将子区间 [l+1, r] 或者 [l, r-1] 染色完后，再统一向左或者向右染一格即可。
  • 状态转移：

• 情况 3：s[l] ≠ s[r]

  • 若区间两端颜色不同，则需将区间 [l, r] 分成左右两个子区间 [l, k] 和 [k+1, r]，分别染色。
  • 遍历所有断点 k ∈ [l, r-1]，选择染色次数最小的分法。
  • 状态转移：

package main

import "fmt"

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

func main() {
	var s string
	fmt.Scan(&s)
	n := len(s)
	dp := make([][]int, n)
	for i := 0; i < n; i++ {
		dp[i] = make([]int, n+1)
		for j := i; j < n; j++ {
			if i == j {
				dp[i][j] = 1
			} else {
				dp[i][j] = n
			}
		}
	}
	for l := 2; l <= n; l++ {
		for i := 0; i < n-l+1; i++ {
			j := i + l - 1
			if s[i] == s[j] {
				dp[i][j] = min(dp[i+1][j], dp[i][j-1])
			} else {
				for k := i; k < j; k++ {
					dp[i][j] = min(dp[i][j], dp[i][k]+dp[k+1][j])
				}
			}
		}
	}
	fmt.Println(dp[0][n-1])
}