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

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

简单题 小美的因子查询

x 是否存在至少一个偶数因子 <==> x 是否为偶数

package main

import "fmt"

func main() {
	var t int
	fmt.Scan(&t)
	for i := 0; i < t; i++ {
		var x int
		fmt.Scan(&x)
		if x%2 == 0 {
			fmt.Println("YES")
		} else {
			fmt.Println("NO")
		}
	}
}

中等题 跳台阶扩展问题

f(n) 表示跳上n级台阶的总跳法数。

观察规律：

• 如果青蛙第一次跳了1级，那么剩下的就是n-1级，有f(n-1)种跳法。
• 如果第一次跳了2级，那么剩下的就是n-2级，有f(n-2)种跳法。
• …
• 如果第一次直接跳了n级，那么剩下的是0级（也算1种完成的方法）。

所以公式是：

其中，初始条件是：（跳上0级台阶，有1种方式：什么都不做。）

我们可以推导进一步优化

package main

import "fmt"

func main() {
	var n int
	fmt.Scan(&n)
	fmt.Println(1 << (n - 1))
}

困难题 能量项链

为了处理环形的情况，将数组复制一份接在后面，长度变为 2n

2. DP状态定义：

• dp[i][j] 表示区间 [i,j] 内的最大值

3. 状态转移：

• 枚举区间长度 l，从3开始，因为至少需要 2 颗珠（3 个值）才能合并

• 对于每个区间 [i,j]，枚举中间点 k

• 状态转移方程：dp[i][j] = max(dp[i][j], dp[i][k] + dp[k][j] + a[i]*a[k]*a[j])

• 其中 a[i]*a[k]*a[j] 是选择这三个点形成三角形的得分

4. 最终答案：

• 枚举所有长度为 n+1 的区间（即原始序列的完整一圈）
• 取所有这些区间中的最大值

package main

import "fmt"

const MOD = 1000000007

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

func main() {
	var n int
	fmt.Scan(&n)
	a := make([]int64, 2*n)
	for i := 0; i < n; i++ {
		fmt.Scan(&a[i])
		a[i+n] = a[i]
	}
	dp := make([][]int64, 2*n)
	for i := 0; i < 2*n; i++ {
		dp[i] = make([]int64, 2*n)
	}
	for l := 3; l <= n+1; l++ {
		for i := 0; i+l-1 < 2*n; i++ {
			j := i + l - 1
			for k := i + 1; k <= j-1; k++ {
				dp[i][j] = max(dp[i][j], dp[i][k]+dp[k][j]+a[i]*a[k]*a[j])
			}
		}
	}
	ans := int64(0)
	for i := 0; i < n; i++ {
		ans = max(ans, dp[i][i+n])
	}
	fmt.Println(ans % MOD)
}