题解 | #2024牛客寒假算法基础集训营5#

A

数 $1$ 。

$O(n)$ 。

#include "bits/stdc++.h"

using namespace std;
using i64 = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    int ans = n;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        if (x == 1) {
            ans--;
        }
    }
    cout << ans << '\n';

    return 0;
}

B

#include "bits/stdc++.h"

using namespace std;
using i64 = long long;
constexpr int P = 1'000'000'007;

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string s;
    cin >> s;
    int n = s.size();

    vector<i64> f(n);
    f[0] = 1, f[1] = 2;
    for (int i = 2; i <= n; i++) {
        f[i] = (f[i - 1] + f[i - 2]) % P;
    }

    i64 ans = 0;
    for (int i = 0; i < n; i++) {
        if (s[i] == 'm') {
            for (int j = 1; j < 3; j++) {
                for (int k = 1; k < 3; k++) {
                    for (int l = 1; l < 3; l++) {
                        int x = i + j, y = x + k, z = y + l;
                        if (z < n && s[x] == 'y' && s[y] == 'g' && s[z] == 'o') {
                            ans = (ans + f[i] * f[n - z - 1] % P) % P;
                        }
                    }
                }
            }
        }
    }

    cout << ans << '\n';

    return 0;
}

C

考虑在 $a_{i-1},a_i$ 中间插若干个 $0$ 。

$O(n)$ 。

#include "bits/stdc++.h"

using namespace std;
using i64 = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<int> a(n + 2);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    a[0] = a[n + 1] = 1'000'000'000;

    i64 ans = 0;
    for (int i = 1; i <= n + 1; i++) {
        int x = min(a[i - 1], a[i]) - 1;
        ans += x;
        a[i] -= x;
    }

    cout << ans << '\n';

    return 0;
}

E

操作的本质是区间相邻两数之差加一。

$n$ 偶数一定可以。

$n$ 奇数倒着贪心。

$O(\sum n)$ 。

#include "bits/stdc++.h"

using namespace std;
using i64 = long long;

void solve() {
    int n;
    cin >> n;
    vector<i64> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    
    if (n % 2 == 0) {
        cout << "YES\n";
        return;
    }
    
    i64 add = 0;
    for (int i = n - 2; i >= 0; i--) {
        if (a[i + 1] + add < a[i]) {
            cout << "NO\n";
            return;            
        }

        if ((i + 1) % 2 == 0) {
            add += (a[i + 1] + add - a[i]) / (i + 1);
        }
    }
    
    cout << "YES\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    
    return 0;
}

F

在可以的前提下，答案是最大的 $a_{i}-a_{i 1}$ 。

$O(\sum n)$ 。

#include "bits/stdc++.h"

using namespace std;
using i64 = long long;

void solve() {
    int n;
    cin >> n;
    vector<i64> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    
    i64 ans = 0, add = 0;
    for (int i = n - 2; i >= 0; i--) {
        if (n % 2) {
            if (a[i + 1] + add < a[i]) {
                cout << "-1\n";
                return;                
            }
          
            if ((i + 1) % 2 == 0) {
                add += (a[i + 1] + add - a[i]) / (i + 1);
            }      
        }

        ans = max(ans, a[i] - a[i + 1]);
    }
    
    cout << ans << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    
    return 0;
}

G

H

都有解。

一定是一段一段的倒着的连续的数。

线性筛出 $2n$ 以内的质数后倒着构造。

$O(2n)$ 。

#include "bits/stdc++.h"

using namespace std;
using i64 = long long;

vector<int> isprime, primes;
 
void sieve(int n) {
    isprime.assign(n + 1, 1);
    isprime[0] = isprime[1] = 0;
    for (int i = 2; i <= n; i++) {
        if (isprime[i]) {
            primes.push_back(i);
        }
        for (auto p : primes) {
            if (i * p > n) {
                break;
            }
            isprime[i * p] = 0;
            if (i % p == 0) {
                break;
            } 
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    sieve(2 * n);

    vector<int> a(n);

    for (int i = n; i > 0; i--) {
        int x = i + 1;
        while (!isprime[x]) {
            x++;
        }
        for (int j = x - i - 1; j < i; j++) {
            a[j] = x - (j + 1);
        }
        i = x - i;
    }

    for (int i = 0; i < n; i++) {
        cout << a[i] << " \n"[i == n - 1];
    }

    return 0;	
}

I

$O(1)$ 。

#include "bits/stdc++.h"

using namespace std;
using i64 = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t, a, k;
    cin >> t >> a >> k;

    if (a >= min(-k, t - k) && a <= max(k, t + k)) {
        cout << i64(0) + abs(a) + abs(t - a) << '\n';
    } else {
        cout << i64(2) * abs(t - a) + abs(t) << '\n';
    }

    return 0;
}

J

可以看成是在求凸函数极值。

整数三分一下。

记三分次数为 $t$ 。

$O(tn)$ 。

#include "bits/stdc++.h"

using namespace std;
using i64 = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
  
    int n;
    cin >> n;
    vector<int> a(n), b(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i] >> b[i];
    }
  
    auto f = [&](int x) {
        i64 res = 0;
        for (int i = 0; i < n; i++) {
            if (a[i] > x) {
                res += a[i] - x;
                x = a[i];
            } else if (x > b[i]) {
                res += x - b[i];
                x = b[i];
            }
        }
        return res;
    };
  
    int l = a[0], r = b[0];
    for (int times = 0; times < 60; times++) {
        int lm = l + (r - l) / 3, rm = r - (r - l) / 3;
        if (f(lm) < f(rm)) {
            r = rm;
        } else {
            l = lm;
        }
    }
  
    i64 ans = 1E18;
    for (int i = l; i <= r; i++) {
        ans = min(ans, f(i));
    }
    cout << ans << '\n';
    
    return 0;
}

L

$O(1)$

#include "bits/stdc++.h"

using namespace std;
using i64 = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, x;
    cin >> n >> x;

    if ((n + x) % 2) {
        cout << "-1\n";
    } else {
        cout << (n + x) / 2 << ' ' << (n - x) / 2 << '\n';
    }

    return 0;
}

M

可以特判一下 $1,2$ ，然后可以看有没有斜的一样或者竖的一样，有就输出 $1$ ，不然输出 $2$ 。

$O(\sum n)$ 。

#include "bits/stdc++.h"

using namespace std;
using i64 = long long;

void solve() {
    int n;
    cin >> n;
    vector<int> a(n), b(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    for (int i = 0; i < n; i++) {
        cin >> b[i];
    }
    
    if (n == 1 || (n == 2 && a[0] == b[0])) {
        cout << "-1\n";
        return;
    }
    
    for (int i = 0; i + 1 < n; i++) {
        if ((i && a[i] == b[i]) || a[i] == b[i + 1] || b[i] == a[i + 1]) {
            cout << "1\n";
            return;
        }
    }
    cout << "2\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    
    return 0;
}