题解 | #2023牛客暑期多校训练营5#

A

考虑莫队，若 $a_{l} = a_{r}$ ，要知道在 $[l, r]$ 区间有多少个数小于 $a_{l}$ ，先用树状数组跑出每个位置前面有多少个小于它的数字，记为 $b_{i}$ ，则 $b_{r} - b_{l}$ 就可以得到在 $[l, r]$ 区间有多少个数小于 $a_{l}$ 的数量。

$O(n\log n+n\sqrt{n})$ ，跑了 $2\text{s}$ 。

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 = 5E5;

int cnt[N + 1];
i64 sum[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];
        a[i]--;
    }

    Fenwick<int> f(n);
    vector<int> b(n);
    for (int i = 0; i < n; i++) {
        b[i] = f.get(a[i]);
        f.modify(a[i], 1);
    }

    vector<array<int, 3>> q(m);
    for (int i = 0; i < m; i++) {
        auto &[l, r, j] = q[i];
        cin >> l >> r;
        l--, r--;
        j = i;
    }

    int bk = sqrt(n);
    sort(q.begin(), q.end(), [&](const auto &a, const auto &b) {
        return ((a[0] / bk) ^ (b[0] / bk))
                ? a[0] < b[0]
                : (((a[0] / bk) & 1) ? a[1] < b[1] : a[1] > b[1]);
    });

    int l = 0, r = -1;
    i64 res = 0;
    vector<i64> ans(m);

    auto add = [&](const int &i, const int &v) {
        int x = a[i];
        res += v * (1LL * cnt[x] * b[i] - sum[x]);
        cnt[x]++;
        sum[x] += b[i];
    };

    auto del = [&](const int &i, const int &v) {
        int x = a[i];
        cnt[x]--;
        sum[x] -= b[i];
        res -= v * (1LL * cnt[x] * b[i] - sum[x]);
    };

    for (int i = 0; i < m; i++) {
        auto &[ql, qr, qi] = q[i];
        while (r < qr) add(++r, +1);
        while (l > ql) add(--l, -1);
        while (l < ql) del(l++, -1);
        while (r > qr) del(r--, +1);
        ans[qi] = res;
    }

    for (int i = 0; i < m; i++) {
        cout << ans[i] << '\n';
    }
    
    return 0;
}

B

若 $w_{i}$ 都大于等于 $0$ ，那么就是选一段最短的连续区间使该区间和大于等于 $k$ ，存在负数那么问题变为找一段区间 $[l, r]$ ，然后在该区间中选 $x$ 个数使这 $x$ 个数之和大于等于 $k$ ，最小化 $r - l + (r - l + 1 - x)$ 。

贪心， $O(n^{2}\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, k;
    cin >> n >> k;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    int ans = 1E9;
    for (int l = 0; l < n; l++) {
        if (a[l] >= k) {
            ans = 0;
            continue;
        }
        i64 sum = 0;
        int x = 0;
        priority_queue<int> q;
        for (int r = l; r < n; r++) {
            if (a[r] >= 0) {
                sum += a[r];
                x++;
            } else {
                q.push(a[r]);
            }
            while (!q.empty()) {
                auto cur = q.top();
                if (sum + cur >= k) {
                    sum += cur;
                    q.pop();
                    x++;
                } else {
                    break;
                }
            }
            if (sum >= k && x != 0) {
                ans = min(ans, r - l + r - l + 1 - x);
            }
        }
    }
    cout << (ans == 1E9 ? -1 : ans) << '\n';

    return 0;
}

C

把 $(i, j + n)$ 的边视为连边 $(i, j)$ ，根据竞赛图的性质，其一定存在一条哈密顿路径，最大匹配至少为 $n - 1$ ，若有一个强连通分量大小为 $1$ 则 $n - 1$ ，否则为 $n$ 。

用兰道定理根据点的度数可以快速判断。

下面这个数据输出 $6$ 。

数据

7
0 1 0 1 1 1 1
0 0 1 1 1 1 1
1 0 0 1 1 1 1
0 0 0 0 1 1 1
0 0 0 0 0 1 0
0 0 0 0 0 0 1
0 0 0 0 1 0 0

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> deg(n);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            int x;
            cin >> x;
            if (x) {
                deg[j]++;
            }
        }
    }

    sort(deg.begin(), deg.end());
    
    int sum = 0;
    for (int i = 0; i < n - 1; i++) {
        sum += deg[i];
        if (sum == (i + 1) * i / 2) {
            cout << n - 1 << '\n';
            return 0;
        }
    }
    cout << n << '\n';
    
    return 0;
}

D

直接数， $O(\sqrt{c} \log c)$ 。

C++ Code

#include "bits/stdc++.h"

using namespace std;
using i64 = long long;

void solve() {
    int k, c, n;
    cin >> k >> c >> n;

    int ans = 0;
    for (int i = 1; i64(i) * i <= c; i++) {
        if (c % i == 0) {
            int b0 = i, b1 = c / i;

            int ka = c - b0;
            if (ka > 0 && ka % k == 0) {
                int a = ka / k;
                if (gcd(a, b0) >= n) {
                    ans++;
                }
            }
            if (b0 == b1) {
                continue;
            }
            ka = c - b1;
            if (ka > 0 && ka % k == 0) {
                int a = ka / k;
                if (gcd(a, b1) >= n) {
                    ans++;
                }
            }            
        }
    }
    cout << ans << '\n';
    
}

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

    return 0;
}

G

双指针， $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, k;
    cin >> n >> k;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        a[i]--;
    }
    
    vector<int> c(4);
    auto check = [&]() {
        for (int j = 0; j < 3; j++) {
            if (c[j] == 0) {
                return false;
            }
        }
        if (c[3] < k) {
            return false;
        }
        return true;
    };

    int ans = 1E9;
    for (int i = 0, j = -1; i < n; i++) {
        while (j + 1 < n && !check()) {
            j++;
            c[a[j]]++;
        }
        if (i <= j && check()) {
            ans = min(ans, j - i + 1);
        }
        j = max(j, i);
        c[a[i]]--;
    }
    cout << ans << '\n';
    
    return 0;
}

I

一个数组的所有子区间异或和的和是一个经典问题黑暗爆炸 - 4017。

在这个问题的基础上，按位考虑贡献，做三次前缀和。

$O (90 n)$ 。

C++ Code

#include "bits/stdc++.h"

using namespace std;
using i64 = long long;

constexpr int P = 998244353;

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<int> sum(n + 1);
    for (int i = 0; i < n; i++) {
        sum[i + 1] = sum[i] ^ a[i];
    }

    vector<i64> f(n + 1, 1);
    for (int times = 0; times < 3; times++) {
        vector<i64> g(n + 1);
        for (int j = 0; j < 30; j++) {
            i64 v[2] = {f[0], 0};
            for (int i = 1; i <= n; i++) {
                int b = sum[i] >> j & 1;
                g[i] = (g[i] + (1 << j) * v[b ^ 1] % P) % P;
                v[b] = (v[b] + f[i]) % P;
            }
        }
        for (int i = 0; i < n; i++) {
            g[i + 1] = (g[i + 1] + g[i]) % P;
        }
        swap(f, g);
    }
    cout << f[n] << '\n';

    return 0;
}