题解 | #2023河南萌新联赛第（七）场：信息工程大学#

A

懒标记线段树，区间修改，区间查询。

$O(n\log n m\log n)$ 。

C++ Code

#include "bits/stdc++.h"

using namespace std;
using i64 = long long;

template<class Info, class Tag>
struct LazySegmentTree {
    int n;
    vector<Info> info;
    vector<Tag> tag;
    LazySegmentTree() : n(0) {}
    LazySegmentTree(int n_, Info v_ = Info()) {
        init(n_, v_);
    }
    template<class T>
    LazySegmentTree(vector<T> init_) {
        init(init_);
    }
    void init(int n_, Info v_ = Info()) {
        init(vector(n_, v_));
    }
    template<class T>
    void init(vector<T> init_) {
        n = init_.size();
        info.assign(4 << __lg(n), Info());
        tag.assign(4 << __lg(n), Tag());
        std::function<void(int, int, int)> build = [&](int p, int l, int r) {
            if (r - l == 1) {
                info[p] = init_[l];
                return;
            }
            int m = (l + r) / 2;
            build(2 * p, l, m);
            build(2 * p + 1, m, r);
            pull(p);
        };
        build(1, 0, n);
    }
    void pull(int p) {
        info[p] = info[2 * p] + info[2 * p + 1];
    }
    void apply(int p, const Tag &v) {
        info[p].apply(v);
        tag[p].apply(v);
    }
    void push(int p) {
        apply(2 * p, tag[p]);
        apply(2 * p + 1, tag[p]);
        tag[p] = Tag();
    }
    void modify(int p, int l, int r, int x, const Info &v) {
        if (r - l == 1) {
            info[p] = v;
            return;
        }
        int m = (l + r) / 2;
        push(p);
        if (x < m) {
            modify(2 * p, l, m, x, v);
        } else {
            modify(2 * p + 1, m, r, x, v);
        }
        pull(p);
    }
    void modify(int p, const Info &v) {
        modify(1, 0, n, p, v);
    }
    Info rangeQuery(int p, int l, int r, int x, int y) {
        if (l >= y || r <= x) {
            return Info();
        }
        if (l >= x && r <= y) {
            return info[p];
        }
        int m = (l + r) / 2;
        push(p);
        return rangeQuery(2 * p, l, m, x, y) + rangeQuery(2 * p + 1, m, r, x, y);
    }
    Info rangeQuery(int l, int r) {
        return rangeQuery(1, 0, n, l, r);
    }
    void rangeApply(int p, int l, int r, int x, int y, const Tag &v) {
        if (l >= y || r <= x) {
            return;
        }
        if (l >= x && r <= y) {
            apply(p, v);
            return;
        }
        int m = (l + r) / 2;
        push(p);
        rangeApply(2 * p, l, m, x, y, v);
        rangeApply(2 * p + 1, m, r, x, y, v);
        pull(p);
    }
    void rangeApply(int l, int r, const Tag &v) {
        return rangeApply(1, 0, n, l, r, v);
    }
    template<class F>
    int findFirst(int p, int l, int r, int x, int y, F pred) {
        if (l >= y || r <= x || !pred(info[p])) {
            return -1;
        }
        if (r - l == 1) {
            return l;
        }
        int m = (l + r) / 2;
        push(p);
        int res = findFirst(2 * p, l, m, x, y, pred);
        if (res == -1) {
            res = findFirst(2 * p + 1, m, r, x, y, pred);
        }
        return res;
    }
    template<class F>
    int findFirst(int l, int r, F pred) {
        return findFirst(1, 0, n, l, r, pred);
    }
    template<class F>
    int findLast(int p, int l, int r, int x, int y, F pred) {
        if (l >= y || r <= x || !pred(info[p])) {
            return -1;
        }
        if (r - l == 1) {
            return l;
        }
        int m = (l + r) / 2;
        push(p);
        int res = findLast(2 * p + 1, m, r, x, y, pred);
        if (res == -1) {
            res = findLast(2 * p, l, m, x, y, pred);
        }
        return res;
    }
    template<class F>
    int findLast(int l, int r, F pred) {
        return findLast(1, 0, n, l, r, pred);
    }
};
 
struct Tag {
    int x;
    Tag(int x = 0) : x(x) {};
    void apply(const Tag &t) {
        x ^= t.x;
    }
};

struct Info {
    int c0, c1, c;
    Info(int c0 = 0, int c1 = 0, int c = -1) : c0(c0), c1(c1), c(c) {
    }
    void apply(const Tag &t) {
        if (t.x) {
            swap(c0, c1);
            c ^= 1;
        }
    }
};

Info operator+(const Info &a, const Info &b) {
    return Info(a.c0 + b.c0, a.c1 + b.c1);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, m;
    string s;
    cin >> n >> m >> s;
    
    vector<Info> a(n);
    for (int i = 0; i < n; i++) {
        a[i].c = s[i] - '0'; 
        if (a[i].c == 0) {
            a[i].c0++;
        } else {
            a[i].c1++;
        }
    }
    
    LazySegmentTree<Info, Tag> seg(a);
    for (int i = 0; i < m; i++) {
        int o, l, r;
        cin >> o >> l >> r;
        l--;
        if (o == 0) {
            seg.rangeApply(l, r, 1);
        } else {
            cout << seg.rangeQuery(l, r).c1 << '\n';
        }
    }
    
    return 0;
}

B

原题题面错误。

题面重制

七夕节左近，楚楚想去见女朋友，可是他最近和女朋友吵架了，女朋友躲着他，不知道会出现在哪座城市里。楚楚心知肚明女朋友是在赌气，所以无论自己在哪座城市，女朋友在哪座城市，他一定要在七夕节见到她。城市之间用铁路或者城际公交中的一种相连通，虽然并不是任意两个城市都直接相连，但是保证可以通过这两种交通方式从任一城市出发到另一任意城市。由于楚楚的特殊身份，他可以免费乘坐城际公交，那么他最少需要买多少张火车票才能保证见到女朋友呢？

输入描述：

第一行三个整数 $n,k,m$ $(1\le n\le 10^{4},0\le k,m\le 10^{4})$ ，表示共 $n$ 个城市，编号从 $1$ 到 $n$ ， $k$ 条城际公交线， $m$ 条铁路。

接下来 $k$ 行，每行两个整数 $u,v$ ，表示城市 $u,v$ 之间可以通过城际公交相互到达。

再接下来 $m$ 行，每行两个整数 $u,v$ ，表示城市 $u,v$ 之间可以通过铁路相互到达。

实际是构造最小生成树，城际公交免费即直接连边。

$O(k\log n m\log n)$ 。

C++ Code

#include "bits/stdc++.h"

using namespace std;
using i64 = long long;

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

struct UnionFind {
    int n;
    vector<int> f, sz;
    UnionFind(const int &n = 0) : n(n), f(n), sz(n, 1) {
        iota(f.begin(), f.end(), 0);
    }
    int get(int x) {
        while (x != f[x]) {
            x = f[x] = f[f[x]];
        }
        return x;
    }
    bool unite(int x, int y) {
        x = get(x), y = get(y);
        if (x != y) {
            f[y] = x;
            sz[x] += sz[y];
            return 1;
        }
        return 0;
    }
    bool united(int x, int y) {
        return get(x) == get(y);
    }
    int size(int x) {
        x = get(x);
        return sz[x];
    }
};

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

    int n, k, m;
    cin >> n >> k >> m;

    UnionFind f(n);

    for (int i = 0; i < k; i++) {
        int u, v;
        cin >> u >> v;
        u--, v--;
        f.unite(u, v);
    }

    vector<array<int, 2>> e(m);
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        u--, v--;
        e[i] = {u, v};  
    }

    int ans = 0;
    for (int i = 0; i < m; i++) {
        auto &[u, v] = e[i];
        if (f.unite(u, v)) {
            ans++;
        }
    }
    cout << ans << '\n';

    return 0;
}

C

$\text{dp}$ 。

https://www.luogu.com.cn/problem/P1006

D

数据水。

懒标记线段树，区间修改，区间查询最小值。

$O(n\log n m\log n)$ 。

C++ Code

#include "bits/stdc++.h"

using namespace std;
using i64 = long long;

template <class Info, class Tag>
struct LazySegmentTree {
    int n;
    vector<Info> info;
    vector<Tag> tag;
    LazySegmentTree() : n(0) {}
    LazySegmentTree(int n_, Info v_ = Info()) {
        init(n_, v_);
    }
    template<class T>
    LazySegmentTree(vector<T> init_) {
        init(init_);
    }
    void init(int n_, Info v_ = Info()) {
        init(vector(n_, v_));
    }
    template<class T>
    void init(vector<T> init_) {
        n = init_.size();
        info.assign(4 << __lg(n), Info());
        tag.assign(4 << __lg(n), Tag());
        function<void(int, int, int)> build = [&](int p, int l, int r) {
            if (r - l == 1) {
                info[p] = init_[l];
                return;
            }
            int m = (l + r) / 2;
            build(2 * p, l, m);
            build(2 * p + 1, m, r);
            pull(p);
        };
        build(1, 0, n);
    }
    void pull(int p) {
        info[p] = info[2 * p] + info[2 * p + 1];
    }
    void apply(int p, const Tag &v) {
        info[p].apply(v);
        tag[p].apply(v);
    }
    void push(int p) {
        apply(2 * p, tag[p]);
        apply(2 * p + 1, tag[p]);
        tag[p] = Tag();
    }
    void modify(int p, int l, int r, int x, const Info &v) {
        if (r - l == 1) {
            info[p] = v;
            return;
        }
        int m = (l + r) / 2;
        push(p);
        if (x < m) {
            modify(2 * p, l, m, x, v);
        } else {
            modify(2 * p + 1, m, r, x, v);
        }
        pull(p);
    }
    void modify(int p, const Info &v) {
        modify(1, 0, n, p, v);
    }
    Info rangeQuery(int p, int l, int r, int x, int y) {
        if (l >= y || r <= x) {
            return Info();
        }
        if (l >= x && r <= y) {
            return info[p];
        }
        int m = (l + r) / 2;
        push(p);
        return rangeQuery(2 * p, l, m, x, y) + rangeQuery(2 * p + 1, m, r, x, y);
    }
    Info rangeQuery(int l, int r) {
        return rangeQuery(1, 0, n, l, r);
    }
    void rangeApply(int p, int l, int r, int x, int y, const Tag &v) {
        if (l >= y || r <= x) {
            return;
        }
        if (l >= x && r <= y) {
            apply(p, v);
            return;
        }
        int m = (l + r) / 2;
        push(p);
        rangeApply(2 * p, l, m, x, y, v);
        rangeApply(2 * p + 1, m, r, x, y, v);
        pull(p);
    }
    void rangeApply(int l, int r, const Tag &v) {
        return rangeApply(1, 0, n, l, r, v);
    }
    template<class F>
    int findFirst(int p, int l, int r, int x, int y, F pred) {
        if (l >= y || r <= x || !pred(info[p])) {
            return -1;
        }
        if (r - l == 1) {
            return l;
        }
        int m = (l + r) / 2;
        push(p);
        int res = findFirst(2 * p, l, m, x, y, pred);
        if (res == -1) {
            res = findFirst(2 * p + 1, m, r, x, y, pred);
        }
        return res;
    }
    template <class F>
    int findFirst(int l, int r, F pred) {
        return findFirst(1, 0, n, l, r, pred);
    }
    template <class F>
    int findLast(int p, int l, int r, int x, int y, F pred) {
        if (l >= y || r <= x || !pred(info[p])) {
            return -1;
        }
        if (r - l == 1) {
            return l;
        }
        int m = (l + r) / 2;
        push(p);
        int res = findLast(2 * p + 1, m, r, x, y, pred);
        if (res == -1) {
            res = findLast(2 * p, l, m, x, y, pred);
        }
        return res;
    }
    template<class F>
    int findLast(int l, int r, F pred) {
        return findLast(1, 0, n, l, r, pred);
    }
};
 
struct Tag {
    int x;
    Tag(const int &x = 0) : x(x) {};
    void apply(const Tag &t) {
        x += t.x;
    }
};
 
struct Min {
    int x;
    Min(const int &x = 1E9) : x(x) {}
    void apply(const Tag &t) {
        x += t.x;
    }
};
 
Min operator+(const Min &a, const Min &b) {
    return min(a.x, b.x);
}

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];
    }

    LazySegmentTree<Min, Tag> seg(a);
    for (int i = 0; i < m; i++) {
        int d, s, t;
        cin >> d >> s >> t;
        s--;

        if (seg.rangeQuery(s, t).x < d) {
            cout << "-1\n" << i + 1 << '\n';
            return 0;
        }

        seg.rangeApply(s, t, -d);
    }
    cout << "0\n";

    return 0;
}

E

原题数据错误。

无向有环图最长路。

$1\le n,m\le 5$ 可以 $\text{dfs}$ 。

F

队友写的 $\text{sa}$ 。

G

模拟。

复杂度不会算。

C++ Code

#include "bits/stdc++.h"

using namespace std;
using i64 = long long;

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

struct P {
    pair<int, int> p;
    P() {}
    P(const string &s) {
        string x, y;
        for (auto &si : s) {
            if (si >= 'a' && si <= 'z') {
                x += si;
            } else {
                y += si;
            }
        }
        if (x == "heitao") {
            p.second = 4;
        } else if (x == "hongtao") {
            p.second = 3;
        } else if (x == "meihua") {
            p.second = 2;
        } else if (x == "fangkuai") {
            p.second = 1;
        }
        if (y == "A") {
            p.first = 1;
        } else if (y == "J") {
            p.first = 11;
        } else if (y == "Q") {
            p.first = 12;
        } else if (y == "K") {
            p.first = 13;
        } else {
            p.first = stoi(y);
        }
    }
    bool operator<(const P &t) const {
        return p < t.p;
    }
};

struct F {
    pair<int, vector<P>> p;
    F() {}
    F(const vector<P> &v) {
        p.second = v;
        int sum = 0;
        for (int i = 0; i < 5; i++) {
            sum += min(10, v[i].p.first);
        }
        p.first = -1;
        for (int i = 0; i < 5; i++) {
            for (int j = i + 1; j < 5; j++) {
                for (int k = j + 1; k < 5; k++) {
                    int x = min(10, v[i].p.first);
                    int y = min(10, v[j].p.first);
                    int z = min(10, v[k].p.first);
                    if ((x + y + z) % 10 == 0) {
                        int w = (sum - x - y - z) % 10;
                        w += (w == 0 ? 10 : 0);
                        p.first = max(p.first, w);
                    }
                }
            }
        }
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n;
    vector<vector<P>> a(n, vector<P>(5));
    vector<F> b(n);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < 5; j++) {
            string s;
            cin >> s;
            a[i][j] = P(s);
        }
        sort(range(a[i]), [&](P &a, P &b) {
            return a.p > b.p;
        });
        b[i] = F(a[i]);
    }
    
    vector<int> p(n);
    iota(range(p), 0);
    sort(range(p), [&](int &i, int &j) {
        return b[i].p > b[j].p;
    });

    cout << p[0] << '\n';

    return 0;
}

H

可以使用双向队列。

https://www.luogu.com.cn/problem/P1016

I

https://www.luogu.com.cn/problem/P1069

J

$\text{bfs}$ ，答案即为从 $0$ 出发到其他点的最长路。

$O(n)$ 。

C++ Code

#include "bits/stdc++.h"

using namespace std;
using i64 = long long;

template <class T>
T max(const vector<T> &a) {
    return *max_element(a.begin(), a.end());
}

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

    int n, k;
    cin >> n >> k;

    vector<vector<int>> g(n);
    for (int i = 0; i < n; i++) {
        g[i].push_back((i + 1) % n);
        g[i].push_back((i + k) % n);
    }

    queue<int> q;
    vector<int> dis(n, -1);
    q.push(0);
    dis[0] = 0;
    while (!q.empty()) {
        auto cur = q.front();
        q.pop();
        for (auto &nex : g[cur]) {
            if (dis[nex] == -1) {
                q.push(nex);
                dis[nex] = dis[cur] + 1;
            }
        }
    }
    cout << max(dis) << '\n';

    return 0;
}

K

$\text{ST}$ 表。

$O(n\log n)$ 。

C++ Code

#include "bits/stdc++.h"

using namespace std;
using i64 = long long;

template <class T>
struct SparseTable {
    int n;
    vector<vector<T>> a;
    SparseTable(const vector<T> &init) : n(init.size()) {
        int lg = __lg(n);
        a.assign(lg + 1, vector<T>(n));
        a[0] = init;
        for (int i = 1; i <= lg; i++) {
            for (int j = 0; j <= n - (1 << i); j++) {
                a[i][j] = min(a[i - 1][j], a[i - 1][(1 << (i - 1)) + j]);
            }
        }  	    
    }
    T get(int l, int r) {// [l, r)
        int lg = __lg(r - l);
        return min(a[lg][l], a[lg][r - (1 << lg)]);
    }
};

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];
    }

    SparseTable<int> mn(a);
    for (int i = 0; i + m <= n; i++) {
        cout << mn.get(i, i + m) << '\n';
    }

    return 0;
}

L

https://www.luogu.com.cn/problem/P1613