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

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

简单题 循环求和

初步思路：发现分别求奇偶项的和：求 的和， 的和，二者相加为答案。
但是数据范围太大，等差数列求和后结果为 量级，不能接受。
然后考虑前缀和：发现数列的前缀和为 ，有通项公式。
记 ，本题即为求 。
时间复杂度 。

#include <bits/stdc++.h>
using namespace std;
void solve() {
    long long l, r;
    cin >> l >> r;
    l--;
    long long ansl, ansr;
    if (l % 2 == 1)ansl = (l + 1) / 2;
    else ansl = -(l + 1) / 2;
    if (r % 2 == 1)ansr = (r + 1) / 2;
    else ansr = -(r + 1) / 2;
    cout << ansr - ansl << '\n';
}
int main() {
    int t;
    cin >> t;
    while (t--)solve();
    return 0;
}

中等题 小美走公路

按顺逆时针方向走两遍，统计两个方向上的答案，输出两种方向上答案的最小值。
将 数组复制一份拼接在后面。
假设 ，这样即求 。
如果 ，只需将 交换，按同样的方法求。

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n;
    cin >> n;
    vector<int> a(2 * n + 1);
    for (int i = 1; i <= n; i++)cin >> a[i];
    for (int i = 1; i <= n; i++)a[i + n] = a[i];
    int x, y;
    cin >> x >> y;
    if (x > y)swap(x, y);
    long long ans1 = 0, ans2 = 0;
    for (int i = x; i < y; i++)ans1 += a[i];
    for (int i = y; i < n + x; i++)ans2 += a[i];
    cout << min(ans1, ans2) << '\n';
    return 0;
}

困难题 游游的除2操作

可以证明，对于每个数最多操作 次，因为对每个数操作 次后都会变成 。
我们将这种操作成为一轮：本轮开始前记录 的最小值 ，然后遍历 ，尝试将 除以 变成 ，如果变不成则继续将 除以 使得 。
这种操作最多不会超过 轮。
只需要一轮一轮操作记录答案即可。
时间复杂度 ， 为 的最大值。

#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];
    int ans = 0;
    while (count(a.begin(), a.end(), a[0]) != n) {
        int minn = *min_element(a.begin(), a.end());
        for (auto& it : a)
            while (it > minn) {
                it /= 2;
                ans++;
            }
    }
    cout << ans;
    return 0;
}