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

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

简单题 藻类植物

每年的递推公式就是 x = r*x - d，通过循环计算 2025-2034 年的藻类植物总重

package main

import "fmt"

func main() {
	var r, d, x int
	fmt.Scan(&r, &d, &x)
	for i := 0; i < 10; i++ {
		x = r*x - d
		fmt.Println(x)
	}
}

中等题 小红的蛋糕切割

1. 计算二维前缀和数组 s。
2. 枚举所有可能的正方形子矩阵，计算其美味度和 s1。
3. 使用总美味度和减去 s1 得到 s2。
4. 计算两者的差值绝对值，并更新最小值。

package main

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

func abs(x int) int {
	if x < 0 {
		return -x
	}
	return x
}

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

	var n, m int
	fmt.Fscan(in, &n, &m)
	a := make([][]int, n+1)
	s := make([][]int, n+1)
	for i := 0; i <= n; i++ {
		a[i] = make([]int, m+1)
		s[i] = make([]int, m+1)
	}
	for i := 1; i <= n; i++ {
		for j := 1; j <= m; j++ {
			fmt.Fscan(in, &a[i][j])
			s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1] + a[i][j]
		}
	}
	total := s[n][m]
	minDiff := math.MaxInt

	for i := 1; i <= n; i++ {
		for j := 1; j <= m; j++ {
			for size := 1; i+size-1 <= n && j+size-1 <= m; size++ {
				x1, y1 := i, j
				x2, y2 := i+size-1, j+size-1
				s1 := s[x2][y2] - s[x1-1][y2] - s[x2][y1-1] + s[x1-1][y1-1]
				s2 := total - s1
				diff := abs(s1 - s2)
				if diff < minDiff {
					minDiff = diff
				}
			}
		}
	}

	fmt.Fprintln(out, minDiff)
}

困难题 【模板】整数域三分

算法思路：

• 由于表达式 |kix + ai| + bi 是一个凸函数，它们的和也是凸函数
• 对于凸函数求最小值，可以使用三分法来解决
• 三分法的原理是通过将区间分成三份，比较两个三分点的函数值来缩小搜索范围

关键函数实现：

• check(x)：计算给定 x 值时所有表达式的总和
• threeDivide(left, right)：三分法实现，在区间内寻找最小值
  • 当区间长度大于 3 时，持续缩小搜索范围
  • 最后对剩余的小区间进行暴力搜索以确保精确性

package main

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

var (
	in  *bufio.Reader
	out *bufio.Writer
)

var (
	n       int
	k, a, b []int64
)

func abs(x int64) int64 {
	if x < 0 {
		return -x
	}
	return x
}

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

func check(x int64) int64 {
	var ans int64
	for i := 0; i < n; i++ {
		ans += abs(k[i]*x+a[i]) + b[i]
	}
	return ans
}

func threeDivide(left, right int64) int64 {
	for right-left > 3 {
		mid1 := left + (right-left)/3
		mid2 := right - (right-left)/3
		if check(mid1) > check(mid2) {
			left = mid1
		} else {
			right = mid2
		}
	}
	res := check(left)
	for i := left + 1; i <= right; i++ {
		res = min(res, check(i))
	}
	return res
}

func solve() {
	var l, r int64
	fmt.Fscan(in, &n, &l, &r)
	k = make([]int64, n)
	a = make([]int64, n)
	b = make([]int64, n)
	for i := 0; i < n; i++ {
		fmt.Fscan(in, &k[i], &a[i], &b[i])
	}
	fmt.Println(threeDivide(l, r))
}

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

	var t int
	fmt.Fscan(in, &t)
	for i := 0; i < t; i++ {
		solve()
	}
}