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

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

简单题 统计每个月兔子的总数

a[i] 表示出生后第 i 个月兔子的数量

因为出生后三个月的兔子每只兔子都可以生育新的兔子，所以 的都包含在 a[3] 中。

每过一个月，出生后第一个月的兔子变为第二个月，出生后第二个月的兔子变为第三个月，出生后第三个月（包含大于等于第三个月）的兔子生育出生后第一个月的兔子。

package main

import "fmt"

func main() {
	var n int
	fmt.Scan(&n)
	a := [4]int{0, 1}
	for i := 2; i <= n; i++ {
		a[2], a[3] = a[1], a[3]+a[2]
		a[1] = a[3]
	}
	fmt.Println(a[1] + a[2] + a[3])
}

中等题 高精度整数加法

1. 输入处理：

   • 用字符串接收两个大数
   • 将字符串转换为整数数组，且倒序存储（便于从低位到高位进行计算）

2. 实现加法逻辑：

   • 确保第一个数组长度大于等于第二个数组
   • 使用进位变量t记录每一位相加的进位
   • 按位相加并处理进位，当前位结果 = (a[i] + b[i] + t) % 10
   • 最后处理剩余进位，新的进位 = (a[i] + b[i] + t) / 10

3. 输出结果：

   • 将结果数组倒序输出

package main

import (
	"fmt"
)

func main() {
	var s1, s2 string
	fmt.Scan(&s1, &s2)

	a, b := make([]int, 0), make([]int, 0)
	for i := len(s1) - 1; i >= 0; i-- {
		a = append(a, int(s1[i]-'0'))
	}
	for i := len(s2) - 1; i >= 0; i-- {
		b = append(b, int(s2[i]-'0'))
	}

	if len(a) < len(b) {
		a, b = b, a
	}

	c := make([]int, 0)
	t := 0

	for i := 0; i < len(a); i++ {
		t += a[i]
		if i < len(b) {
			t += b[i]
		}
		c = append(c, t%10)
		t /= 10
	}

	if t > 0 {
		c = append(c, t)
	}

	for i := len(c) - 1; i >= 0; i-- {
		fmt.Print(c[i])
	}
}

困难题 喜欢切数组的红

方案一 时间复杂度

主体思路：遍历第二段，第一段的信息包含在 mp 中，其中因为mp是前缀的关系，保证是递增数组。通过二分查找来找到第一个小于 cnt[i] 的位置，确保第一段包含正数。

package main

import (
	"fmt"
	"sort"
)

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

	sum := make([]int64, n+1) // 1～i的前缀和
	cnt := make([]int, n+1)   // 1～i的正数个数
	for i := 1; i <= n; i++ {
		sum[i] = sum[i-1] + a[i]
		if a[i] > 0 {
			cnt[i] = cnt[i-1] + 1
		} else {
			cnt[i] = cnt[i-1]
		}
	}

	ans := 0
	mp := make(map[int64][]int) // mp的value是存放的是第一段包含正数的个数
	mp[a[1]] = []int{cnt[1]}
	for i := 2; i <= n-1; i++ { // 遍历第二段的终点
		if sum[i]%2 == 0 { // 如果第一段+第二段的和是偶数
			if sum[n]-sum[i] == sum[i]/2 { // 如果第三段的和等于第一段+第二段的和的一半
				if cnt[i] > 0 && cnt[n]-cnt[i] > 0 { // 如果第一段+第二段和第三段都包含正数
					ans += sort.SearchInts(mp[sum[i]/2], cnt[i]) // 找到第一段包含的正数个数
				}
			}
		}
		if cnt[i] > 0 {
			mp[sum[i]] = append(mp[sum[i]], cnt[i])
		}
	}

	fmt.Println(ans)
}

方案二 时间复杂度

参考 https://www.nowcoder.com/discuss/690318541862559744 的思路

因为三段的和相等且为正数，所以保证存在方案数一定是 sum[n] 可以被 3 整除且 cnt[n] 要大于等于 3，每段的和都为 sum[n]/3

dp[i] 表示第三段符合的方案数

枚举第一段的结尾下标记为 i ，那么第二段的开始下标就是 i+1，nxt[i+1] 表示满足包含正数时最小的第二段的结尾下标，那么 nxt[i+1] + 1 就是最小的第三段的开始下标

然后就是满足每段包含正数且和为 sum[n]/3 条件即可

package main

import (
	"fmt"
)

func main() {
	var n int
	fmt.Scan(&n)
	a := make([]int64, n+1)
	sum := make([]int64, n+1) // 1～i的前缀和
	cnt := make([]int, n+1)   // 1～i的正数个数
	for i := 1; i <= n; i++ {
		fmt.Scan(&a[i])
		sum[i] = sum[i-1] + a[i]
		if a[i] > 0 {
			cnt[i] = cnt[i-1] + 1
		} else {
			cnt[i] = cnt[i-1]
		}
	}

	if sum[n]%3 != 0 || cnt[n] < 3 {
		fmt.Println(0)
		return
	}
	s := sum[n] / 3

	dp := make([]int, n+2) // i到n的区间中，和为s的个数

	for i := n; i >= 1; i-- {
		if sum[n]-sum[i-1] == s && cnt[n]-cnt[i-1] > 0 {
			dp[i] = dp[i+1] + 1
		} else {
			dp[i] = dp[i+1]
		}
	}

	nxt := make([]int, n+2) // i之后（包括i）下一个正数的位置
	nxt[n+1] = n + 1
	for i := n; i >= 1; i-- {
		if a[i] > 0 {
			nxt[i] = i
		} else {
			nxt[i] = nxt[i+1]
		}
	}

	ans := 0
	for i := 1; i < n; i++ {
		if sum[i] == s && cnt[i] > 0 {
			if nxt[i+1]+1 > n {
				continue
			}
			ans += dp[nxt[i+1]+1]
		}
	}
	fmt.Println(ans)
}