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

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

简单题 字符串字符匹配

1. 构建字符集合：
   使用一个 map 来存储字符串 t 中的所有字符。这样可以快速判断某个字符是否存在于 t 中。

2. 遍历字符串 s：
   遍历字符串 s 的每个字符，检查它是否存在于前面构建的字符集合中。如果有任意一个字符不在集合中，则输出 false 并结束程序。

3. 输出结果：
   如果遍历完 s 的所有字符都在集合中，则输出 true。

package main

import "fmt"

func main() {
	var s, t string
	fmt.Scan(&s, &t)
	st := make(map[rune]struct{})
	for _, c := range t {
		st[c] = struct{}{}
	}
	for _, c := range s {
		if _, ok := st[c]; !ok {
			fmt.Println("false")
			return
		}
	}
	fmt.Println("true")
}

中等题 小红的区间构造

对于任意区间 内，满足 的整数个数可以表示为：

换句话说，调整起始点 L（对于给定 k 与 x），使得区间内恰有 n 个 x 的倍数。

注意到，每连续 x 个整数中必有一个 x 的倍数（不论区间如何选取，倍数的分布“均匀”）；因此，对于长度为 k 的区间，它所包含的 x 的倍数个数只可能落在两个相邻值上：

​ • 如果不“完整对齐”，区间内可能只有 个倍数；

​ • 如果区间起点选得“巧妙”，可以多容纳一个倍数，达到 个倍数。

参数之间的充分必要条件

1. 至少要容纳 n 个倍数

设区间中希望包含的 x 的倍数依次为

则这 n 个倍数的跨度为

由于区间长度为 k（区间跨度为 k-1），必有

2. 又不能太长，防止多出一个倍数

如果区间长得太多，还会额外容纳下一个 x 的倍数。假设 (m+n)x 落入区间，则倍数个数会达到 n+1。为了避免这种情况，我们要求区间右端点严格小于下一个倍数，即

当“最宽松”时取最小可能的 L（如使得 m x 正好处于区间内部），经过计算可推出

因此，存在一个长度为 k 的区间，使得其中恰有 n 个 x 的倍数的充分必要条件为

构造满足条件的区间

在满足上述条件时，我们可以构造出这样的区间。一个简单方法是选择适当的 L 使得区间恰好包含 n 个 x 的倍数。下面给出一种构造方案：

我们希望区间内恰好出现连续的 n 个 x 的倍数，可以设这 n 个倍数为

对于某个正整数 m，为确保这 n 个倍数全部落在 内，同时前一个倍数 和后一个倍数 都不在区间内，可以令，同时要求

为了简化，我们可以取 m=1，此时我们要求：

​ • 包含 x（第一个倍数）和 nx（可能是最后一个倍数）。

​ • 为了使 nx 落在区间内，应有

​ • 同时，为防止包含 (n+1)x，要求

一个简单的选法是取

这样构造出来的区间为

这种选择可以保证：

​ • 若 则 nx 恰好位于区间靠右侧，且由于 时还可以再移动 L（如果有余地）以避开 (n+1)x。

​ • 如果 则直接取 L=1，区间起点最小，从而不会提前包含多余的倍数。

package main

import "fmt"

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

func main() {
	var n, k, x int64
	fmt.Scan(&n, &k, &x)
	if k >= (n-1)*x+1 && k <= (n+1)*x-1 {
		l := max(1, n*x-k+1)
		fmt.Println(l, l+k-1)
		return
	} else {
		fmt.Println(-1)
	}
}

困难题 最长公共子序列(一)

• 使用二维 dp 数组，dp[i][j] 表示 s1 的前 i 个字符和 s2 的前 j 个字符的最长公共子序列长度
• 状态转移方程：
  • 如果 s1[i] == s2[j]，则 dp[i][j] = dp[i-1][j-1] + 1
  • 否则，dp[i][j] = max(dp[i-1][j], dp[i][j-1])

时间复杂度：

空间复杂度：

package main

import "fmt"

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

func main() {
	var n, m int
	fmt.Scan(&n, &m)
	var s1, s2 string
	fmt.Scan(&s1, &s2)
	s1, s2 = " "+s1, " "+s2
	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 s1[i] == s2[j] {
				dp[i][j] = dp[i-1][j-1] + 1
			} else {
				dp[i][j] = max(dp[i-1][j], dp[i][j-1])
			}
		}
	}
	fmt.Println(dp[n][m])
}

可以使用滚动数组来实现空间优化

空间复杂度：

package main

import "fmt"

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

func main() {
	var n, m int
	fmt.Scan(&n, &m)
	var s1, s2 string
	fmt.Scan(&s1, &s2)
	s1, s2 = " "+s1, " "+s2
	if n < m {
		n, m = m, n
		s1, s2 = s2, s1
	}

	dp := make([][]int, 2)
	dp[0] = make([]int, m+1)
	dp[1] = make([]int, m+1)

	// curr 表示当前行，prev 表示前一行
	curr := 0
	prev := 1

	for i := 1; i <= n; i++ {
		curr, prev = prev, curr
		for j := 1; j <= m; j++ {
			if s1[i] == s2[j] {
				dp[curr][j] = dp[prev][j-1] + 1
			} else {
				dp[curr][j] = max(dp[prev][j], dp[curr][j-1])
			}
		}
	}

	fmt.Println(dp[curr][m])
}