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

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

简单题 小红的正整数构造

暴力枚举 内是否存在 的倍数。

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

中等题 数独数组

记数字 的出现次数为 。

1. 当 时， 个数字的出现次数必须相等，。
2. 否则，就有 个数的出现次数比其他数多 ，。

所以存在的数独数组的条件是 。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void solve() {
    int n;
    cin >> n;
    int cnt[9] = {};
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        cnt[x - 1]++;
    }
    int maxx = *max_element(cnt, cnt + 9);
    int minn = *min_element(cnt, cnt + 9);
    if (maxx > minn + 1) {
        cout << "NO\n";
        return;
    }
    cout << "YES";
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    // int t=1;cin>>t;while(t--)
    solve();
    return 0;
}

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

和一维前缀和一样的思想，记 为 且 内所有 的和。
的计算式为 ，类似于一维前缀和， 应该可以通过 来计算，但是直接使用 计算会重复加了 这一部分，应该减去。
以 为左上角, 为右下角的子矩阵的和 ，同样子矩阵的和应该能通过 来计算，但是直接使用 计算会多减去了 这一部分，应该加上。

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