2025 NTU Training 8

A - Covid-19

签到

AC Code

#include "bits/stdc++.h"

int main() {
    int p, q;
    std::cin >> p >> q;

    if (p <= 50 && q <= 10) std::cout << "White\n";
    else if (q > 30) std::cout << "Red\n";
    else std::cout << "Yellow\n";
}

B - Statistics

要求单调不增，每一步维护前缀的最小值，如果当前值更大，那么就修改之；否则更新最小值。时间复杂度 $O(n)$ .

AC Code

#include <bits/stdc++.h>

constexpr int N = 1e4 + 10;

int n, a[N];
long long sum = 0;

int main() {
    std::cin >> n;
    for (int i = 1; i <= n; i++) std::cin >> a[i];

    int maxv = a[1];
    for (int i = 1; i <= n; i++) {
        if (maxv < a[i]) {
            sum += a[i] - maxv;
            a[i] = maxv;
        }
        maxv = std::min(maxv, a[i]);
    }

    std::cout << sum << "\n";
}

考虑按元素从小到大一个一个排序。假设 $0\sim t-1$ 已经排序完成，接下来把在 $k$ 位置上的数排到 $t$ 上. 由于每次交换的两个数的位置只能有一个 bit 位的差别，所以我们只需要从 lowest bit 往 highest bit 考虑，如果 $k,t$ 的 $i$ -th bit 不一致，那么就交换 $a_k,a_{k\oplus 2^i}$ . 我们可以证明 $k\oplus 2^i$ 一定不会 $\lt t$ （然而我不会证，我是猜的）

所以总的交换次数最多为 $O(n\log n)$ ， $10\times 1024\lt 12000$ .

AC Code

#include <bits/stdc++.h>
#include <cstdlib>

constexpr int N = (1 << 10) + 10;
int n, a[N], T;
std::map<int, int> p;
std::vector<std::pair<int, int>> ans;

int main() {
    std::cin >> n, T = 1 << n;
    for (int i = 0; i < T; i++) std::cin >> a[i];
    for (int i = 0; i < T; i++) p[a[i]] = i;

    int place = 0;
    auto get = [&](int v, int i) { return v >> i & 1; };
    auto mod = [&](int v, int i) { return v ^ (1 << i); };

    for (auto [val, id] : p) {
        assert(id >= place);

        for (int i = 0; i < n; i++) {
            if (get(id, i) != get(place, i)) {
                p[val] = mod(id, i);
                p[a[mod(id, i)]] = id;
                std::swap(a[id], a[mod(id, i)]);
                id = mod(id, i);

                ans.push_back({id, mod(id, i)});
            }
        }

        place++;
    }

    assert(ans.size() <= 12000);
    std::cout << ans.size() << "\n";
    for (auto [i, j] : ans) std::cout << i << " " << j << "\n";
}

L - The Last Supper

因为有时间上的顺序，如果我们定义 $dp[i][j]$ 为 $i$ 可以感染 $j$ ，那么考虑

i\to i-1 \\ i+1\to i

这样会错误地让 $i+1$ 也可以感染 $i-1$ 实际上并不行。所以我们定义 $dp[i][j]$ 为 $i$ 可以被 $j$ 感染，这样上述的问题就不存在了. 因为是存在性 DP，所以转移式是（考虑 $i\to j$ ）

\forall k, dp[j][k] \texttt{ |= } dp[i][k]

用 std::bitset 可以优化到 $O(\frac{qn}{w})$ ，足以通过此题.

AC Code

#include <bits/stdc++.h>
constexpr int N = 1e5 + 10;
using bset = std::bitset<N>;

int n, m, q;
int af[N];
bset from[N];

int main() {
    std::cin.tie(0)->sync_with_stdio(0);
    std::cout.tie(0);

    std::cin >> n >> m >> q;
    for (int i = 1; i <= m; i++) std::cin >> af[i];
    for (int i = 1; i <= n; i++) from[i].set(i);

    while (q--) {
        int id, next;
        char c;

        std::cin >> id >> c;
        if (c == 'L') next = id == n ? 1 : id + 1;
        else next = id == 1 ? n : id - 1;

        from[next] |= from[id];
    }

    bset ans;
    for (int i = 1; i <= n; i++) ans.set(i);
    for (int i = 1; i <= m; i++) ans &= from[af[i]];

    for (int i = 1; i <= n; i++)
        if (ans.test(i)) std::cout << i << " ";
    std::cout << "\n";
}

2025 NTU Training 8

A - Covid-19

B - Statistics

C - Science Fiction

L - The Last Supper