题解 | #2023河南萌新联赛第（一）场：河南农业大学#

A

打表发现答案为 $(^{k+2}_{3})$ ， $O (1)$ 。

C++ Code

#include "bits/stdc++.h"

using namespace std;
using i64 = long long;
using i128 = __int128;

constexpr int P = 1000000007;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    i64 k;
    cin >> k;
    i64 ans = i128(k + 2) * (k + 1) * k / 6 % P;
    cout << ans << '\n';
    
    return 0;
}

令 $f(n)=\sum\limits_{i=1}^{n}\varphi(i)\cdot \lfloor\frac{n}{i}\rfloor,g(n)=\sum\limits_{i=1}^{n}f(i)$ 。

\begin{aligned} f(n)=&\sum\limits_{i=1}^{n}\varphi(i)\cdot\lfloor\frac{n}{i}\rfloor\\=&\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{\lfloor\frac{n}{i}\rfloor}\varphi(i)\\=&\sum\limits_{i=1}^{n}\sum\limits_{d|i}\varphi(d)\\=&\sum\limits_{i=1}^{n}i\\=&\frac{n\cdot(n+1)}{2} \end{aligned}

\begin{aligned} g(n)=&\sum\limits_{i=1}^{n}f(i)\\=&\sum\limits_{i=1}^{n}\frac{i\cdot(i+1)}{2}\\=&\frac{\sum\limits_{i=1}^{n}i^{2}+\sum\limits_{i=1}^{n}i}{2}\\=&\frac{\frac{n\cdot(n+1)\cdot(2n+1)}{6}+\frac{n\cdot(n+1)}{2}}{2}\\=&\frac{n\cdot(n+1)\cdot(n+2)}{6} \end{aligned}

C

若操作一次就能获胜则先手胜，若无论第一次怎么操作，第二次操作都能获胜则后手胜，否则平局。

D

二分路径上最大值，跑 $\text{dijkstra}$ 。

C++ Code

#include "bits/stdc++.h"

using namespace std;
using i64 = long long;

constexpr i64 inf = 1E18;

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

    st--, ed--;

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

    vector<vector<pair<int, int>>> g(n);
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;

        u--, v--;
        g[u].push_back({v, w});
        g[v].push_back({u, w});
    }

    vector<int> vis(n);
    vector<i64> dis(n);

    auto check = [&](int x) {
        if (a[st] > x) {
            return false;
        }
        vis.assign(n, 0);
        dis.assign(n, inf);
        priority_queue<pair<i64, int>, vector<pair<i64, int>>, greater<>> q;    
        dis[st] = 0;
        q.push({dis[st], st});
        while (!q.empty()) {
            auto [d, v] = q.top();
            q.pop();
            if (v == ed) {
                break;
            }
            if (!vis[v]) {
                vis[v] = 1;
                for (auto &[nex, w] : g[v]) {
                    if (a[nex] > x) {
                        continue;
                    }
                    if (dis[nex] > dis[v] + w) {
                        dis[nex] = dis[v] + w;
                        q.push({dis[nex], nex});
                    }
                }
            }
        }
        return dis[ed] <= h;
    };
    int ans = -1;
    int l = 0, r = 1E7;
    while (l <= r) {
        int m = (l + r) >> 1;
        if (check(m)) {
            r = m - 1;
            ans = m;
        } else {
            l = m + 1;
        }
    }
    cout << ans << '\n';

    return 0;
}

E

维护连续段， $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, m;
    cin >> n >> m;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    i64 sum = 0;
    queue<int> q;
    int ans = 0;
    for (int i = 0; i < n; i++) {
        q.push(a[i]);
        sum += a[i];
        while (sum > m && !q.empty()) {
            auto cur = q.front();
            sum -= cur;
            q.pop();
        }
        if (sum == m) {
            ans++;
        }
    }
    cout << ans << '\n';
    return 0;
}

F

任意换两数变为升序， $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);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        a[i]--;
    }

    auto b = a;
    sort(b.begin(), b.end());
    vector<int> nex(n);
    for (int i = 0; i < n; i++) {
        nex[b[i]] = i;
    }
    int ans = n;
    vector<int> vis(n);
    for (int i = 0; i < n; i++) {
        if (!vis[i]) {
            for (int j = i; !vis[j]; j = nex[a[j]]) {
                vis[j] = 1;
            }
            ans--;
        }
    }
    cout << ans << '\n';
    
    return 0;
}

G

选两段最长的 $1$ 长度加起来， $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;
    string s;
    cin >> s;
    int cnt = 0;
    vector<int> a;
    for (int i = 0; i < n; i++) {
        if (s[i] == '0') {
            a.push_back(cnt);
            cnt = 0;
        } else {
            cnt++;
        }
    }
    a.push_back(cnt);
    int ans = 0;
    sort(a.begin(), a.end(), greater());
    for (int i = 0; i < 2 && i < (int) a.size(); i++) {
        ans += a[i];
    }
    cout << ans << '\n';
    return 0;
}

H

没想到什么短的写法， $\text{bfs}$ 。

C++ Code

#include "bits/stdc++.h"

using namespace std;
using i64 = long long;

constexpr int inf = 1E9;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, m;
    cin >> n >> m;
    vector<string> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    int k;
    cin >> k;
    vector<vector<i64>> b(n, vector<i64>(m));
    for (int i = 0; i < k; i++) {
        i64 x, y, z;
        cin >> x >> y >> z;

        x--, y--;
        b[x][y] = z;
    }
    int dx[] = {-1, +1, +0, +0};
    int dy[] = {+0, +0, -1, +1};
    
    auto get = [&](int i, int j) {
        return i * m + j;
    };
    const int N = n * m;

    vector<int> vis(N);
    vector<int> dis(N, inf);
    priority_queue<array<int, 3>, vector<array<int, 3>>, greater<>> q;    
    dis[0] = 0;
    q.push({dis[0], 0, 0});
    while (!q.empty()) {
        auto [d, x, y] = q.top();
        q.pop();
        int cur = get(x, y);
        if (cur == N - 1) {
            cout << dis[cur] << '\n';
            return 0;
        }
        if (!vis[cur]) {
            vis[cur] = 1;
            if (a[x][y] == '*') {
                for (int i = 0; i < 4; i++) {
                    int nx = x + dx[i] * b[x][y];
                    int ny = y + dy[i] * b[x][y];
                    if (nx < 0 || nx >= n || ny < 0 || ny >= m) {
                        continue;
                    }
                    int nex = get(nx, ny);
                    if (dis[nex] > dis[cur]) {
                        dis[nex] = dis[cur];
                        q.push({dis[nex], nx,ny});
                    }
                } 
            }
            if (a[x][y] == '.') {
                for (int i = 0; i < 4; i++) {
                    int nx = x + dx[i];
                    int ny = y + dy[i];
                    if (nx < 0 || nx >= n || ny < 0 || ny >= m) {
                        continue;
                    }
                    int nex = get(nx, ny);
                    if (dis[nex] > dis[cur] + 1) {
                        dis[nex] = dis[cur] + 1;
                        q.push({dis[nex], nx,ny});
                    }
                } 
            }
        }
    }
    cout << -1 << '\n';

    return 0;
}

I

$\text{lca}$ ，树上差分前缀和， $O(n\log n+m\log n+q\log 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, m, q;
    cin >> n >> m >> q;

    vector<vector<pair<int, int>>> g(n + 1);
    for (int i = 1; i < n; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        g[u].push_back({v, w});
        g[v].push_back({u, w});
    } 
    
    const int lg = __lg(n + 1);

    vector<int> dep(n + 1);
    vector<vector<int>> p(lg + 1, vector<int>(n + 1));
    function<void(int, int)> dfs = [&](int cur, int pre) {
        p[0][cur] = pre;
        dep[cur] = dep[pre] + 1;
        for (int i = 1; i <= lg; i++) {
            p[i][cur] = p[i - 1][p[i - 1][cur]];
        }
        for (auto &x : g[cur]) {
            int nex = x.first;
            int w = x.second;
            if (nex != pre) {
                dfs(nex, cur);
            }
        }
    };

    dfs(1, 0);

    auto lca = [&](int x, int y) {
        if (dep[x] < dep[y]) {
            swap(x, y);
        }
        for (int i = lg; i >= 0; i--) {
            if((dep[x] - dep[y]) >> i & 1) {
                x = p[i][x];
            }
        }
        if (x == y) {
            return x;
        }
        for (int i = lg; i >= 0; i--) {
            if(p[i][x] != p[i][y]) {
                x = p[i][x];
                y = p[i][y];
            }
        }        
        return p[0][x];
    };
    
    vector<i64> sum(n + 1);
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;

        int m = lca(u, v);
        sum[u] += w;
        sum[v] += w;
        sum[m] -= 2 * w;
    }
    function<void(int, int)> dfs1 = [&](int cur, int pre) {
        for (auto &[nex, w] : g[cur]) {
            if (nex != pre) {
                dfs1(nex, cur);
                sum[cur] += sum[nex];
            }
        }
    };
    function<void(int, int)> dfs2 = [&](int cur, int pre) {
        for (auto &[nex, w] : g[cur]) {
            if (nex != pre) {
                sum[nex] += sum[cur] + w;
                dfs2(nex, cur);
            }
        }
    };
    dfs1(1, 0);
    dfs2(1, 0);
    
    for (int i = 0; i < q; i++) {
        int u, v;
        cin >> u >> v;
        int m = lca(u, v);
        cout << sum[u] + sum[v] - 2 * sum[m] << '\n';
    }
    return 0;
}

J

和减最大的、和减最小的， $O (n)$ 。

C++ Code

#include "bits/stdc++.h"

using namespace std;
using i64 = long long;

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    i64 sum = accumulate(range(a), 0LL);
    int mx = *max_element(range(a));
    int mn = *min_element(range(a));

    cout << fixed << setprecision(6) << 1.0 * (sum - mx) / (n - 1) << ' ' 
    << 1.0 * (sum - mn) / (n - 1) << '\n';
 
    return 0;
}

K

$O (4 n)$ 。

C++ Code

#include "bits/stdc++.h"

using namespace std;
using i64 = long long;

constexpr int inf = 1E9;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, m;
    cin >> n >> m;
    vector<string> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    bool ok = 0;
    int ans = 0;
    int dx[] = {-1, +1, +0, +0};
    int dy[] = {+0, +0, -1, +1};
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (a[i][j] == '0') {
                int cnt = 0;
                for (int k = 0; k < 4; k++) {
                    int x = dx[k] + i;
                    int y = dy[k] + j;
                    if (x < 0 || x >= n || y < 0 || y >= m) {
                        continue;
                    }
                    cnt += (a[x][y] == '1');
                    if (a[x][y] == '2') {
                        cnt += inf;
                    }
                }          
                if (cnt == 3) {
                    ok = 1;
                    ans++;
                }      
            }
        }
    }
    if (!ok) {
        cout << "NO\n";
    } else {
        cout << "YES\n";
        cout << ans << '\n';
    }
    return 0;
}

L

感觉使用 $\text{multiset}$ 实现的可修对顶堆跑的非常慢，更快的解法应该是二分线段树或者二分树状数组。

赛时：

Code

树状数组， $O(n\log n)$ ：

C++ Code

#include "bits/stdc++.h"

using namespace std;
using i64 = long long;

template <class T>
struct Fenwick {
    int n;
    vector<T> a;
    Fenwick(const int n = 0) : n(n), a(n, T()) {}
    void modify(int i, T x) {
        for (i += 1; 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;
    }
    T sum(int l, int r) { // [l, r)
        return get(r) - get(l);
    }
    int kth(T k) {
        int x = 0;
        for (int i = 1 << __lg(n); i; i >>= 1) {
            if (x + i <= n && k >= a[x + i - 1]) {
                x += i;
                k -= a[x - 1];
            }
        }
        return x;
    }
};

constexpr int N = 1E6;

Fenwick<int> f(N + 1);

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, m;
    cin >> n >> m;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        f.modify(a[i], 1);
    }

    const int k = n / 2;

    for (int i = 0; i < m; i++) {
        int x, y;
        cin >> x >> y;

        x--;
        f.modify(a[x], -1);
        f.modify(y, 1);   
        a[x] = y;
        cout << f.kth(k) << '\n';
    }
    return 0;
}