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

B

考虑子集枚举， $O(2^n\log 2^{64})$ 。

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, k;
    cin >> n >> k;

    vector<i64> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    
    int ans = 0;
    function<void(int, i64)> dfs = [&](int i, i64 sum) {
        if (i == n) {
            if (sum != -1 && __builtin_popcount(sum) == k) {
                ans++;
            }
            return;
        }
        dfs(i + 1, sum & a[i]);
        dfs(i + 1, sum);
    };
    dfs(0, -1);
    cout << ans << '\n';

    return 0;
}

C

本题弱化版：https://atcoder.jp/contests/arc153/tasks/arc153_b。

D

实际上是 $2^{2\times 2\times 2\times \dots}$ ，直接算， $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, p;
    cin >> n >> p;

    i64 ans = 2;
    for (int i = 0; i < n; i++) {
        ans = ans * ans % p;
    }
    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;
    i64 s;
    cin >> n >> s;
    vector<i64> a(n);
    for (int i = 0; i < n; i++) {
        a[i] = s / n;
        if (i >= n - s % n) {
            a[i]++;
        }
    }
    for (int i = 0; i < n; i++) {
        cout << a[i] << " \n"[i == n - 1];
    }

    return 0;
}

F

考虑离线并查集，算出每两滴墨隔多久就会连接到一起， $O(n^{2}\log n^{2}+m\log m)$ 。

双倍经验：https://codeforces.com/contest/1851/problem/G。

C++ Code

#include "bits/stdc++.h"

using namespace std;
using i64 = long long;

using Point = complex<double>;

struct UnionFind {
    int n;
    vector<int> f;
    UnionFind(const int &n = 0) : n(n), f(n) { 
        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;
           return 1;
        }
        return 0;
    }
    bool united(int x, int y) {
        return get(x) == get(y);
    }
};

constexpr int inf = 1E9;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n;
    vector<Point> p(n);
    vector<int> v(n);
    for (int i = 0; i < n; i++) {
        int x, y;
        cin >> x >> y;
        p[i] = Point(x, y);
        cin >> v[i];
    }

    vector<array<int, 3>> e;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (v[i] + v[j] == 0) {
                e.push_back({inf, i, j});
            } else {
                e.push_back({int(ceil(abs(p[i] - p[j]) / (v[i] + v[j]))), i, j});
            }
        }
    }
    sort(e.begin(), e.end());

    int m;
    cin >> m;
    vector<array<int, 2>> qry(m);
    for (int i = 0; i < m; i++) {
        int t;
        cin >> t;
        qry[i] = {t, i};
    }
    sort(qry.begin(), qry.end());

    vector<int> ans(m);
    UnionFind f(n);
    int cnt = n;
    int N = e.size();
    int j = 0;
    for (auto &[t, i] : qry) {
        while (j < N && e[j][0] <= t) {
            if (f.unite(e[j][1], e[j][2])) {
                cnt--;
            }
            j++;
        }
        ans[i] = cnt;
    }
    
    for (int i = 0; i < m; i++) {
        cout << ans[i] << '\n';
    }

    return 0;

}

G

注意到题目中说保证 $a$ 中元素至少有 $n - 1$ 个数字互不相同。

那么若 $a$ 中有 $n$ 个不同数字，答案为 $(_{k}^{n}) (^{n}_{k})$ 。

若有 $n - 1$ 个不同数字，说明有两个数字出现两次，就 $(_{k}^{n}) (^{n}_{k})$ 减去重复的。

不考虑预处理， $O (n)$ 。

C++ Code

#include "bits/stdc++.h"

using namespace std;
using i64 = long long;

constexpr int P = 1000000007;
vector<i64> fac, ifac;

i64 power(i64 a, i64 b, int p = P) {
    i64 res = 1;
    for (; b; b >>= 1, a = a * a % p) {
        if (b & 1) {
            res = res * a % p;
        }
    }
    return res;
}
 
i64 inv(i64 x) {
    return power(x, P - 2);
}

void init(int N) {
    fac.assign(N + 1, 0);
    ifac.assign(N + 1, 0);
    fac[0] = 1;
    for (int i = 1; i <= N; i++) {
        fac[i] = fac[i - 1] * i % P;
    }
    ifac[N] = inv(fac[N]);
    for (int i = N - 1; i >= 0; i--) {
        ifac[i] = ifac[i + 1] * (i + 1) % P;
    }
}

i64 C(int n, int m) {
    if (m < 0 || m > n) {
        return 0;
    }
    return fac[n] * ifac[m] % P * ifac[n - m] % P;
}

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

    unordered_map<int, int> s;
    for (int i = 0; i < n; i++) {
       s[a[i]]++;
    }

    if (s.size() == n) {
        cout << C(n, k) << '\n';
    } else {
        int l = -1, r = -1;
        for (int i = 0; i < n; i++) {
            if (s[a[i]] == 2) {
                if (l == -1) {
                    l = i;
                } else if (r == -1) {
                    r = i;
                }
            }
        }
        cout << (C(n, k) - C(n - (r - l + 1), k - 1) + P) % P << '\n';
    }
}

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

    init(1E5);

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

    return 0;
}

H

$m$ 取 $2$ ，每次两个人战斗，显然大于等于某个值的人都有可能获胜，只要让他参与最后一次战斗，二分找到这个值。

$O(n\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;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    vector<array<int, 2>> b(n);
    for (int i = 0; i < n; i++) {
        b[i] = {a[i], i};
    }
    sort(b.begin(), b.end());

    int ans = 0;
    int l = 0, r = n - 1;
    while (l <= r) {
        int m = (l + r) >> 1;

        int sum = b[n - 1][0];
        for (int i = n - 2; i >= 0; i--) {
            if (i != m) {
                sum = (sum + b[i][0]) / 2;
            }       
        }

        if (sum <= b[m][0]) {
            r = m - 1;
            ans = m;
        } else {
            l = m + 1;
        }
    } 

    string s(n, '0');
    for (int i = ans; i < n; i++) {
        s[b[i][1]] = '1';
    }
    cout << s << '\n';

    return 0;
}

I

根据右端点排序后贪心， $O(n\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;
    vector<pair<int, int>> a(n);
    for (int i = 0; i < n; i++) {
        auto &[r, l] = a[i];
        cin >> l >> r;
    }
    sort(a.begin(), a.end());

    int ans = 0;
    int pre = -1;
    int cur = -1;
    for (int i = 0; i < n; i++) {
        auto &[r, l] = a[i];
        if (l <= cur) {
            continue;
        }
        if (l <= pre) {
            ans++;
            cur = r;
        } else {
            pre = r;
        }
    }
    cout << ans << '\n';

    return 0;
}

J

本来我感觉都是 NO，但是样例说 $1$ 的时候是 YES，那又感觉似乎只有 $1$ 是 YES。

K

感觉不需要操作 $3$ ，发现只要 $1, 2$ 交替即可，答案为 $\lceil \frac{n}{2}\rceil$ 。

L

数位 $\text{dp}$ 。

M

存在 $(x, y)$ 和 $(y, z)$ 边，那么 $z$ 是 $x$ 的孙子，那么枚举 $y$ ， $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> deg(n);
    vector<vector<int>> g(n);
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        u--, v--;
        deg[u]++;
        g[v].push_back(u);
    }

    vector<i64> ans(n);
    for (int y = 0; y < n; y++) {
        for (auto &z : g[y]) {
            ans[z] += deg[y];
        }
    }

    for (int i = 0; i < n; i++) {
        cout << ans[i] << " \n"[i == n - 1];
    }
    
    return 0;
}