牛客春招刷题训练营-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])
}
中等题 高精度整数加法
-
输入处理：
- 用字符串接收两个大数
- 将字符串转换为整数数组，且倒序存储（便于从低位到高位进行计算）
-
实现加法逻辑：
- 确保第一个数组长度大于等于第二个数组
- 使用进位变量t记录每一位相加的进位
- 按位相加并处理进位，当前位结果 = (a[i] + b[i] + t) % 10
- 最后处理剩余进位，新的进位 = (a[i] + b[i] + t) / 10
-
输出结果：
- 将结果数组倒序输出
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)
}
牛客春招刷题训练营 文章被收录于专栏
爱丽姐真是太好了
查看10道真题和解析