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

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

简单题 小红的正整数构造

1. 遍历区间 [l, r]，找到第一个能被 x 整除的数字：

   • 用 i%x == 0 判断当前数字是否能被 x 整除
   • 如果找到了，直接输出该数字并返回

2. 如果遍历完整个区间都没找到能被 x 整除的数字，则输出 -1

package main

import "fmt"

func main() {
	var l, r, x int
	fmt.Scan(&l, &r, &x)
	for i := l; i <= r; i++ {
		if i%x == 0 {
			fmt.Println(i)
			return
		}
	}
	fmt.Println(-1)
}

中等题 数独数组

一个数组要想满足当且仅当其每一个长度为 9 的连续子数组，都包含 1～9 这 9 个数字，这个数组中 1～9 出现频率要平衡。

Q：为什么 “max − min ≤ 1” 就够了？

1. 必要性

   设原序列经过重排后得到满足条件的序列 。

   • 对于任何位置 i，窗口 [i,i+8] 与 [i+1,i+9] 都是 1 ~ 9 的全排列；

   • 这两个窗口只差首尾各一个元素，因此 。

     于是序列按 9 为周期循环。

   • 完整的 个周期里，每个数字出现次数相同；

   • 余下的 个位置里，每个数字至多再出现 1 次。

     因此所有数字的出现次数最多相差 1。

2. 充分性

   若 1 ~ 9 的出现次数至多相差 1，设

   

   • 先写下 c 个完整周期（任意同一个 1 ~ 9 的排列）；

   • 把出现次数为 c+1 的那 r 个数字，按同样的顺序接到末尾。

     得到的长度 n 序列显然仍保持 9 周期性，因而每个长度 9 的窗口都是 1 ~ 9。

   所以 “max − min ≤ 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")
	}
}

困难题 【模板】二维前缀和

蓝色面积s[i][j] = 绿色面积s[i-1][j] + 紫色面积s[i][j-1] - 红色面积s[i-1][j-1] + 小方块的面积a[i][j]

绿色面积 = 蓝色面积s[x2, y2] - 黄色面积s[x2, y1 - 1] - 紫色面积s[x1 - 1, y2] + 红色面积 s[x1 - 1, y1 - 1]

package main

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

func main() {
	in := bufio.NewReader(os.Stdin)
	out := bufio.NewWriter(os.Stdout)
	defer out.Flush()

	var n, m, q int
	fmt.Fscan(in, &n, &m, &q)

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

	for i := 0; i < q; i++ {
		var x1, y1, x2, y2 int
		fmt.Fscan(in, &x1, &y1, &x2, &y2)
		result := s[x2][y2] - s[x1-1][y2] - s[x2][y1-1] + s[x1-1][y1-1]
		fmt.Fprintln(out, result)
	}
}