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

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

简单题 藻类植物

题面给出了递推式，直接根据递推式循环 次计算 即可。

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

中等题 小红的蛋糕切割

首先需要二维前缀和维护一段矩阵的和。
设整个矩阵的和为 ，如果知道了正方形内的和 ，则美味度之差为 。
首先可以想到枚举正方形左上角的点，再暴力枚举正方形的边长。
该算法时间复杂度为 ，因为本题bug，可以通过。
考虑优化：
仍然枚举正方形左上角的点，但是在枚举边长时，因为 ，所以 对于边长 单调递增， 对于 应当是一个单峰函数，所以可以三分 来寻找这个函数的极值。
或者可以把绝对值去掉，这样就变成了严格单调递减的函数，可以二分最接近 的点。
时间复杂度为 。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll a[1003][1003];
ll pre[1003][1003];
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    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];
    ll ans = 8e18;
    ll sum = pre[n][m];
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            int l = 1, r = min(n - i + 1, m - j + 1);
            auto calc = [&](int x) -> ll {
                return abs(sum - 2 * (pre[i + x - 1][j + x - 1] - pre[i + x - 1][j - 1] - pre[i - 1][j + x - 1] + pre[i - 1][j - 1]));
            };
            while (l < r) {
                if (r - l <= 2) {
                    for (int k = l; k <= r; k++)
                        ans = min(ans, calc(k));
                    break;
                }
                int mid1 = (l + r) / 2;
                int mid2 = mid1 + 1;
                ll ans1 = calc(mid1);
                ll ans2 = calc(mid2);
                if (ans1 == ans2) {
                    l = mid1;
                    r = mid2;
                } else if (ans1 < ans2) {
                    r = mid2;
                } else {
                    l = mid1;
                }
            }
        }
    }
    cout << ans << '\n';
    return 0;
}

困难题 【模板】整数域三分

三分主要用来寻找单峰函数的最值。
本题的 是一个存在最小值的单峰函数。
三分过程中，首先取两个点 。
如果 ，则 。
如果 ，则 。
如果 ，则 。
当 时，取中点比较麻烦，直接暴力计算该区间内所有数的函数值即可。
时间复杂度 。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct line {
    int k, a, b;
};
void solve() {
    int n, l, r;
    cin >> n >> l >> r;
    ll ans = 8e18;
    vector<line> f(n);
    for (int i = 0; i < n; i++)cin >> f[i].k >> f[i].a >> f[i].b;
    auto calc = [&](int x) -> ll {
        ll sum = 0;
        for (int i = 0; i < n; i++)
            sum += abs(1ll * f[i].k * x + f[i].a) + f[i].b;
        return sum;
    };
    while (l < r) {
        if (r - l <= 2) {
            for (int i = l; i <= r; i++)
                ans = min(ans, calc(i));
            break;
        }
        int mid1 = l + (r - l) / 3;
        int mid2 = l + (r - l) * 2 / 3;
        ll ans1 = calc(mid1);
        ll ans2 = calc(mid2);
        if (ans1 == ans2) {
            l = mid1;
            r = mid2;
        } else if (ans1 < ans2)r = mid2;
        else l = mid1;
    }
    cout << ans << '\n';
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--)solve();
    return 0;
}