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

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

简单题 小红的正整数计数

按题意从 内逐个枚举判断是否是 的倍数。

#include <bits/stdc++.h>
using namespace std;
int main() {
    int l, r;
    cin >> l >> r;
    int ans = 0;
    for (int i = l; i <= r; i++)
        if (i % 2 == 0)
            ans++;
    cout << ans << '\n';
    return 0;
}

中等题 【模板】堆

C++ STL 中有 std::priority_queue 优先队列可以看作堆这种数据结构，需要 #include <queue>。
这样创建 std::priority_queue<T> 是大根堆，和题目一致。
需这样创建小根堆： std::priority<T, vector<T>, greater<T>>
成员函数如下：
pop() 弹出堆顶，如果堆内没有元素则会 RE。
top() 输出堆顶，如果堆内没有元素则会 RE。
push(x) 向堆内插入 x。
size() 获得堆内元素个数。
empty() 判定堆是否为空。

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n;
    cin >> n;
    priority_queue<int> pq;
    while (n--) {
        string op;
        cin >> op;
        if (op == "push") {
            int x;
            cin >> x;
            pq.push(x);
        }
        if (op == "top") {
            if (pq.empty())cout << "empty\n";
            else cout << pq.top() << '\n';
        }
        if (op == "pop") {
            if (pq.empty())cout << "empty\n";
            else {
                cout << pq.top() << '\n';
                pq.pop();
            }
        }
    }
    return 0;
}

困难题 【模板】二维差分

记差分数组为 。
给 加上 相当于给 的元素都加上了 。
那我们可以这样操作：

1. 
2. 
3. 
   发现 这段区间多减去了 ，因此给这段区间加上 。
4. 

此后仍然是对 数组做前缀和，不过这次是做二维前缀和。

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, m, q;
    cin >> n >> m >> q;
    vector<vector<long long>> a(n + 2, vector<long long>(m + 2));
    vector<vector<long long>> cf(n + 2, vector<long long>(m + 2));
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            cin >> a[i][j];
    while (q--) {
        int x1, y1, x2, y2, k;
        cin >> x1 >> y1 >> x2 >> y2 >> k;
        cf[x2 + 1][y2 + 1] += k;
        cf[x2 + 1][y1] -= k;
        cf[x1][y2 + 1] -= k;
        cf[x1][y1] += k;
    }
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            cf[i][j] += cf[i - 1][j] + cf[i][j - 1] - cf[i - 1][j - 1];
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            cout << a[i][j] + cf[i][j] << " \n"[j == m];
    return 0;
}