牛客练习赛73

A 招生

int main() {
    IOS; cin >> n >> m >> k;
    vector<ll> a;
    rep (i, 1, n) {
        ll x, y; cin >> x >> y;
        a.pb(x * 85 + y * 15);
    }
    sort(all(a), greater<ll>());
    ll c = (a[m - 1] - k * 15 - 1) / 85 + 1;
    if (k * 15 >= a[m - 1]) c = 0;
    cout << c << '
';
    return 0;
}

遥远的记忆

并查集

int find(int x) { return x == f[x] ? x : f[x] = find(f[x]); }

void unit(int x, int y) {
    x = find(x), y = find(y);
    if (x == y) return;
    f[y] = x;
}

int main() {
    IOS; cin >> n;
    rep (i, 1, n) cin >> a[i], f[i] = i;
    rep (i, 2, n - 1) if (a[i] == 0) unit(i, i - 1); else unit(i, i + 1);
    if (a[1] == 1) unit(1, 2);
    if (a[n] == 0) unit(n, n - 1);
    rep (i, 1, n) if (f[i] == i) ++m;
    cout << m;
    return 0;
}

C 生涯回忆录

组合数学

对于任意一种 权值k, 只能算 i(a[i] = k, i = min) 的贡献

即 权值小于k的, 在集合中至少出现一次 (2^{cnt} - 1), 权值大于k的 (2^{cnt}), 乘贡献值 i 即可

ll qpow(ll a, ll b) {
    ll ans = 1;
    for (; b; b >>= 1, a = a * a % mod)
        if (b & 1) ans = ans * a % mod;
    return ans;
}

int main() {
    IOS; cin >> n; b[0].fi = -2e9;
    rep (i, 1, n) cin >> a[i];
    sort(a + 1, a + 1 + n);
    rep (i, 1, n) {
        if (a[i] == b[m].fi) ++b[m].se;
        else b[++m] = { a[i], 1 };
    }
    ll ans = 0, sum = 1, s = 0;
    rep (i, 1, m + 1) {
        if (i != b[i].fi) {
            ans = (ans + qpow(2, n - s) * sum % mod * i % mod) % mod;
            break;
        }
        s += b[i].se;
        ans = (ans + qpow(2, n - s) * sum % mod * i % mod);
        sum  = (qpow(2, b[i].se) - 1 + mod) % mod * sum % mod;
    }
    cout << ans;
    return 0;
}

D 离别

通过线段树等数据结构或stl, 维护出对与i的贡献区间, 及[l, r], 在维护个前缀和

对于询问[L, R], 对于所有 i 属于 [L, R] 且 r <= R, 直接前缀和计算

对于 i 属于 [L, R], l <= R < r 的, 用容斥计算, 也是要维护个前缀和

剩下的看代码吧

int n, m, _, k;
int v[N], l[N], r[N];
ll s[N], t[N];

struct BIT {
    int val[N << 2];
    void change(int rt, int v, int l, int r, int k) {
        if (l == r) { val[rt] += k; return; }
        int mid = l + r >> 1;
        if (v <= mid) change(rt << 1, v, l, mid, k);
        else change(rt << 1 | 1, v, mid + 1, r, k);
        val[rt] = max(val[rt << 1], val[rt << 1 | 1]);
    }
} A, B;

int main() {
    IOS; cin >> n >> m >> k;
    rep (i, 1, n) cin >> v[i];
    for (int i = 1, a = 0, b = 0; i <= n; ++i) {
        while (a < n && A.val[1] < k) A.change(1, v[++a], 1, n, 1);
        while (b < n && B.val[1] <= k) B.change(1, v[++b], 1, n, 1);
        if (B.val[1] > k) B.change(1, v[b--], 1, n, -1);
        if (A.val[1] < k) l[i] = r[i] = n + 1;
        else l[i] = a, r[i] = b;
        s[i] = s[i - 1] + r[i] - l[i] + 1, t[i] = t[i - 1] + l[i] - 1;
        A.change(1, v[i], 1, n, -1); B.change(1, v[i], 1, n, -1);
    }
    rep (i, 1, m) {
        int x, y; cin >> x >> y;
        ll a = x - 1, b = x - 1;
        per (j, 18, 0) {
            if (a + (1 << j) <= n && r[a + (1 << j)] <= y) a += 1 << j;
            if (b + (1 << j) <= n && l[b + (1 << j)] <= y) b += 1 << j;
        }
        cout << s[a] - s[x - 1] + (b - a) * y - t[b] + t[a] << '
';
    }
    return 0;
}