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

简单题【模板】队列

使用切片 q []int 来模拟队列，具体实现：

push 操作使用 append 将元素添加到切片末尾
pop 操作先检查队列是否为空，不为空则输出 q[0] 并使用 q[1:] 移除队首元素
front 操作只需要检查队列是否为空，不为空则输出 q[0]

package main

import "fmt"

func main() {
	var n int
	fmt.Scan(&n)
	var q []int
	for i := 0; i < n; i++ {
		var op string
		fmt.Scan(&op)
		switch op {
		case "push":
			var x int
			fmt.Scan(&x)
			q = append(q, x)
		case "pop":
			if len(q) == 0 {
				fmt.Println("error")
			} else {
				fmt.Println(q[0])
				q = q[1:]
			}
		case "front":
			if len(q) == 0 {
				fmt.Println("error")
			} else {
				fmt.Println(q[0])
			}
		}
	}
}

中等题【模板】循环队列

初始化:

创建长度为n的数组que作为队列
head表示队首位置，tail表示队尾位置
size记录当前队列中元素数量

三种操作:

push x: 入队操作
- 如果size == n说明队列已满，输出"error"
- 否则将x加入tail位置，tail向后移动一位(循环)，size增加
pop: 出队操作
- 如果size == 0说明队列为空，输出"error"
- 否则输出head位置的元素，head向后移动一位(循环)，size减少
front: 查看队首
- 如果size == 0说明队列为空，输出"error"
- 否则输出head位置的元素

package main

import "fmt"

func main() {
	var n, q int
	fmt.Scan(&n, &q)
	que := make([]int, n)
	head, tail := 0, 0
	size := 0
	for i := 0; i < q; i++ {
		var op string
		fmt.Scan(&op)
		switch op {
		case "push":
			var x int
			fmt.Scan(&x)
			if size == n {
				fmt.Println("full")
				continue
			}
			que[tail] = x
			tail = (tail + 1) % n
			size++
		case "pop":
			if size == 0 {
				fmt.Println("empty")
				continue
			}
			fmt.Println(que[head])
			head = (head + 1) % n
			size--
		case "front":
			if size == 0 {
				fmt.Println("empty")
				continue
			}
			fmt.Println(que[head])
		}
	}
}

困难题合并回文子串

状态定义：

dp[l1][i1][l2][i2] 表示从字符串 a 中选择长度为 l1，起始位置为 i1 的子序列，从字符串 b 中选择长度为 l2，起始位置为 i2 的子序列，能否交错形成回文串
值为 1 表示可以，0 表示不可以

转移方程：有四种转移情况：

// 1. a[i1] 和 b[j2] 匹配
if l1 >= 1 && l2 >= 1 && a[i1] == b[j2]
    dp[l1][i1][l2][i2] |= dp[l1-1][i1+1][l2-1][i2]

// 2. a[j1] 和 b[i2] 匹配
if l1 >= 1 && l2 >= 1 && a[j1] == b[i2]
    dp[l1][i1][l2][i2] |= dp[l1-1][i1][l2-1][i2+1]

// 3. a 串内部匹配
if l1 >= 2 && a[i1] == a[j1]
    dp[l1][i1][l2][i2] |= dp[l1-2][i1+1][l2][i2]

// 4. b 串内部匹配
if l2 >= 2 && b[i2] == b[j2]
    dp[l1][i1][l2][i2] |= dp[l1][i1][l2-2][i2+1]

边界条件：

当 l1 + l2 ≤ 1 时，dp[l1][i1][l2][i2] = 1

最终答案：

遍历所有状态，找到满足条件的最大的 l1 + l2

package main

import "fmt"

func solve() {
	var a, b string
	fmt.Scan(&a, &b)
	n, m := len(a), len(b)
	dp := make([][][][]int, n+1)
	for i := 0; i <= n; i++ {
		dp[i] = make([][][]int, n+1)
		for j := 0; j <= n; j++ {
			dp[i][j] = make([][]int, m+1)
			for k := 0; k <= m; k++ {
				dp[i][j][k] = make([]int, m+1)
			}
		}
	}
	ans := 0
	for l1 := 0; l1 <= n; l1++ {
		for i1 := 0; i1 <= n; i1++ {
			j1 := i1 + l1 - 1
			if j1 >= n {
				break
			}
			for l2 := 0; l2 <= m; l2++ {
				for i2 := 0; i2 <= m; i2++ {
					j2 := i2 + l2 - 1
					if j2 >= m {
						break
					}
					if l1+l2 <= 1 {
						dp[l1][i1][l2][i2] = 1
					} else {
						if l1 >= 1 && l2 >= 1 && a[i1] == b[j2] {
							dp[l1][i1][l2][i2] |= dp[l1-1][i1+1][l2-1][i2]
						}
						if l1 >= 1 && l2 >= 1 && a[j1] == b[i2] {
							dp[l1][i1][l2][i2] |= dp[l1-1][i1][l2-1][i2+1]
						}
						if l1 >= 2 && a[i1] == a[j1] {
							dp[l1][i1][l2][i2] |= dp[l1-2][i1+1][l2][i2]
						}
						if l2 >= 2 && b[i2] == b[j2] {
							dp[l1][i1][l2][i2] |= dp[l1][i1][l2-2][i2+1]
						}
					}
					if dp[l1][i1][l2][i2] == 1 {
						if l1+l2 > ans {
							ans = l1 + l2
						}
					}
				}
			}
		}
	}
	fmt.Println(ans)
}

func main() {
	var t int
	fmt.Scan(&t)
	for i := 0; i < t; i++ {
		solve()
	}
}

#牛客春招刷题训练营#

牛客春招刷题训练营文章被收录于专栏

爱丽姐真是太好了