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

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

简单题 构造A+B

满足正整数 (x,y) 使得 x+y=n ，一共会存在 n-1种情况 (1,n-1)、(2,n-2) 、...、(n-2,2) 、 (n-1,1)

package main

import "fmt"

func main() {
	var n, k int
	fmt.Scan(&n, &k)
	if n-1 >= k {
		fmt.Println("YES")
	} else {
		fmt.Println("NO")
	}
}

中等题 小红的双生排列

如果相邻两项之和为奇数，那么一个数是奇数，一个数是偶数。因此，最终的排列一定是奇数和偶数交替出现。

• 对于长度为 n 的序列，需要将 n/2（向上取整）个奇数和 n/2（向下取整）个偶数交替排列
• 当 n 为奇数时，奇数和偶数的个数分别为 (n+1)/2 和 n/2，分别计算奇数位置和偶数位置的排列数（阶乘）
• 当 n 为偶数时，奇数和偶数的个数相等，都是 n/2，，同样计算两部分的排列数，最后乘2（因为可以用奇数或偶数开头）

package main

import "fmt"

const mod int = 1e9 + 7

func main() {
	var n int
	fmt.Scan(&n)
	ans := 1
	if n%2 == 1 {
		even, odd := n/2, n/2+1
		for i := 1; i <= even; i++ {
			ans = (ans * i) % mod
		}
		for i := 1; i <= odd; i++ {
			ans = (ans * i) % mod
		}
	} else {
		even, odd := n/2, n/2
		for i := 1; i <= even; i++ {
			ans = (ans * i) % mod
		}
		for i := 1; i <= odd; i++ {
			ans = (ans * i) % mod
		}
		ans = (ans * 2) % mod
	}
	fmt.Println(ans)
}

困难题 【模板】前缀和

首先做一个预处理，定义一个 sum 数组，sum[i] 表示 a 数组中前 i 个数的和 sum[i] = a[1] + a[2] + a[3] + ... + a[i]

对于每次查询，只需执行 sum[r] - sum[l - 1] ，时间复杂度为

n,q = map(int,input().split())
a = [0] * (n + 1)
a[1:n + 1] = list(map(int,input().split()))

s = [0] * (n + 1)
for i in range(1,n + 1):
	s[i] = s[i-1] + a[i]

for i in range(q):
	l,r = map(int,input().split())
	print(s[r] - s[l-1])