Good Bye 2024: 2025 is NEAR

比赛链接

Problems	AC	Note
A. Tender Carpenter	○
B. Outstanding Impressionist	○
C. Bewitching Stargazer	○
D. Refined Product Optimality	⊕	交换
E. Resourceful Caterpillar Sequence	⊕	game、树上计数
F. Earnest Matrix Complement
G. Naive String Splits
H. Delicate Anti-monotonous Operations
I1. Affectionate Arrays (Easy Version)
I2. Affectionate Arrays (Hard Version)

A

Code >folded

void solve() {
    int n = read();
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) a[i] = read();
    for (int i = 1; i + 1 <= n; i++) {
        int x = a[i];
        int y = a[i + 1];
        if (x < y) swap(x, y);

        if (x + x > y and y + y > x) {
            puts("YES");
            return;
        }
    }
    puts("NO");
}

B

Code >folded

void solve() {
    int n = read();
    vector<pii> a(n + 1);
    for (int i = 1; i <= n; i++) {
        a[i].fi = read();
        a[i].se = read();
    }
    
    vector<int> buk(2 * n + 1);
    vector<int> cnt(2 * n + 1);

    for (int i = 1; i <= n; i++) {
        auto [l, r] = a[i];
        if (l != r) {
            continue;
        }
        buk[l] = 1;
        cnt[l] ++;
    }
    for (int i = 1; i <= 2 * n; i++) {
        buk[i] += buk[i - 1];
    }

    for (int i = 1; i <= n; i++) {
        auto [l, r] = a[i];

        if ((l == r and cnt[l] == 1) or
            buk[r] - buk[l - 1] != r - l + 1) putchar('1');
        else putchar('0');
    }
    puts("");
}

C

天空中有 $n$ 颗星星，排成一排。Iris 有一架望远镜，她用它来看星星。

最初，Iris 观察线段 $[1, n]$ 中的星星，她的幸运值为 $0$ 。Iris 想要寻找她观察到的每个线段 $[l, r]$ 中间位置的星星。因此使用以下递归程序：

• 首先，她将计算 $m = \left\lfloor \frac{l+r}{2} \right\rfloor$ 。
• 如果线段长度（即 $r - l + 1$ ）为偶数，Iris 会将其分成两个等长的线段 $[l, m]$ 和 $[m+1, r]$ ，以便进一步观察。
• 否则，Iris 会将望远镜对准恒星 $m$ ，她的幸运值将增加 $m$ ；随后，如果为 $l \neq r$ ，Iris 将继续观察两个线段 $[l, m-1]$ 和 $[m+1, r]$ 。

Iris 有点懒。她用整数 $k$ 来定义她的懒惰程度：随着观察的进行，她不会继续观察任何长度严格小于 $k$ 的线段 $[l, r]$ 。在这种情况下，请预测她的最终幸运值。

$1 \leq k \leq n \leq 2\cdot 10^9$

注意到左子树和右子树是对称的，且差的只和当前这一层的中点以及数量有关。维护下即可

Code

void solve() {
    int n = read();
    int k = read();

    auto dfs = [&](this auto&& self, int l, int r) -> pii {
        int len = r - l + 1;
        if (len < k) return {0, 0};
        if (len == 1) return {l, 1};
        int m = l + r >> 1;

        if (len % 2 == 0) {
            auto [sum, cnt] = self(l, m);
            return {2 * sum + cnt * m, cnt * 2};
        } else {
            auto [sum, cnt] = self(l, m - 1);
            return {m + 2 * sum + cnt * m, cnt * 2 + 1};
        }
    };

    auto [ans, _] = dfs(1, n);
    cout << ans << '\n';
}

D

• Chris 得到两个数组 $a$ 和 $b$ ，均由 $n$ 个整数组成。
• Iris 感兴趣的是，在对 $b$ 进行任意重新排列后， $P = \prod\limits_{i=1}^n \min(a_i, b_i)$ 的最大可能值。请注意，她只想知道 $P$ 的最大值，并且不会对 $b$ 进行任何实际的重新排列。
• 将有 $q$ 次修改。每次修改都可以用两个整数 $o$ 和 $x$ 表示（ $o$ 是 $1$ 或 $2$ ， $1 \leq x \leq n$ ）。如果是 $o = 1$ ，那么 Iris 会将 $a_x$ 增加 $1$ ；否则，她会将 $b_x$ 增加 $1$ 。
• Iris 向 Chris 询问 $P$ 的最大值，共询问了 $q + 1$ 次：一次是在修改之前，另一次是在每次修改之后。
• 由于 $P$ 可能很大，Chris 只需要计算它对 $998,244,353$ 的模数。

显然的观察是两个数组分别排序最优。而且观察到每次变化不超过 $1$，随便维护下位置就做完了。

注意不要一个一个交换，复杂度是错的。

Code

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

    auto c = a;
    auto d = b;

    std::ranges::sort(c);
    std::ranges::sort(d);
    Z ans = 1;
    for (int i = 0; i < n; i++) {
        ans *= min(c[i], d[i]);
    }

    cout << ans << ' ';

    while (m--) {
        // int opt = read(), pos = read() - 1;
        int opt, x;
        cin >> opt >> x;
        x--;

        if (opt == 1) {
            a[x]++;
            int i = std::lower_bound(c.begin(), c.end(), a[x]) - c.begin() - 1;
            ans /= std::min(c[i], d[i]);
            c[i]++;
            ans *= std::min(c[i], d[i]);
        }
         if (opt == 2) {
            b[x]++;
            int i = std::lower_bound(d.begin(), d.end(), b[x]) - d.begin() - 1;
            ans /= std::min(c[i], d[i]);
            d[i]++;
            ans *= std::min(c[i], d[i]);
        }

        cout << ans << " \n"[m == 0];
    }
}

E

给定一棵树和一条毛毛虫 $(p, q)$ （一条树上路径），每次 N 和 A 交替移动，N 把毛毛虫的 p 端移动一步（身体也跟着动），类似地 A 把毛毛虫的 q 端移动一步，p 到叶子则 N 赢，q 到叶子则 A 赢。对满足 A 有必胜策略的初始毛毛虫计数。

Code

void solve() {
    int n = read();
    vector<vector<int>> g(n);

    for (int i = 1; i < n; i++) {
        int u = read() - 1, v = read() - 1;
        g[u].eb(v), g[v].eb(u);
    }

    if (n == 2) { puts("0"); return; }

    int cnt = 0;
    int rt = 0;
    vector<int> leaf(n), sp(n);
    for (int i = 0; i < n; i++) {
        if (g[i].size() != 1) { rt = i; continue; }

        cnt++;
        leaf[i] = sp[i] = 1;
        for (auto j : g[i]) sp[j] = 1;
    }

    int ans = cnt * (n - cnt);

    vector<int> fa(n), sum(n), siz(n);
    auto dfs = [&](this auto&& self, int u, int f) -> void {
        fa[u] = f;
        sum[u] = sp[u], siz[u] = 1;
        for (auto v : g[u]) {
            if (v == f) continue;
            self(v, u);
            sum[u] += sum[v], siz[u] += siz[v];
        }
    };
    dfs(rt, -1);

    for (int i = 0; i < n; i++) {
        if (leaf[i]) continue;

        if (i != rt and sp[fa[i]] and !leaf[fa[i]]) {
            ans += (n - siz[i]) - (sum[rt] - sum[i]);
        }

        for (auto j : g[i]) {
            if (j == fa[i]) continue;
            if (sp[j] and !leaf[j]) ans += siz[j] - sum[j];
        }
    }

    cout << ans << '\n';
}