Codeforces Round 1048 (Div. 1)

Codeforces Round 1048 (Div. 1)

Date 2025.09.08

A	B	C1	C2	D	E1	E2	F
O	O	O	O	Ø

D - Antiamuny and Slider Movement

首先一个 trick 是，你可以把求和转化成求期望（对 $q!$ 种操作序列求平均），再乘上 $q!$。

这样的话，你就可以枚举每个滑块，再枚举最后决定滑块位置的那一次操作，统计贡献。

还有一个 trick 是，因为滑块不会越过另外一个滑块，相对位置是不变的，所以可以让 a[i] -= i; b[i].x -= b[i].id; 转化成相对位置。

令 $b_i = a_i - i$，这样 $b_i$ 是单调不降的。且原来 $a_i \le a_{i + 1} - 1$ 的约束变成了 $b_i \le b_{i + 1}$。

$a_i \leftarrow x$ 对应为 $b_i \leftarrow x - i$。

并且，对于左右滑块位置的更新也从加减操作变成了取 min/max 操作：

• 往左一侧（$j<i$）：$a^\prime_j=\min(a_j,a^\prime_{j+1}-1) \Longrightarrow b^\prime_j=\min(b_j,b^\prime_{j+1}).$
• 往右一侧（$j>i$）：$a^\prime_j=\max(a_j,a^\prime_{j-1}+1) \Longrightarrow b^\prime_j=\max(b_j,b^\prime_{j-1}).$

因此有一个推论，若只看对第 $i$ 个滑块的影响，把第 $id$ 个（目标 $x$）作用一次对 $b_i$ 的“净效果”是
$$
b_i \leftarrow
\begin{cases}
\max(b_i,x), & id<i。\
x, & id=i。 \
\min(b_i,x), & id>i。 \
\end{cases}
$$

那么回到之前说的，枚举滑块 $[i, x]$，枚举最后一个决定位置的操作 $[j, y]$。假如你现在维护了一个可能对当前滑块最终位置有影响的集合 $S$
根据定义，$S$ 只有可能是 $j > i$ 且 $y < x$ 或者 $j < i$ 且 $y \ge x$ 的元素
并且最终是操作 $[j, y]$ 决定了 滑块 $i$ 的最终位置。
那么需要满足的条件是：

• $j$ 在 $S$ 中是最后一个元素
• 倒数第二个必须是 $j > i$ 且 $y < x$ 的，因为不能是 $j < i$ 且 $y \ge x$。

只需要维护这两种的数量，然后算算组合数即可。

时间复杂度 $O(nq)$

void solve() {
    int n, m, q; 
    cin >> n >> m >> q;

    vector<int> a(n);
    for (auto &x : a) cin >> x;

    vector<pii> b(q);
    for (auto &[id, x] : b) cin >> id >> x;

    for (int i = 0; i < n; i++) a[i] -= i;
    for (int i = 0; i < q; i++) {
        auto &[id, x] = b[i];
        id--, x -= id;
    }

    ranges::sort(b, [&](auto i, auto j) {
        return i.second < j.second;
    });

    for (int i = 0; i < n; i++) {
        int f = 0;
        for (auto [id, x] : b) {
            if (id <= i and x >= a[i]) f = 1;
            if (id >= i and x < a[i]) f = 1;
        }
        if (!f) { 
            cout << Z(a[i] + i) * comb.fac(q) << " \n"[i == n - 1];
            continue; 
        }

        Z res = 0;
        int cl = 0, cr = 0;
        for (auto [id, x] : b) if (id <= i) cr++;

        for (auto [id, x] : b) {
            if (id <= i) cr--;

            Z fp = x + i;
            Z denom = comb.inv(cl + cr + 1) * comb.inv(cl + cr);

            if (id == i) {
                res += fp / (cl + cr + 1);
            } else if (id < i) {
                if (cl == 0 and cr == 0 and a[i] <= x) {
                    res += fp;
                } else {
                    res += fp * cl * denom;
                }
            } else {
                if (cl == 0 and cr == 0 and a[i] > x) {
                    res += fp;
                } else {
                    res += fp * cr * denom;
                }
            }

            if (id >= i) cl++;
        }

        cout << res * comb.fac(q) << " \n"[i == n - 1];
    }
}

C1 & C2 - Maple and Tree Beauty

01 背包即可，bitset 优化一下

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

    vector<vector<int>> g(n + 1);
    vector<int> p(n + 1);
    for (int i = 2; i <= n; i++) {
        p[i] = read();
        g[p[i]].eb(i);
    }

    vector<int> dep(n + 1);

    dep[1] = 1;
    auto dfs = [&](this auto&& dfs, int u) -> void {
        for (int v : g[u]) {
            dep[v] = dep[u] + 1;
            dfs(v);
        }
    };
    dfs(1);

    int dmin = inf;
    for (int i = 1; i <= n; i++) {
        if (g[i].empty()) {
            dmin = min(dmin, dep[i]);
        }
    }

    vector<int> cnt(dmin + 1, 0);
    for (int i = 1; i <= n; i++) {
        if (dep[i] <= dmin) cnt[dep[i]]++;
    }

    vector<int> cost;
    for (int d = 1; d <= dmin; d++) cost.eb(cnt[d]);
    ranges::sort(cost); 

    const int MAXK = 200000 + 5;
    bitset<MAXK> dp;
    dp[0] = 1; 

    int tot = 0;
    int ans = 0;
    int m = cost.size();

    for (int i = 0; i < m; i++) {
        int w = cost[i];
        tot += w;

        if (w <= 200000) dp |= (dp << w);

        int L = max(0LL, tot - (n - k));
        int R = min(k, tot);
        bool f = 0;
        for (int s = L; s <= R; s++) {
            if (dp.test(s)) { f = 1; break; }
        }
        if (f) ans = i + 1;
    }

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

B - Antiamuny Wants to Learn Swap

check 一下是否存在 3 2 1 的子序列

如果是任意的话，还需 check 4 3 1 2

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

    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) a[i] = read();

    vector<int> l(n + 1, 0);
    {
        vector<int> st;
        st.reserve(n);
        for (int i = 1; i <= n; i++) {
            while (!st.empty() and a[st.back()] <= a[i]) st.pop_back();
            l[i] = st.empty() ? 0 : st.back();
            st.eb(i);
        }
    }
    vector<int> r(n + 1, n + 1);
    {
        vector<int> st;
        st.reserve(n);
        for (int i = n; i >= 1; --i) {
            while (!st.empty() and a[st.back()] >= a[i]) st.pop_back();
            r[i] = st.empty() ? n + 1 : st.back();
            st.eb(i);
        }
    }

    vector<int> f(n + 1, n);
    for (int i = 1; i <= n; i++) {
        if (l[i] != 0 && r[i] != n + 1) {
            f[l[i]] = min(f[l[i]], r[i] - 1);
        }
    }
    for (int i = n - 1; i >= 1; i--) {
        f[i] = min(f[i], f[i + 1]);
    }

    while (q--) {
        int l = read(), r = read();
        if (r <= f[l]) {
            cout << "YES\n";
        } else {
            cout << "NO\n";
        }
    }
}

A - Cake Assignment

反着来的话，会发现操作是唯一的

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

    int t = 1LL << (k + 1);    
    int half = 1LL << k;
    int p = x;                   

    vector<int> ans;
    while (p != half) {
        if (p < half) {
            ans.eb(1);
            p <<= 1;
        } else {                          
            ans.eb(2);
            p = (p << 1) - t;
        }
    }

    int n = ans.size();
    cout << n << "\n";
    ranges::reverse(ans);
    for (auto x : ans) cout << x << " ";
    cout << "\n";
}