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

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

简单题 小红的正整数计数

1. 通过标准输入读取两个整数 l 和 r，分别代表范围的左右边界
2. 初始化计数器 sum 为 0
3. 从 l 到 r 遍历每个数字：
   • 如果当前数字能被2整除（即偶数），计数器 sum 加1
4. 最后输出偶数的个数

package main

import "fmt"

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

中等题 【模板】堆

1. 使用 Go 语言的 container/heap 包来实现优先队列
2. 定义 PriorityQueue 类型为 []int 的切片
3. 实现堆接口所需的五个方法：
   • Len() - 返回堆的长度
   • Less(i, j int) - 比较函数，这里用 > 实现大根堆
   • Swap(i, j int) - 交换元素
   • Push(x interface{}) - 添加元素
   • Pop() interface{} - 删除末尾元素

package main

import (
	"container/heap"
	"fmt"
)

type PriorityQueue []int

func (pq PriorityQueue) Len() int           { return len(pq) }
func (pq PriorityQueue) Less(i, j int) bool { return pq[i] > pq[j] }
func (pq PriorityQueue) Swap(i, j int)      { pq[i], pq[j] = pq[j], pq[i] }

func (pq *PriorityQueue) Push(x interface{}) {
	*pq = append(*pq, x.(int))
}

func (pq *PriorityQueue) Pop() interface{} {
	old := *pq
	n := len(old)
	item := old[n-1]
	*pq = old[0 : n-1]
	return item
}

func main() {
	pq := &PriorityQueue{}
	heap.Init(pq)
	var n int
	fmt.Scan(&n)
	for i := 0; i < n; i++ {
		var op string
		fmt.Scan(&op)
		switch op {
		case "push":
			var x int
			fmt.Scan(&x)
			heap.Push(pq, x)
		case "pop":
			if pq.Len() > 0 {
				fmt.Println(heap.Pop(pq))
			} else {
				fmt.Println("empty")
			}
		case "top":
			if pq.Len() > 0 {
				fmt.Println((*pq)[0])
			} else {
				fmt.Println("empty")
			}
		}
	}
}

困难题 【模板】二维差分

1. 差分数组的构建：

b[i][j] = a[i][j] - a[i-1][j] - a[i][j-1] + a[i-1][j-1]

2. 区域更新操作： 当要将左上角 (x1,y1) 到右下角 (x2,y2) 的矩形区域都加上值 c 时，需要在差分数组上进行以下操作：

b[x1][y1] += c        // 左上角
b[x2+1][y1] -= c      // 左下角
b[x1][y2+1] -= c      // 右上角
b[x2+1][y2+1] += c    // 右下角

3. 还原原数组：

a[i][j] = a[i-1][j] + a[i][j-1] - a[i-1][j-1] + b[i][j]

#include <bits/stdc++.h>
using namespace std;
const int N=1010;
long long a[N][N],b[N][N];

int main(){
    int m,n,q,x1,y1,x2,y2,c;
    cin>>n>>m>>q;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>a[i][j];
            b[i][j]=a[i][j]-a[i-1][j]-a[i][j-1]+a[i-1][j-1];  //构造差分数组
        }
    }
    
    while(q--){
        cin>>x1>>y1>>x2>>y2>>c;
        b[x1][y1]+=c;
        b[x2+1][y1]-=c;
        b[x1][y2+1]-=c;
        b[x2+1][y2+1]+=c;
    }
    
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            a[i][j]=a[i-1][j]+a[i][j-1]-a[i-1][j-1]+b[i][j];
            cout<<a[i][j]<<" \n"[j==m];
        }
    }
    return 0;
}