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

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

简单题 变幻莫测

分类讨论，需要自己推。
如果 ，操作次数为 。
如果 ，做一次操作二，操作次数为 。
如果 ，做一次操作一，再做一次操作二，操作次数为 。
如果 ，操作二→操作一→操作二，操作次数为 。
此外无解。

#include <bits/stdc++.h>
using namespace std;
int main() {
    int x, y;
    cin >> x >> y;
    int ans = -1;
    if (x == y)ans = 0;
    else if (y == 0)ans = 1;
    else if (x == 0)ans = 2;
    else if (x + y == 0)ans = 3;
    cout << ans << '\n';
    return 0;
}

中等题 平均数为k的最长连续子数组

将所有 减去 ，问题即变成和为 的最长连续子数组，转化为经典问题。
使用 map 记录前缀和最早出现的位置，即，如果前缀和 出现过， 记录最小的 。
用 下标判断方便，如果 ，当前可能的最长长度为 ；否则如果 保存过 ，则当前可能的最长长度为 ；否则 。
时间复杂度 。

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, k;
    cin >> n >> k;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        a[i] -= k;
    }
    map<long long, int> mp;
    int ans = -1;
    long long presum = 0;
    for (int i = 1; i <= n; i++) {
        presum += a[i];
        if (presum == 0) {
            ans = max(ans, i);
        } else if (mp[presum] != 0) {
            ans = max(ans, i - mp[presum]);
        } else {
            mp[presum] = i;
        }
    }
    cout << ans << '\n';
    return 0;
}

困难题 最大子矩阵

暴力复杂度是 ，应该不能通过，考虑优化。
先枚举行的上下边界 ，求上下边界分别为行 的最大子矩阵和，因为行固定了，可以看成在列上的最大子段和问题。
然后枚举 做dp，套用最大子段和的dp方程来解决，只不过 换成了 ，可以通过二维前缀和快速得出 。
时间复杂度 。

#include <bits/stdc++.h>
using namespace std;
constexpr int N = 105;
int a[N][N];
long long pre[N][N];
int main() {
    int n;
    cin >> n;
    long long ans = numeric_limits<long long>::min();
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            cin >> a[i][j];
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            pre[i][j] = pre[i - 1][j] + pre[i][j - 1] - pre[i - 1][j - 1] + a[i][j];
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = i; j <= n; j++) {
            long long sum = 0;
            for (int k = 1; k <= n; k++) {
                sum += pre[j][k] - pre[i - 1][k] - pre[j][k - 1] + pre[i - 1][k - 1];
                ans = max(ans, sum);
                if (sum < 0) sum = 0;
            }
        }
    }
    cout << ans << '\n';
    return 0;
}