题解 | #牛客小白月赛79#

A

从后往前找第一位偶数。

$O(n)$ 。

C++ Code

#include "bits/stdc++.h"

using namespace std;
using i64 = long long;

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

    string s;
    cin >> s;
    int n = s.size();
    for (int i = n - 1; i >= 0; i--) {
        if ((s[i] - '0') % 2 == 0) {
            cout << n - i - 1 << '\n';
            return 0;
        }
    }
    cout << n << '\n';  

    return 0;
}

B

求和，若和为奇数则减去最小奇数。

$O(n)$ 。

C++ Code

#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 mn = 1E9, ans = 0;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        ans += x;
        if (x % 2 == 1) {
            mn = min(mn, x);
        }
    }
    if (ans % 2 == 1) {
        ans -= mn;
    }
    cout << ans << '\n';

    return 0;
}

C

若存在 $a_i$ 为 $0$ ，取区间 $[i,i 1],[i-1,i]$ ；取区间 $[1,n]$ ，对上述区间的 $f$ 取 $\max$ 。

$O(n)$ 。

C++ Code

#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);
    vector<int> vis(n + 1);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        vis[a[i]] = 1;
    }

    int ans = 0;
    for (int i = 0; i < n; i++) {
        if (a[i] == 0) {
            if (i + 1 < n) {
                ans = max(ans, a[i + 1]);
            }
            if (i - 1 >= 0) {
                ans = max(ans, a[i - 1]);
            }
        }
    }

    int mex = 0;
    while (vis[mex]) {
        mex++;        
    }

    if (mex > 1) {
        ans = max(ans, mex);
    }    
    cout << ans << '\n';

    return 0;
}

D

显然不存在 $-1$ 。

两个操作，操作一是对 $n$ 加 $1$ ，操作二是对 $n$ 乘 $2$ 。

枚举做操作一的次数即可，显然不超过 $20$ 次。

$O(20\cdot t)$ 。

C++ Code

#include "bits/stdc++.h"

using namespace std;
using i64 = long long;

void solve() {
    int n;
    cin >> n;
    int ans = 1E9;
    for (int i = 0; i < 20; i++) {
        ans = min(ans, max(0, 20 - __builtin_ctz(n + i)) + i);
    }
    cout << ans << '\n';
}

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

    int t;
    cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

E

式子为 $(6^{7}\cdot n)^{2^{m}}\pmod{10}$ 。

欧拉降幂。

$\varphi(10)$ 为 $4$ 。

$6^{7}\pmod{10}$ 为 $6$ 。

C++ Code

#include "bits/stdc++.h"

using namespace std;
using i64 = long long;

int power(int a, int b, int p) {
    int res = 1;
    for (; b; b >>= 1, a = i64(a) * a % p) {
        if (b & 1) {
            res = i64(res) * a % p;
        } 
    }
    return res;
}

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

    int n, m;
    cin >> n >> m;
    if (n < 7) {
        cout << "-1\n";
    } else {
        int k = power(2, m, 4);
        
        if (m >= 2) {
            k += 4;
        }
        cout << power(n % 10 * 6 % 10, k, 10) << '\n';
    }

    return 0;
}

F

$\text{dp}$ 。

记录构造方案时使用了暴力，感觉复杂度怪怪的。

C++ Code

#include "bits/stdc++.h"

using namespace std;
using i64 = long long;

#define range(a) begin(a), end(a)

constexpr int N = 1000;

void solve() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        a[i] %= N;
    }
  
    vector<int> f(N);
    vector<vector<int>> p(N);
    for (int i = 0; i < n && !f[0]; i++) {
        vector<int> v;
        for (int j = 0; j < N && !f[0]; j++) {
            int x = (j + a[i]) % N;
            if (f[j] && !f[x]) {
                v.push_back(x);
            }
        }
        for (auto &x : v) {
            int y = (x - a[i] + N) % N;
            p[x].insert(p[x].end(), range(p[y]));
            p[x].push_back(i);
            f[x] = 1;
        }
        if (!f[a[i]]) {
            p[a[i]].push_back(i);
            f[a[i]] = 1;
        }
    }

    if (f[0]) {
        cout << accumulate(range(a), 0) % N << '\n';
        int M = p[0].size();
        cout << M << ' ';
        for (int i = 0; i < M; i++) {
            cout << p[0][i] + 1 << " \n"[i == M - 1];
        }
    } else {
        cout << "-1\n";
    }
}

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

    int t;
    cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}