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

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

简单题 彩虹糖的梦

因为每一位小朋友都想要吃到全部七种颜色的彩虹糖，所以一共只能分给这七种糖中数量最少的个数。

a = list(map(int, input().split()))
print(min(a))

中等题 小红走网格

• 计算 dx = gcd(c,d)：表示在 x 方向上最小的移动单位
• 计算 dy = gcd(a,b)：表示在 y 方向上最小的移动单位
• 判断条件：
  • 如果 x%dx == 0 且 y%dy == 0，则可以到达
  • 否则不可到达

1. 为什么这样判断是正确的？
   • 因为任何通过这两种移动方式能到达的点，其坐标一定是各自最大公约数的倍数
   • 如果坐标不能被对应的最大公约数整除，那么无论如何组合这些移动，都无法到达该点

package main

import "fmt"

func main() {
	var n int
	fmt.Scan(&n)
	st := make([]int, 10)
	for i := 0; i < n; i++ {
		var x int
		fmt.Scan(&x)
		st[x]++
	}
	min, max := n, 0
	for i := 1; i <= 9; i++ {
		if st[i] > max {
			max = st[i]
		}
		if st[i] < min {
			min = st[i]
		}
	}
	if max-min <= 1 {
		fmt.Println("YES")
	} else {
		fmt.Println("NO")
	}
}

困难题 【模板】差分

差分可以看成前缀和的逆运算。

首先给定一个原数组a：a[1], a[2], a[3]... a[n];

然后我们构造一个数组b ： b[1] ,b[2] , b[3]... b[i];

使得 a[i] = b[1] + b[2]+ b[3] +...+ b[i]

也就是说，a数组是b数组的前缀和数组，反过来我们把b数组叫做a数组的差分数组。换句话说，每一个a[i]都是b数组中从头开始的一段区间和。

考虑如何构造差分b数组？

最为直接的方法

如下：

a[0]= 0;
b[1] = a[1] - a[0];
b[2] = a[2] - a[1];   a[2] = s[2] - s[1]
b[3] = a[3] - a[2];
........
b[n] = a[n] - a[n-1];

给定区间[l ,r]，让我们把a数组中的[l, r]区间中的每一个数都加上c, 即 a[l] + c , a[l+1] + c , a[l+2] + c ,,,,,, a[r] + c;

暴力做法是for循环l到r区间，时间复杂度O(n)，如果我们需要对原数组执行m次这样的操作，时间复杂度就会变成O(n*m)。

有没有更高效的做法吗? 考虑差分做法。

a[i] = b[1...i]

包含 b[i] ：a[i, n]

始终要记得，a数组是b数组的前缀和数组，比如对b数组的b[i]的修改，会影响到a数组中从a[i]及往后的每一个数。

首先让差分b数组中的 b[l] + c ,a数组变成 a[l] + c ,a[l+1] + c ... a[n] + c; a数组范围[l, n] + c

然后我们打个补丁，b[r+1] - c, a数组变成 a[r+1] - c,a[r+2] - c ... a[n] - c; a[r+1，n]- c

package main

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

func main() {
	var n, m int
	in := bufio.NewReader(os.Stdin)
	out := bufio.NewWriter(os.Stdout)
	defer out.Flush()

	fmt.Fscan(in, &n, &m)

	a := make([]int, n+1)
	b := make([]int, n+2)
	for i := 1; i <= n; i++ {
		fmt.Fscan(in, &a[i])
		b[i] = a[i] - a[i-1]
	}

	for i := 0; i < m; i++ {
		var l, r, c int
		fmt.Fscan(in, &l, &r, &c)
		b[l] += c
		b[r+1] -= c
	}

	for i := 1; i <= n; i++ {
		a[i] = a[i-1] + b[i]
		fmt.Fprint(out, a[i], " ")
	}
}