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

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

简单题 小红的校招笔试

1. 输入处理：

   • 接收一个整数 n，表示数组长度
   • 创建一个长度为 n 的整数数组 a
   • 使用循环读入 n 个整数

2. 计算排名：

   • 设置初始排名 rk = 1
   • 遍历数组，如果发现比第一个数（a[0]）大的数，就给排名加1
   • 这样可以得到第一个数的排名

3. 判断条件：

   • 特殊情况：如果 n = 1，直接输出 "Yes"
   • 一般情况：如果排名 rk > n/2（即第一个数排在后半段），输出 "No"
   • 否则（即第一个数排在前半段），输出 "Yes"

package main

import "fmt"

func main() {
	var n int
	fmt.Scan(&n)
	a := make([]int, n)
	rk := 1
	for i := 0; i < n; i++ {
		fmt.Scan(&a[i])
		if a[0] < a[i] {
			rk++
		}
	}
	if n == 1 {
		fmt.Println("Yes")
		return
	}
	if rk > n/2 {
		fmt.Println("No")
	} else {
		fmt.Println("Yes")
	}
}

中等题 小红的区间查询

1. 数据输入部分:

   • 读入两个整数 n 和 q，分别表示数组长度和操作次数
   • 创建一个长度为 n+1 的数组 a（注意索引从1开始使用）
   • 循环读入 n 个数作为数组的初始值

2. 操作处理部分:

   • 执行 q 次操作，每次读入三个整数：
     • op：操作类型（1或2）
     • id：操作相关的位置/范围
     • x：操作的值

3. 两种操作类型:

   • 操作1（修改操作）：

     • 当 op = 1 时
     • 将数组位置 id 的值修改为 x

   • 操作2（查询操作）：

     • 当 op = 2 时
     • 统计数组从位置1到位置id中等于x的元素个数
     • 输出统计结果

package main

import "fmt"

func main() {
	var n, q int
	fmt.Scan(&n, &q)
	a := make([]int, n+1)
	for i := 1; i <= n; i++ {
		fmt.Scan(&a[i])
	}
	for i := 0; i < q; i++ {
		var op, id, x int
		fmt.Scan(&op, &id, &x)
		switch op {
		case 1:
			a[id] = x
		case 2:
			cnt := 0
			for j := 1; j <= id; j++ {
				if a[j] == x {
					cnt++
				}
			}
			fmt.Println(cnt)
		}
	}
}

困难题 最长回文子序列

1. 状态定义

   • 我们使用二维数组 dp[i][j] 来表示字符串 s 中从第 i 个字符到第 j 个字符之间的最长回文子序列的长度。

2. 转移方程

   1. 对于任意情况，dp[i][j] = max(dp[i+1][j], dp[i][j-1])，最长回文子序列要么在 s[i+1..j] 中，要么在 s[i..j-1] 中。
   2. 如果 s[i] == s[j]，存在 dp[i][j] = dp[i+1][j-1] + 2 ，如果两端字符相等，那么它们一定可以作为回文的一部分，而中间部分的状态由 dp[i+1][j-1] 决定。

3. 初始化

   • 对于单个字符的情况，即 dp[i][i]，显然最长回文子序列就是该字符本身，因此 dp[i][i] = 1。

package main

import "fmt"

func max(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)
		dp[i][i] = 1
	}
	for l := 2; l <= n; l++ {
		for i := 0; i+l-1 < n; i++ {
			j := i + l - 1
			dp[i][j] = max(dp[i+1][j], dp[i][j-1])
			if s[i] == s[j] {
				dp[i][j] = max(dp[i][j], dp[i+1][j-1]+2)
			}
		}
	}
	fmt.Println(dp[0][n-1])
}