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

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

简单题 查找组成一个偶数最接近的两个素数

从 开始暴力枚举 ，判断 和 是否均为素数。

#include <bits/stdc++.h>
using namespace std;
bool isprime(int n) {
    if (n == 1)return false;
    for (int i = 2; i <= sqrt(n); i++)
        if (n % i == 0)
            return false;
    return true;
}
int main() {
    int n;
    cin >> n;
    for (int i = n / 2; i >= 2; i--) {
        if (isprime(i) && isprime(n - i)) {
            cout << i << '\n' << n - i << '\n';
            return 0;
        }
    }
    return 0;
}

中等题 最小循环节

输出字符串内不同字符的个数。

#include <bits/stdc++.h>
using namespace std;
int main() {
    string s;
    cin >> s;
    vector<int> a(128);
    for (auto it : s)a[it] = 1;
    int ans = 0;
    for (int i = 0; i < 128; i++)ans += a[i];
    cout << ans << '\n';
    return 0;
}

困难题 连续子数组最大和

设 为到当前位置的最大子段和，当 时将 置为 。 为 的最大值。
但是要至少选长度为 的连续子数组，所以特判全为负数的情况，全为负数的情况则输出整个数组的最大值。

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++)cin >> a[i];
    long long ans = 0, tmp = 0;
    for (int i = 0; i < n; i++) {
        tmp += a[i];
        if (tmp < 0)tmp = 0;
        ans = max(ans, tmp);
    }
    if (*max_element(a.begin(), a.end()) < 0)
        cout << *max_element(a.begin(), a.end()) << '\n';
    else
        cout << ans << '\n';
    return 0;
}