题解 | #2023牛客寒假算法基础集训营6#

A

C++ Code

#include <bits/stdc++.h>

using i64 = long long;

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

    if (x <= 7) {
        std::cout << "very easy\n";
    } else if (x <= 233) {
        std::cout << "easy\n";
    } else if (x <= 10032) {
        std::cout << "medium\n";
    } else if (x <= 114514) {
        std::cout << "hard\n";
    } else if (x <= 1919810) {
        std::cout << "very hard\n";
    } else {
        std::cout << "can not imagine\n";
    }
    
    return 0;
}

B

预处理出 $i$ ( $1\le i\le 2\cdot 10^{5})$ 的所有因子。

C++ Code

#include <bits/stdc++.h>

using i64 = long long;

constexpr int N = 2E5;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    std::vector<std::vector<int>> fac(N + 1);
    for (int i = 1; i <= N; i++) {
        for (int j = i; j <= N; j += i) {
            fac[j].push_back(i);
        }
    }

    int n, q;
    std::cin >> n >> q;

    std::vector<int> a;
    std::vector<std::vector<int>> p(N + 1);

    auto add = [&](int pos, int x) {
        a.push_back(x);
        for (auto num : fac[x]) {
            p[num].push_back(pos);
        }
    };

    for (int i = 0; i < n; i++) {
        int x;
        std::cin >> x;

        add(i, x);
    }
    
    int pos = n - 1;
    for (int i = 0; i < q; i++) {
        int o, x;
        std::cin >> o >> x;
        
        if (o == 1) {
            add(++pos, x);
        } else {
            x--;
            int j = std::lower_bound(p[a[x]].begin(), p[a[x]].end(), x) - p[a[x]].begin();
            std::cout << (int) p[a[x]].size() - j - 1 << '\n';
        }
    }

    return 0;
}

C

C++ Code

#include <bits/stdc++.h>

using i64 = long long;

constexpr int P = 1000000007;
using i64 = long long;
// assume -P <= x < 2P
int norm(int x) {
    if (x < 0) {
        x += P;
    }
    if (x >= P) {
        x -= P;
    }
    return x;
}
template<class T>
T power(T a, i64 b) {
    T res = 1;
    for (; b; b /= 2, a *= a) {
        if (b % 2) {
            res *= a;
        }
    }
    return res;
}
struct Z {
    int x;
    Z(int x = 0) : x(norm(x)) {}
    Z(i64 x) : x(norm(x % P)) {}
    int val() const {
        return x;
    }
    Z operator-() const {
        return Z(norm(P - x));
    }
    Z inv() const {
        assert(x != 0);
        return power(*this, P - 2);
    }
    Z &operator*=(const Z &rhs) {
        x = i64(x) * rhs.x % P;
        return *this;
    }
    Z &operator+=(const Z &rhs) {
        x = norm(x + rhs.x);
        return *this;
    }
    Z &operator-=(const Z &rhs) {
        x = norm(x - rhs.x);
        return *this;
    }
    Z &operator/=(const Z &rhs) {
        return *this *= rhs.inv();
    }
    friend Z operator*(const Z &lhs, const Z &rhs) {
        Z res = lhs;
        res *= rhs;
        return res;
    }
    friend Z operator+(const Z &lhs, const Z &rhs) {
        Z res = lhs;
        res += rhs;
        return res;
    }
    friend Z operator-(const Z &lhs, const Z &rhs) {
        Z res = lhs;
        res -= rhs;
        return res;
    }
    friend Z operator/(const Z &lhs, const Z &rhs) {
        Z res = lhs;
        res /= rhs;
        return res;
    }
    friend std::istream &operator>>(std::istream &is, Z &a) {
        i64 v;
        is >> v;
        a = Z(v);
        return is;
    }
    friend std::ostream &operator<<(std::ostream &os, const Z &a) {
        return os << a.val();
    }
};
struct Comb {
    int n;
    std::vector<Z> _fac;
    std::vector<Z> _invfac;
    std::vector<Z> _inv;
    
    Comb() : n{0}, _fac{1}, _invfac{1}, _inv{0} {}
    Comb(int n) : Comb() {
        init(n);
    }
    
    void init(int m) {
        if (m <= n) return;
        _fac.resize(m + 1);
        _invfac.resize(m + 1);
        _inv.resize(m + 1);
        
        for (int i = n + 1; i <= m; i++) {
            _fac[i] = _fac[i - 1] * i;
        }
        _invfac[m] = _fac[m].inv();
        for (int i = m; i > n; i--) {
            _invfac[i - 1] = _invfac[i] * i;
            _inv[i] = _invfac[i] * _fac[i - 1];
        }
        n = m;
    }
    
    Z fac(int m) {
        if (m > n) init(2 * m);
        return _fac[m];
    }
    Z invfac(int m) {
        if (m > n) init(2 * m);
        return _invfac[m];
    }
    Z inv(int m) {
        if (m > n) init(2 * m);
        return _inv[m];
    }
    Z binom(int n, int m) {
        if (n < m || m < 0) return 0;
        return fac(n) * invfac(m) * invfac(n - m);
    }
} comb;

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

    if (n == 1) {
        std::cout << "1\n1\n";
        return 0;
    }

    Z ans = power(Z(2), n - 1) + (n % 2) * (n - 1) * comb.binom(n - 1, (n - 1) / 2);
    for (int i = 0; i <= (n - 2) / 2; i++) {
        ans += (4 * i + 1) * comb.binom(n - 1, i);
    }
    std::cout << ans << '\n';

    for (int i = 1; i <= n; i++) {
        if (i % 2 == 1) {
            std::cout << i << ' ';
        }
    }
    for (int i = n; i >= 1; i--) {
        if (i % 2 == 0) {
            std::cout << i << ' ';
        }
    }
    std::cout << '\n';

    return 0;
}

D

算出每个位置的贡献，把贡献最大的替换掉。

C++ Code

#include <bits/stdc++.h>

using i64 = long long;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    std::string s;
    std::cin >> s;

    int n = s.size();
    std::vector<i64> pre1(n + 2), pre2(n + 2), suf1(n + 2), suf2(n + 2), val(n);

    for (int i = 1; i <= n; i++) {
        pre1[i] += pre1[i - 1] + (s[i - 1] == 'u');
        pre2[i] += pre2[i - 1] + (s[i - 1] == 'd' ? pre1[i - 1] : 0);    
    }

    for (int i = n; i >= 1; i--) {
        suf1[i] += suf1[i + 1] + (s[i - 1] == 'u');
        suf2[i] += suf2[i + 1] + (s[i - 1] == 'd' ? suf1[i + 1] : 0);                
    }

    for (int i = 1; i <= n; i++) {
        if (s[i - 1] == 'd') {
            val[i - 1] = pre1[i - 1] * suf1[i + 1];
        } else if (s[i - 1] == 'u') {
            val[i - 1] = pre2[i - 1] + suf2[i + 1];
        }
    }
    
    int pos = 0;
    i64 mx = 0;
    for (int i = 0; i < n; i++) {
        if (val[i] > mx) {
            mx = val[i];
            pos = i;
        }
    }
    s[pos] = 'z';
    std::cout << s << '\n';
    
    return 0;
}

E

贪心，大于 $k + 1$ 的跟 $1$ 连起来，再找小于等于 $n$ 的最大质数 $p$ ， $p - i > k$ 的和 $p$ 连起来，剩下的点遍历一下可以和它取到 $\gcd$ 的点，取 $\min$ 。

C++ Code

#include <bits/stdc++.h>

using i64 = long long;

bool is_prime(int x) {
    if (x < 2) {
        return false;
    }

    for (int i = 2; i <= std::sqrt(x); i++) {
        if (x % i == 0) {
            return false;
        }
    }
    return true;
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int n, k;
    std::cin >> n >> k;

    std::vector<int> w(n + 1);
    std::iota(w.begin(), w.end(), 0);

    for (int i = k + 2; i <= n; i++) {
        w[i] = 1;
    }

    int p = -1;
    for (int i = n; i >= 2; i--) {
        if (is_prime(i)) {
            p = i;
            break;
        }
    }

    for (int i = 2; i <= std::min(k + 1, n); i++) {
        if (p - i <= k) {
            for (int j = i + k + 1; j <= n; j++) {
                w[i] = std::min(w[i], std::gcd(i, j));
                if (w[i] == 1) {
                    break;
                }
            }
        } else {
            w[i] = 1;
        }
    }

    i64 ans = 0;
    for (int i = 2; i <= n; i++) {
        ans += w[i];
    }
    std::cout << ans << '\n';
    
    return 0;
}

F

小于等于 $2\cdot 10^{5}$ 的数最多变化 $4$ 次就会变成 $1$ 。

C++ Code

#include <bits/stdc++.h>

using i64 = long long;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int n, m;
    std::cin >> n >> m;

    std::priority_queue<int> q;
    std::vector<int> ans(4 * n);

    for (int i = 0; i < n; i++) {
        int x;
        std::cin >> x;
        
        q.push(x);
    }

    for (int i = 0; i < 4 * n; i++) {
        int x = q.top();
        q.pop();
        q.push(__builtin_popcount(x));
        ans[i] = q.top();
    }

    for (int i = 0; i < m; i++) {
        int x;
        std::cin >> x;
        x--;

        if (x >= 4 * n) {
            std::cout << 1 << '\n';
        } else {
            std::cout << ans[x] << '\n';
        }
    }

    return 0;
}

G

C++ Code

#include <bits/stdc++.h>

using i64 = long long;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int n, k;
    std::cin >> n >> k;

    std::vector<int> a, b;
    for (int i = 0; i < n; i++) {
        int x;
        std::cin >> x;

        if (x > 0) {
            a.push_back(x);
        } else {
            b.push_back(x);
        }
    }
    sort(a.begin(), a.end(), std::greater());
    sort(b.begin(), b.end());

    if ((int) a.size() % 2 == 1) {
        b.push_back(a.back());
        a.pop_back();
    }

    std::vector<int> p;
    for (int i = 0; i < (int) a.size(); i += 2) {
        p.push_back(a[i] * a[i + 1]);
    }
    for (int i = 0; i < (int) b.size(); i += 2) {
        p.push_back(b[i] * b[i + 1]);
    }
    sort(p.begin(), p.end(), std::greater());

    int ans = 0;
    for (int i = 0; i < std::min(k, (int) p.size()); i++) {
        ans += p[i];
    }
    std::cout << ans << '\n';
    
    return 0;
}

H

C++ Code

#include <bits/stdc++.h>

using i64 = long long;

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

    int x, l, r;
    std::cin >> x >> l >> r;

    std::cout << std::fixed << std::setprecision(12) << std::min(1., std::max(0, x - l) / (r - l + 1.)) << '\n';
    
    return 0;
}

I

除了第一步，走过的边就可以删除它。

C++ Code

#include <bits/stdc++.h>

using i64 = long long;

constexpr int inf = 1E9;
  
int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int n, m;
    std::cin >> n >> m;

    std::vector<std::vector<std::array<int, 2>>> adj(n);

    bool ok = 0;

    for (int i = 0; i < m; i++) {
        int u, v, w;
        std::cin >> u >> v >> w;
        
        u--, v--;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }
    
    std::queue<int> q;
    std::vector<int> dis(n, inf);
    std::vector<bool> vis(n);

    q.push(0);
    vis[0] = 1;
    dis[0] = 0;
    while (!q.empty()) {
        int cur = q.front();
        q.pop();
        for (auto [nex, w] : adj[cur]) {
            if (!vis[nex]) {
                q.push(nex);
                vis[nex] = 1;
                dis[nex] = dis[cur] + 1;
            }
        }
    }

    if (n == 1) {
        std::cout << 0 << '\n';
    } else {
        if (dis[n - 1] == m) {
            std::cout << adj[0][0][1] + dis[n - 1] - 1 << '\n';
        } else {
            std::cout << dis[n - 1] << '\n';
        }
    }
    
    return 0;
}

J

模拟。

C++ Code

#include <bits/stdc++.h>

using i64 = long long;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int n, t, r;
    std::cin >> n >> t >> r;

    std::map<std::string, int> mp;
    std::vector<std::array<int, 5>> events;
    
    int people = 0;
    for (int i = 0; i < n; i++) {
        int o, ti;
        std::string name;
        std::cin >> o >> ti >> name;

        if (!mp.count(name)) {
            mp[name] = people;
            people++;
        }

        if (o == 1) { 
            events.push_back({ti, 3, mp[name], 0, i});
            events.push_back({ti / t * t, 2, mp[name], 0, i});
            events.push_back({ti + r, 2, mp[name], 0, i});            
        } else {
            int w;
            std::cin >> w;
            events.push_back({ti, 1, mp[name], w, i});
        }
    }
    sort(events.begin(), events.end());

    std::vector<i64> pro, rank, ans(n, -1);
    pro.resize(people);
    rank.resize(people);

    for (auto &[ti, type, name, w, i] : events) {
        if (type == 1) {
            pro[name] += w;
        } else if (type == 2) {
            rank[name] = pro[name];
        } else {
            ans[i] = rank[name];
        }
    }

    for (int i = 0; i < n; i++) {
        if (ans[i] != -1) {
            std::cout << ans[i] << '\n';
        }
    }

    return 0;
}

L

容斥。

C++ Code

#include <bits/stdc++.h>

using i64 = long long;

constexpr int P = 1000000007;
using i64 = long long;
// assume -P <= x < 2P
int norm(int x) {
    if (x < 0) {
        x += P;
    }
    if (x >= P) {
        x -= P;
    }
    return x;
}
template<class T>
T power(T a, i64 b) {
    T res = 1;
    for (; b; b /= 2, a *= a) {
        if (b % 2) {
            res *= a;
        }
    }
    return res;
}
struct Z {
    int x;
    Z(int x = 0) : x(norm(x)) {}
    Z(i64 x) : x(norm(x % P)) {}
    int val() const {
        return x;
    }
    Z operator-() const {
        return Z(norm(P - x));
    }
    Z inv() const {
        assert(x != 0);
        return power(*this, P - 2);
    }
    Z &operator*=(const Z &rhs) {
        x = i64(x) * rhs.x % P;
        return *this;
    }
    Z &operator+=(const Z &rhs) {
        x = norm(x + rhs.x);
        return *this;
    }
    Z &operator-=(const Z &rhs) {
        x = norm(x - rhs.x);
        return *this;
    }
    Z &operator/=(const Z &rhs) {
        return *this *= rhs.inv();
    }
    friend Z operator*(const Z &lhs, const Z &rhs) {
        Z res = lhs;
        res *= rhs;
        return res;
    }
    friend Z operator+(const Z &lhs, const Z &rhs) {
        Z res = lhs;
        res += rhs;
        return res;
    }
    friend Z operator-(const Z &lhs, const Z &rhs) {
        Z res = lhs;
        res -= rhs;
        return res;
    }
    friend Z operator/(const Z &lhs, const Z &rhs) {
        Z res = lhs;
        res /= rhs;
        return res;
    }
    friend std::istream &operator>>(std::istream &is, Z &a) {
        i64 v;
        is >> v;
        a = Z(v);
        return is;
    }
    friend std::ostream &operator<<(std::ostream &os, const Z &a) {
        return os << a.val();
    }
};
struct Comb {
    int n;
    std::vector<Z> _fac;
    std::vector<Z> _invfac;
    std::vector<Z> _inv;
    
    Comb() : n{0}, _fac{1}, _invfac{1}, _inv{0} {}
    Comb(int n) : Comb() {
        init(n);
    }
    
    void init(int m) {
        if (m <= n) return;
        _fac.resize(m + 1);
        _invfac.resize(m + 1);
        _inv.resize(m + 1);
        
        for (int i = n + 1; i <= m; i++) {
            _fac[i] = _fac[i - 1] * i;
        }
        _invfac[m] = _fac[m].inv();
        for (int i = m; i > n; i--) {
            _invfac[i - 1] = _invfac[i] * i;
            _inv[i] = _invfac[i] * _fac[i - 1];
        }
        n = m;
    }
    
    Z fac(int m) {
        if (m > n) init(2 * m);
        return _fac[m];
    }
    Z invfac(int m) {
        if (m > n) init(2 * m);
        return _invfac[m];
    }
    Z inv(int m) {
        if (m > n) init(2 * m);
        return _inv[m];
    }
    Z binom(int n, int m) {
        if (n < m || m < 0) return 0;
        return fac(n) * invfac(m) * invfac(n - m);
    }
} comb;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int n, m;
    std::cin >> n >> m;
    
    std::vector<std::array<int, 2>> a(m);
    for (int i = 0; i < m; i++) {
        std::cin >> a[i][0] >> a[i][1];
    }
    sort(a.begin(), a.end());

    std::vector<Z> f(m);
    for (int i = 0; i < m; i++) {
        auto [xi, yi] = a[i];
        f[i] = comb.binom(xi + yi - 2, xi - 1);
    }

    Z ans = power(Z(2), n - 1);
    for (int i = 0; i < m; i++) {
        auto [xi, yi] = a[i];
        for (int j = 0; j < i; j++) {
            auto [xj, yj] = a[j];
            if (xj <= xi && yj <= yi) {
                f[i] -= f[j] * comb.binom(xi + yi - xj - yj, xi - xj);
            }
        }
        ans -= f[i] * power(Z(2), n - xi - yi + 1);
    }
    std::cout << ans << '\n';
    
    return 0;
}