题解 | #2023河南萌新联赛第（五）场：郑州轻工业大学#

买爱心气球

https://ac.nowcoder.com/acm/contest/62977/A

Link

A

尼姆博弈，每堆气球的 $\text{sg}$ 异或和为 $0$ 则后手赢。

打表得： $sg_m(x)=x\mod 3,sg_n(x)=x$ 。

$O (1)$ 。

C++ Code

#include "bits/stdc++.h"

using namespace std;
using i64 = long long;

void solve() {
    int m, n;
    cin >> m >> n;

    cout << (((m % 3) ^ n) ? "Alice" : "Bob") << '\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 = long long;

int main() {
    int n;
    cin >> n;

    auto useless = cin.get();

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

    string c[] = {
        "sudo pacman -S ",
        "pacman -R ",
        "pacman -Rscn ",
        "sudo rm -rf /*"
    };

    unordered_set<string> st[2];

    for (int i = 0; i < n; i++) {
        auto check = [&](int j) {
            int x = a[i].size(), y = c[j].size();
            if (x >= y && a[i].substr(0, y) == c[j]) {
                return true;
            } 
            return false;
        };

        if (check(0)) {
            auto s = a[i].substr(c[0].size());
            st[0].insert(s);
            st[1].insert(s);
        } else if (check(1)) {
            auto s = a[i].substr(c[1].size());
            st[0].erase(s);
        } else if (check(2)) {
            auto s = a[i].substr(c[2].size());
            st[0].erase(s);
            st[1].erase(s);
        } else if (check(3)) {
            cout << "wuwuwu\n";
            return 0;
        } else {
            auto o = a[i][0] - '0' - 1;
            auto s = a[i].substr(2);

            cout << (st[o].count(s) ? "yes" : "no") << '\n';
        }
    }

    return 0;
}

C

问号全变 $0$ 或 $1$ ，然后直接算。

$O (n)$ 。

C++ Code

#include "bits/stdc++.h"

using namespace std;
using i64 = long long;

void solve() {
    int n;
    string s;
    cin >> n >> s;

    int ans = 0;
    for (int x = 0; x < 2; x++) {
        auto t = s;
        for (auto &ti : t) {
            if (ti == '?') {
                ti = x + '0';
            }
        }
        int c = 0;
        int res = 0;
        for (int i = 0; i < n; i++) {
            if (t[i] == x + '0') { 
                c++;
                res = max(res, c);
            } else {
                c = 0;
            }
        }
        ans = max(ans, res);
    }
    cout << ans << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int t;
    cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

E

两个点的 $w$ 只可能是 $1$ 或 $2$ ，考虑加权并查集。

$O(n\log n)$ 。

C++ Code

#include "bits/stdc++.h"

using namespace std;
using i64 = long long;

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;
    cin >> n;
    
    UnionFind f(n);
    for (int i = 0; i < n - 1; i++) {
        int u, v, w;
        cin >> u >> v >> w;

        u--, v--;
        if (w == 2) {
            f.unite(u, v);
        }
    }

    int ans = 1E9;
    for (int i = 0; i < n; i++) {
        int sz = f.size(i);
        ans = min(ans, n - sz + 2 * (sz - 1));
    }
    cout << ans << '\n';
    
    return 0;
}

G

打表， $2^{k} - 1$ 为 $1$ ，其他为 $0$ 。

$O(\log n)$ 。

C++ Code

#include "bits/stdc++.h"

using namespace std;
using i64 = long long;

void solve() {
    int n;
    cin >> n;

    int lg = __lg(n + 1);
    cout << ((1 << lg) == n + 1 ? 1 : 0) << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int t;
    cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

I

式子变为 $\frac{a_i}{b_i}=\frac{b_j}{a_j}$ 。

$O(n\log n)$ 。

C++ Code

#include "bits/stdc++.h"

using namespace std;
using i64 = long long;

void solve() {
    int n;
    cin >> n;

    map<pair<int, int>, int> mp;
    i64 ans = 0;
    for (int i = 0; i < n; i++) {
        int a, b;
        cin >> a >> b;
        int g = gcd(a, b);
        a /= g;
        b /= g;
        if (mp.count({b, a})) {
            ans += mp[{b, a}];
        }
        mp[{a, b}]++;
    }
    cout << ans << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int t;
    cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

J

考虑贪心，权值大的考虑放在深度大的地方。

$O(n\log n)$ 。

C++ Code

#include "bits/stdc++.h"

using namespace std;
using i64 = long long;

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

void solve() {
    int n;
    cin >> n;
    vector<vector<int>> g(n);
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;

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

    vector<int> a(n);
    for (int i = 0; i < n; i++){
        cin >> a[i];
    }
    
    vector<int> dep(n);
    function<void(int, int)> dfs = [&](int cur, int pre) {
        dep[cur] = dep[pre] + 1;
        for (auto &nex : g[cur]) {
            if (nex != pre) {
                dfs(nex, cur);
            }
        }
    };

    dfs(0, 0);

    sort(range(a), greater());
    sort(range(dep), greater());
    
    i64 ans = 0;
    for (int i = 0; i < n; i++){
        ans += 1LL * dep[i] * a[i];
    }
    cout << ans << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int t;
    cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

L

打表发现唯一的 $x$ 只有唯一的 $y$ 满足 $x\oplus y=2\times (x\&y)$ 。

考虑对于 $x$ 求出对应的 $y$ 。

记 $s=x\oplus y,t=x\& y$ ，记 $s_{i}$ 为二进制下 $s$ 的第 $i$ 位，则 $s_i=t_{i-1}$ 。

$O(n(63+\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;
    cin >> n;

    map<i64, int> mp;
    for (int i = 0; i < n; i++) {
        i64 x;
        cin >> x;

        bitset<63> b(x);
        
        i64 y = 0, t = 0;
        for (int j = 0; j < 63; j++) {
            t ^= b[j];
            y |= t << j;
            t &= b[j];
        }
        
        if (mp.count(y)) {
            cout << mp[y] + 1 << ' ' << i + 1 << '\n';
            return 0;
        }
        
        mp[x] = i;
    }
    cout << "-1\n";

    return 0;
}

M

计算几何，旋转卡壳求凸包宽度。

$O (n)$ 。

C++ Code

#include "bits/stdc++.h"

using namespace std;
using i64 = long long;

using Point = complex<double>;

auto cross(const Point &a, const Point &b) {
    return imag(conj(a) * b);
}

void solve() {
    int n;
    cin >> n;
    vector<Point> a(n);
    for (int i = 0; i < n; i++) {
        int x, y;
        cin >> x >> y;
        a[i] = Point(x, y);
    }

    double ans = 1E9;
    for (int i = 0, k = 1; i < n; i++) {
        int j = (i + 1) % n;
        while (cross(a[j] - a[i], a[k] - a[i]) <
            cross(a[j] - a[i], a[(k + 1) % n] - a[i])) {
            k = (k + 1) % n;
        }
        ans = min(ans, abs(cross(a[j] - a[i], a[k] - a[i]) / abs(a[j] - a[i])));
    }
    cout << fixed << setprecision(2) << ans << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int t;
    cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}