Link

牛客练习赛125

A

。

C++ Code 
#include "bits/stdc++.h"

using namespace std;
using i64 = int64_t;

void solve() {
    vector<int> a(5);
    for (int i = 0; i < 5; i++) {
        cin >> a[i];
    }
    int ans = 4;
    for (int i = 1; i < 5; i++) {
        if (a[i] <= a[0]) {
            ans--;
        }
    }
    cout << ans << '\n';
}

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

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

    return 0;
}

B

将 排除在外数质数个数。

因为 都是质数，其他的数操作一次就不能再操作了。

。

用欧拉筛复杂度更优。

C++ Code 
#include "bits/stdc++.h"

using namespace std;
using i64 = int64_t;

bool isprime(int x) {
    if (x < 2) {
        return false;
    }
    for (int i = 2; i <= x / i; i++) {
        if (x % i == 0) {
            return false;
        }
    }
    return true;
}
void solve() {
    int n;
    cin >> n;
    int cnt = 0;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        if (x != 3 && isprime(x)) {
            cnt++;
        }
    }
    cout << (cnt ? 1 - cnt % 2 : -1) << '\n';
}

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

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

    return 0;
}

C

设一个数第一位为 ，最后一位为 ，中间为 ，然后枚举 ，检查合法性。

例如：alt 。

本质是 去掉最高位加 去掉最低位。

。

C++ Code 
#include "bits/stdc++.h"

using namespace std;
using i64 = int64_t;
constexpr i64 inf = 1E17;
void solve() {
    i64 y;
    cin >> y;
    int ans = 0;
    for (int c = 0; c < 10; c++) {
        for (int a = 1; a < 10; a++) {
            for (i64 p = 1; p < inf; p = p * 10) {
                i64 b = y - p * a - c;
                if (b >= 0 && b % 11 == 0 && p > b / 11) {
                    ans++;
                }
            }
        }
    }
    cout << ans << '\n';
}

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

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

    return 0;
}

D

树状数组，dp，离散化。

将不同颜色离散化后，枚举颜色，进而转化为常见的树状数组维护 dp。

。

C++ Code 
#include "bits/stdc++.h"

using namespace std;
using i64 = int64_t;

template <class T> 
struct Fenwick {
    int n;
    vector<T> a;
    Fenwick(int n = 0) : n(n), a(n, T()) {}
    void modify(int i, T x) {
        for (i++; i <= n; i += i & -i) {
            a[i - 1] += x;
        }
    }
    T get(int i) {
        T res = T();
        for (; i > 0; i -= i & -i) {
            res += a[i - 1];
        }
        return res;
    }
};
struct Max {
    i64 x;
    Max(i64 x = 0) : x(x) {}

    Max &operator+=(const Max &a) {
        x = max(a.x, x);
        return *this;
    }
};

void solve() {
    int n, m;
    cin >> n >> m;
    vector a(n, vector<int>(m));
    vector<int> v;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> a[i][j];
            v.push_back(a[i][j]);
        }
    }

    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());

    int nv = v.size();
    vector<vector<tuple<int, int, int>>> pos(nv);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            int c;
            cin >> c;
            int k = lower_bound(v.begin(), v.end(), a[i][j]) - v.begin();
            pos[k].emplace_back(i, j, c);
        }
    }

    i64 ans = 0;
    for (int i = 0; i < nv; i++) {
        vector<int> y;
        for (auto [_, yi, c] : pos[i]) {
            y.push_back(yi);
        }

        sort(y.begin(), y.end());
        y.erase(unique(y.begin(), y.end()), y.end());

        int ny = y.size();
        Fenwick<Max> f(ny);
        for (auto [_, yi, c] : pos[i]) {
            yi = lower_bound(y.begin(), y.end(), yi) - y.begin();
            i64 res = f.get(yi + 1).x + c;
            ans = max(ans, res);
            f.modify(yi, res);
        }
    }
    cout << ans << '\n';
}

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

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

    return 0;
}