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

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

简单题 变幻莫测

操作一：交换

• 这只是交换，不改变值的集合，只是让之后的操作顺序更灵活。

操作二：线性变换

• 可以发现只有第一次进行线性变换才有概率使得这两个数相等，并且条件要满足

	0	已经相等，无需任何操作
	1	直接做 op2：
	2	先 swap 得 ，再如上做 op2 得
	3	取 ： 1. op2： 2. swap： 3. op2：

package main

import "fmt"

func main() {
	var x, y int
	fmt.Scan(&x, &y)
	if x == y {
		fmt.Println(0)
	} else if y == 0 {
		fmt.Println(1)
	} else if x == 0 {
		fmt.Println(2)
	} else if x == -y {
		fmt.Println(3)
	} else {
		fmt.Println(-1)
	}
}

中等题 平均数为k的最长连续子数组

这道题是求解一个数组中平均数为k的最长连续子数组长度。

1. 问题转化

• 若子数组平均数为k，则子数组所有元素之和除以长度等于k
• 可以转化为：(a[l] + a[l+1] + ... + a[r])/len = k
• 即：(a[l] - k) + (a[l+1] - k) + ... + (a[r] - k) = 0

2. 前缀和思想

• 对数组中每个元素都减去k：a[i] -= k
• 计算新数组的前缀和sum
• 如果区间[l,r]的和为0，说明原数组在这个区间的平均数正好为k

3. 代码实现要点:

sum, ans := 0, -1          // sum是前缀和，ans记录最大长度
mp := map[int]int{0: 0}    // 记录前缀和第一次出现的位置

4. 核心逻辑:

• 遍历数组，计算前缀和sum
• 如果某个前缀和sum在map中已经存在
  • 说明找到了一个和为0的区间
  • 区间长度为i - mp[sum]
• 否则将当前前缀和及其位置存入map

package main

import "fmt"

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

func main() {
	var n, k int
	fmt.Scan(&n, &k)
	a := make([]int, n+1)
	mp := map[int]int{
		0: 0,
	}
	sum, ans := 0, -1
	for i := 1; i <= n; i++ {
		fmt.Scan(&a[i])
		a[i] -= k
		sum += a[i]
		if _, ok := mp[sum]; ok {
			ans = max(ans, i-mp[sum])
		} else {
			mp[sum] = i
		}
	}
	fmt.Println(ans)
}

困难题 最大子矩阵

要解决最大子矩阵和的问题，我们需要找到一个二维矩阵中具有最大和的子矩阵。这个问题可以看作是一维最大子数组和问题的扩展。

第一步：将二维问题转化为一维问题

1. 假设我们固定了矩阵的上下边界（即行范围 [top, bottom]），那么我们可以将这个范围内的所有列压缩成一个一维数组。
2. 这样，问题就变成了在一维数组中寻找最大子数组和的问题，这是一个经典问题，可以用 Kadane 算法在 (O(n)) 时间内解决。

第二步：枚举所有可能的上下边界

• 我们需要枚举所有可能的上下边界组合，对于每种组合：
  • 将对应的列压缩成一维数组。
  • 使用 Kadane 算法计算该一维数组的最大子数组和。
• 最终的答案就是所有这些最大子数组和中的最大值。

详细步骤

1. 枚举上下边界

• 外层循环枚举上边界 top，从第 0 行到第 (n-1) 行。
• 内层循环枚举下边界 bottom，从 top 到第 (n-1) 行。

2. 压缩列

• 对于固定的 top 和 bottom，我们将 [top, bottom] 范围内的每一列的元素相加，得到一个长度为 m 的一维数组 sum。

3. 使用 Kadane 算法求解最大子数组和

• 对于压缩后的一维数组 sum，使用 Kadane 算法计算其最大子数组和。
• Kadane 算法的核心思想是维护两个变量：
  • currentSum：当前子数组的和。
  • maxSum：全局的最大子数组和。
• 遍历数组时，更新这两个变量：
  • currentSum = max(currentSum + sum[i], sum[i])​
  • maxSum = max(maxSum, current_sum) ​

4. 更新全局最大值

• 在每次计算完 compressed 数组的最大子数组和后，将其与当前的全局最大值比较，并更新全局最大值。

package main

import (
	"fmt"
	"math"
)

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

func main() {
	var n int
	fmt.Scan(&n)
	a := make([][]int, n)
	for i := 0; i < n; i++ {
		a[i] = make([]int, n)
		for j := 0; j < n; j++ {
			fmt.Scan(&a[i][j])
		}
	}

	maxSum := math.MinInt
	for top := 0; top < n; top++ {
		sum := make([]int, n)
		for bottom := top; bottom < n; bottom++ {
			for col := 0; col < n; col++ {
				sum[col] += a[bottom][col]
			}
			currentSum := 0
			currentMax := -math.MaxInt
			for _, val := range sum {
				currentSum = max(val, currentSum+val)
				currentMax = max(currentMax, currentSum)
			}
			maxSum = max(maxSum, currentMax)
		}
	}
	fmt.Println(maxSum)
}