Codeforces Round 995 (Div. 3) 题解

C

题意

\(n\) 道题，你会做其中 \(k\) 道，有 \(m\) 套试卷，每套有 \(n - 1\) 道题，\(a_i\) 代表这套卷子中没有的那一道题，判断对于每一套能否全部做对。

题解

显然 \(k < n - 1\) 时一定不能全对， \(k = n\) 时一定能全对，对于 \(k = n - 1\)，使用二分判断没有的那道题会不会做即可，如果会做，那么试卷里有一套题一定不会，否则能全对。

#include <bits/stdc++.h>
using namespace std;

using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;
using u128 = unsigned __int128;

void solve() {
    int n, m, k;
    cin >> n >> m >> k;
    vector<int> a(m + 1);
    vector<int> q(k + 1);
    for (int i = 1; i <= m; i++) {
        cin >> a[i];
    }
    for (int i = 1; i <= k; i++) {
        cin >> q[i];
    }
    if (k < n - 1) {
        for (int i = 1; i <= m; i++) {
            cout << 0;
        }
        cout << "\n";
        return;
    }
    if (k >= n) {
        for (int i = 1; i <= m; i++) {
            cout << 1;
        }
        cout << "\n";
        return;
    }
    for (int i = 1; i <= m; i++) {
        vector<int>::iterator it = lower_bound(q.begin() + 1, q.end(), a[i]);
        if (it != q.end() && *it == a[i]) {
            cout << 0;
        } else {
            cout << 1;
        }
    }
    cout << "\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

D

题意

给定 \(x,y\)，和一个数组 \(a\)，求这样的 （i，j），满足从数组中删去 \(a_i,a_j\) 后其余元素的和在 \(x,y\) 之间。

题解

对于每一个数 \(a_i\)，我们可以找到一个区间 \([l,r]\) ，要求删除区间内任意一个数和 \(a_i\) 后，剩下的和能满足条件，那么答案就加上 \(r - l + 1\) 即可，使用二分即可找到。

#include <bits/stdc++.h>
using namespace std;

using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;
using u128 = unsigned __int128;

void solve() {
    int n;
    i64 x, y;
    cin >> n >> x >> y;
    vector<i64> a(n + 1), pre(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        pre[i] = pre[i - 1] + a[i];
    }
    i64 ans = 0;
    sort(a.begin() + 1, a.end());
    for (int i = 1; i <= n; i++) {
        int r = upper_bound(a.begin() + 1, a.end(), pre[n] - a[i] - x) -
                a.begin() - 1,
            l = lower_bound(a.begin() + 1, a.end(), pre[n] - a[i] - y) -
                a.begin();
        if (l <= i) {
            l = i + 1;
        }
        if (l > r) {
            continue;
        }
        ans += (r - l + 1);
    }
    cout << ans << "\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

E

题意

有一个商品需要定价，每个人有两个期望 \(a_i,b_i\)，人们会买价格低于 \(b_i\) 的产品，但是会给贵于 \(a_i\) 的产品负面评价，在负面评价不能多于 \(k\) 的条件下，求能够卖出去的最大价钱。

题解

一个结论是，我们的定价必须为 \(a_i, b_i\) 之一，否则我们可以继续增大价格，仍然满足条件。

那么我们枚举每一个价格，判断以该价格能卖出去的件数和负面评价数，满足条件的话取最大值即可。

具体地，我们可以对两个数组排序，这对于答案是没有影响的（因为是否购买完全由 \(b\) 决定，差评完全由 \(a\) 决定，题目规定了 \(a<b\)，所以在买了的人里面找差评与 \(a\) 顺序无关），然后二分查找满足条件的数量即可。

#include <bits/stdc++.h>
using namespace std;

using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;
using u128 = unsigned __int128;

void solve() {
    int n, k;
    cin >> n >> k;
    vector<int> a(n + 1), b(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    for (int i = 1; i <= n; i++) {
        cin >> b[i];
    }
    sort(a.begin() + 1, a.end());
    sort(b.begin() + 1, b.end());
    i64 ans = 0;
    for (int i = 1; i <= n; i++) {
        auto cal = [&](int x) {
            int cntb =
                n - (lower_bound(b.begin() + 1, b.end(), x) - b.begin() - 1);
            int cnta =
                n - (lower_bound(a.begin() + 1, a.end(), x) - a.begin() - 1);
            // cerr << "cntb = " << cntb << "/ cnta = " << cnta << endl;
            if (cntb - cnta <= k) {
                return 1ll * x * cntb;
            }
            return 0ll;
        };
        ans = max(ans, cal(a[i]));
        ans = max(ans, cal(b[i]));
    }
    cout << ans << "\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

F

题意

\(n\) 张牌，初始第 \(m\) 张为王牌，进行连续的 \(q\) 次操作，每次操作选择一个位置，可以把这个位置的牌放到开头或结尾，回答每次询问王牌可能处于的位置有多少。

题解

一个观察是：如果给定的位置在王牌前面，那么王牌可选的位置就是原位置（这张牌放前面）和前一个位置（这张牌放后面），同理，如果给定的位置在王牌后面，那么可选的位置就是原位置和后一个位置，如果就是王牌，那么王牌就会在最前面和最后面。

因此，王牌出现的区间就是最前面，中间和最后面，我们可以维护出现的区间，对于每个区间，根据每次操作的情况进行维护：如果操作位置完全在区间的左边，那么区间往左拓展一格，如果完全在右边，区间往右，如果被区间包含，区间新增 \([1,1]\) 和 \([n,n]\)​，如果原区间长度为 1 则消失，否则保持长度。同时注意区间合并即可。

#include <bits/stdc++.h>
using namespace std;

using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;
using u128 = unsigned __int128;

void solve() {
    int n, m, q;
    cin >> n >> m >> q;
    vector<array<int, 2>> joker;
    joker.push_back({m, m});
    for (int i = 1; i <= q; i++) {
        int p;
        cin >> p;
        vector<array<int, 2>> copy;
        for (auto [l, r] : joker) {
            if (p < l) {
                copy.push_back({l - 1, r});
            } else if (p > r) {
                copy.push_back({l, r + 1});
            } else {
                copy.push_back({1, 1});
                copy.push_back({n, n});
                if (l != r) {
                    copy.push_back({l, r});
                }
            }
        }
        sort(copy.begin(), copy.end());
        joker.clear();
        for (auto [l, r] : copy) {
            if (joker.empty() || joker.back()[1] < l) {
                joker.push_back({l, r});
            } else {
                joker.back()[1] = max(joker.back()[1], r);
            }
        }
        i64 ans = 0;
        for (auto [l, r] : joker) {
            ans += r - l + 1;
        }
        cout << ans << " \n"[i == q];
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}