1993(963div2)

A. Question Marks

蒂姆正在做一个由 $4 n$ 个问题组成的测试；每个问题有 $4$ 个选项：A"、"B"、"C "和 "D"。每个选项都有 $n$ 个正确答案，也就是说有 $n$ 道题的答案是 "A"， $n$ 道题的答案是 "B"， $n$ 道题的答案是 "C"， $n$ 道题的答案是 "D"。

对于每道题，蒂姆都会把答案写在答题纸上。如果想不出答案，他会在该题上留下问号"？

他的答题纸上有 $4 n$ 个字符。蒂姆最多能答对多少题？

void solve() {
    int n;cin >> n;
    string s;cin >> s;
    int a = count(s.begin(), s.end(), 'A');
    int b = count(s.begin(), s.end(), 'B');
    int c = count(s.begin(), s.end(), 'C');
    int d = count(s.begin(), s.end(), 'D');
    int ans = 4 * n;
    ans -= max(n - a, 0);
    ans -= max(n - b, 0);
    ans -= max(n - c, 0);
    ans -= max(n - d, 0);
    cout << ans << '\n';
}

B. Parity and Sum

给定一个由 $n$ 个正整数组成的数组 $a$ 。

在一次操作中，你可以选取任意一对索引 $(i, j)$ ，使得 $a_{i}$ 和 $a_{j}$ 具有不同的奇偶性，然后用它们的和替换较小的那个。更正式的说法是

如果 $a_{i} < a_{j}$ ，则用 $a_{i} + a_{j}$ 替换 $a_{i}$ ；
否则，用 $a_{i} + a_{j}$ 替换 $a_{j}$ 。

求使数组中所有元素具有相同奇偶性所需的最少操作数。

易得每次尽量都用一次操作将所有的偶数给变为奇数，若需要两次操作的话，直接将最大的偶数与这个奇数来进行操作，后面每个数同样一定为 1 次，最多也只会超出一次操作。

需要特判全为偶数的情况

#define int long long
void solve() {
    int n;cin >> n;
    vector<int> a(n + 1);
    for (int i = 1;i <= n;i++)cin >> a[i];
    vector<int> even;
    int odd = 0;
    for (int i = 1;i <= n;i++) {
        if (a[i] % 2 == 0)even.push_back(a[i]);
        else odd = max(odd, a[i]);
    }
    if (!odd) {
        cout << "0\n";return;
    }
    sort(even.begin(), even.end());
    int cnt = 0, ok = 1;
    for (auto x : even) {
        if (odd < x) {
            ok = 0;
        }
        odd += x;
    }
    cout << even.size() + !ok << '\n';
}

C. Light Switches

有一栋公寓由 $n$ 个房间组成，每个房间的灯**最初都是关着的。

为了控制这些房间的灯光，公寓的主人决定在房间里安装芯片，这样每个房间正好有一个芯片，芯片安装在不同的时间。具体来说，这些时间由数组 $a_{1}, a_{2}, \dots, a_{n}$ 表示，其中 $a_{i}$ 是在 $i$ /th 房间安装芯片的时间（分钟）。

芯片一经安装，每隔 $k$ 分钟就会改变房间的灯光状态--在 $k$ 分钟内开灯，然后在接下来的 $k$ 分钟内关灯，再在接下来的 $k$ 分钟内开灯，以此类推。换句话说，芯片会在 $a_{i}$ 、 $a_{i} + k$ 、 $a_{i} + 2 k$ 、 $a_{i} + 3 k$ 、 $\dots$ 分钟时改变 $i$ /房间的灯光状态。

公寓里所有房间最早亮灯的时刻是什么时候？

易得答案总数大于等于最晚开灯的时间的。且不会很大，求这些区间的交集的最小值

#define int long long
void solve() {
    int n, k;cin >> n >> k;
    vector<int>a(n + 1);
    for (int i = 1;i <= n;i++)cin >> a[i];
    sort(a.begin() + 1, a.end());
    for (int i = 1;i < n;i++) {
        if (a[i] + k < a[n]) {
            int b = (a[n] - a[i]) / k;
            if (b & 1)b++;
            a[i] += b * k;
        }
    }

    int l = 1, r = 1e18;
    for (int i = 1;i <= n;i++) {
        l = max(l, a[i]);
        r = min(r, a[i] + k);
    }
    if (l >= r) {
        cout << "-1\n";return;
    }
    cout << l << '\n';
}

D. Med-imize

给定两个正整数 $n$ 和 $k$ 以及另一个由 $n$ 个整数组成的数组 $a$ 。

在一次操作中，可以选择 $a$ 的任意一个大小为 $k$ 的子数组，然后将其从数组中删除，而不改变其他元素的顺序。更正式地说，假设 $(l, r)$ 是对子数组 $a_{l}, a_{l + 1}, \dots, a_{r}$ 的操作，这样 $r - l + 1 = k$ ，那么执行这个操作就意味着将 $a$ 替换为 $[a_{1}, \dots, a_{l - 1}, a_{r + 1}, \dots, a_{n}]$ 。

当 $a$ 的长度大于 $k$ 时，您必须重复操作。(即 $| a | > k$ ）。处理后数组 $a$ 中所有剩余元素的最大可能中位数 $^{†}$ 是多少？

Solution

EDU: 二分+DP

注意：我的二分写法需要将 r 的范围多拓展一点，不然可能会错

366 之后补

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

    int l = 0, r = 2e9;
    while (l < r) {
        int mid = l + r >> 1;
        for (int i = 0;i < n;i++) {
            if (a[i] >= mid) {
                b[i] = 1;
            } else {
                b[i] = -1;
            }
        }
        dp[0] = b[0];
        for (int i = 1;i < n;i++) {
            if (i % k == 0) {
                dp[i] = max(dp[i - k], b[i]);
            } else {
                dp[i] = dp[i - 1] + b[i];
                if (i > k) {
                    dp[i] = max(dp[i], dp[i - k]);
                }
            }
        }
        if (dp[n - 1] <= 0)r = mid;
        else l = mid + 1;
    }
    cout << l - 1 << '\n';
}