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

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

简单题 构造C的歪

构造 a,b,c 这样一个等差数列，很容易发现 b-a=c-b，化简可得c=2*b-a

package main

import (
	"fmt"
)

func main() {
	var a, b int
	fmt.Scan(&a, &b)
	fmt.Println(2*b - a)
}

中等题 查找两个字符串a,b中的最长公共子串

1. 输入处理：

• 读取两个字符串 s 和 t
• 为了简化处理，让较短的字符串作为 s
• 在字符串前加空格，便于 dp 数组处理

2. 动态规划实现：

• 创建二维 DP 数组，dp[i][j] 表示以 s[i] 和 t[j] 结尾的最长公共子串长度
• 状态转移方程：
  • 当 s[i] == t[j] 时，dp[i][j] = dp[i-1][j-1] + 1
  • 当 s[i] != t[j] 时，dp[i][j] = 0

3. 找到最长子串：

• 遍历 dp 数组找到最大长度 maxLen 和对应的结束位置 idx
• 根据结束位置和长度从原字符串中截取最长公共子串

时间复杂度：，其中 n 和 m 分别是两个字符串的长度 空间复杂度：

package main

import "fmt"

func main() {
	var s, t string
	fmt.Scan(&s, &t)
	if len(s) > len(t) {
		s, t = t, s
	}
	n, m := len(s), len(t)
	s, t = " "+s, " "+t
	dp := make([][]int, n+1)
	for i := 0; i <= n; i++ {
		dp[i] = make([]int, m+1)
	}
	for i := 1; i <= n; i++ {
		for j := 1; j <= m; j++ {
			if s[i] == t[j] {
				dp[i][j] = dp[i-1][j-1] + 1
			} else {
				dp[i][j] = 0
			}
		}
	}
	maxLen, idx := 0, 0
	for i := 1; i <= n; i++ {
		for j := 1; j <= m; j++ {
			if dp[i][j] > maxLen {
				maxLen = dp[i][j]
				idx = i
			}
		}
	}
	fmt.Println(s[idx-maxLen+1 : idx+1])
}

困难题 气球谜题

1. 枚举颜色分组的顺序

由于只有三种颜色 {0,1,2}，它们的所有排列一共就 6 种：

1. 0->1->2
2. 0->2->1
3. 1->0->2
4. 1->2->0
5. 2->0->1
6. 2->1->0

可以对每一种排列单独计算“将原序列染成此排列所要求的顺序”所需的最小代价，然后在 6 种结果中取最小值。

2. 针对单一排列的 DP 设计

假设我们正在处理某个固定的排列，比如 0->1->2。如何计算将原序列变成“所有 0 都在左边，接着 1，最后 2”这种形态的最小花费呢？

令原序列的颜色用字符串（或数组）表示为 s，其中 。再令 表示将第 i 个元素改色的代价。

核心想法：

​ • 最终形成的序列从左到右只能依次出现 0 段、1 段、2 段，不能穿插倒序；一旦开始进入 1 段，就不能再回去变成 0；一旦开始 2 段，就不能再回到 0 或 1。

​ • 可以用 DP 来表示“处理到第 i 个元素时，我们目前染到的颜色段是哪一段”，并根据是否需要改色来累计花费。

DP 状态定义：

​ • ：处理到第 i 个元素时，如果第 i 个元素属于目标排列的第 k 段（），所需的最小总花费。

​ • 例如在排列 0->1->2 里，k=0 代表当前染成颜色 0，k=1 代表当前染成颜色 1，k=2 代表当前染成颜色 2。

状态转移：

​ 1. 第 i 个元素的实际颜色为 ，目标颜色为排列中的第 k 段颜色（记作 ）。

​ 2. 若 ，则第 i 个元素不需要改色；否则需要花费 。

​ 3. 第 i 个元素想要染成第 k 段，必须保证上一个元素（i-1）所处的段 j 不大于 k（即 ），因为不能“往回走”去染成之前的颜色段。

于是有：

其中

• 如果当前字符与目标位置字符相同，不需要额外代价

• 如果不同，需要支付 t[i] 的代价来修改

3. 综合 6 种排列取最小

对 6 种排列分别执行上述 DP，得到 6 个花费结果，最后取最小值即可。

注意：这题因为读入量过大，建议使用 bufio.NewReader 读入优化。

package main

import (
	"bufio"
	"fmt"
	"math"
	"os"
)

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

func main() {
	in := bufio.NewReader(os.Stdin)
	out := bufio.NewWriter(os.Stdout)
	defer out.Flush()

	var (
		n int
		s string
	)
	fmt.Fscan(in, &n, &s)
	s = " " + s
	t := make([]int64, n+1)
	for i := 1; i <= n; i++ {
		fmt.Fscan(in, &t[i])
	}

	f := func(ss string) int64 {
		dp := make([][3]int64, n+1)
		for i := 1; i <= n; i++ {
			for j := 0; j < 3; j++ {
				dp[i][j] = 1e18
			}
		}
		for i := 1; i <= n; i++ {
			for j := 0; j < 3; j++ {
				for k := j; k < 3; k++ {
					if s[i] == ss[k] {
						dp[i][k] = min(dp[i][k], dp[i-1][j])
					} else {
						dp[i][k] = min(dp[i][k], dp[i-1][j]+t[i])
					}
				}
			}
		}

		var ans int64 = math.MaxInt64
		for j := 0; j < 3; j++ {
			ans = min(ans, dp[n][j])
		}
		return ans
	}

	fmt.Fprintln(out, min(min(min(min(min(f("012"), f("021")), f("102")), f("120")), f("201")), f("210")))
}