Codeforces Round 1053 (Div. 1)

Codeforces Round 1053 (Div. 1)

Date 2025/09/25

A	B	C	D	E1	E2	F	G
O	O	O	Ø	Ø

D - Attraction Theory

又是这个 trick，求 sum 不好求，转化为求 期望 乘上对应 概率。

让我们先做一些转化：

令 $f_i$ 表示 $i$ 这个位置上的人数

我们可以通过分析某个 attraction 放在不同位置时会发生什么，轻松得到以下必要条件：

• 存在某个区间 $1 \le L \le R \le n$，使得当且仅当 $L \le i \le R$ 时 $f_i \ge 1$。
• 对于所有满足 $L < i < R$ 的 $i$，都有 $f_i$ 是奇数。

进一步，这些条件也是充分的。一种简单的构造方式是：对于最终停在位置 $i$ 的那一组人，把 $\frac{f_i}{2}$ 个 attraction 放在该组人的中心位置（两端情况容易处理）。最后可能还需要做一些平移，这可以通过在位置 1 或 $n$ 上放 attraction 来完成。

现在假设 $L = 1, R = K (K > 1)$。我们有方程

$$
f_1 + f_2 + f_3 + \ldots + f_k = n
$$

并且 $f_i \ge 1$，且当 $i \ne 1, i \ne k$ 时 $f_i$ 是奇数。我们想要求的是所有情况的

$$
\sum f_i \cdot a_i
$$

固定 $f_1, f_k$ 的奇偶性，分别设为 $x, y$（其中 $1 \le x, y \le 2$），然后令：

• 对于 $i \ne 1, i \ne k$，有 $f_i = 2 \cdot g_i + 1$；
• $f_1 = 2 \cdot g_1 + x$；
• $f_k = 2 \cdot g_k + y$。

设

$$
S = n - x - y - (k - 2)。
$$

那么方程变为

$$
\sum g_i = \frac{S}{2},
$$

若 $S$ 是奇数，则无解。那么 $S$ 是偶数。

我们可以把方程转化为

$$
\sum ways \cdot \mathbb{E}[f_i] \cdot a_i,
$$

其中 $ways$ 是解的个数，隔板法即可求出为

$$
ways = \binom{\frac{S}{2} + k - 1}{k - 1}
$$

由于 $g_i$ 对称，$\mathbb E[g_i]=\dfrac{S}{2k}$。中间位 $2\le i\le k-1$ 的期望 $ \mathbb E[f_i]=\dfrac{S}{k}+1$；两端 $i=1,k$ 的常数项由 $x,y$ 决定（为 1 或 2）。
目标是对所有有效 $[L,R]$（等价于所有长度为 $k$ 的区间、所有 $(x,y)$）累加 $\sum f_i\cdot a_{L+i-1}$。这可拆成：“中间位统一的期望系数” $(\dfrac{S}{k}+1)$ 乘上所有长度为 $k$ 的子数组的总和；
两端若 $x=2$ 或 $y=2$ 的“多出来的 +1”各自乘上“所有长度为 $k$ 的子数组里左端/右端的元素总和”。

用前缀和的前缀和一次性得到：
所有长度为 $k$ 的子数组和的总和；
所有长度为 $k$ 的左端元素之和、右端元素之和。

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

    vector<Z> a(n + 1);
    for (int i = 1; i <= n; i++) {
        a[i] = read();
    }
    vector<Z> s(n + 1), ss(n + 1);
    for (int i = 1; i <= n; i++) {
        s[i] = s[i - 1] + a[i];
    }
    for (int i = 1; i <= n; i++) {
        ss[i] = ss[i - 1] + s[i];
    }

    Z ans = s[n] * n;

    for (int k = 2; k <= n; k++) {
        for (int x : {1, 2}) {
            for (int y : {1, 2}) {
                int S = n - x - y - (k - 2);
                if (S % 2 == 1 or S < 0) continue;

                int v = S / 2;
                Z ways = comb.binom(v + k - 1, v);
                Z avg = Z(S) / k + 1;
                Z sum = ss[n] - ss[k - 1] - ss[n - k];

                ans += ways * avg * sum;

                if (x == 2) {
                    Z sum = s[n - k + 1];
                    ans += sum * ways;
                }
                if (y == 2) {
                    Z sum = s[n] - s[k - 1];
                    ans += sum * ways;
                }
            }
        }
    }

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

E1 - Hidden Single (Version 1)

int ask(vector<int> S, int x) {
    cout << "? " << x << " " << S.size() << ' ';
    for (auto x : S) cout << x << ' ';
    cout << endl;
    return read();
}

vector<int> range(int l, int r) {
    vector<int> res;
    for (int i = l; i <= r; i++) {
        res.eb(i);
    }
    return res;
}

int go(int l, int r, vector<int> vals, vector<int> waste) {
    if (l == r) return vals.back();

    int len = (r - l + 1) / 2;
    int mid = l + len - 1;

    vector<int> vl = range(l, mid);
    vector<int> vr = range(mid + 1, r);

    int siz = mid - l + 1;
    vector<int> waste_l, waste_r;

    for (auto x : waste) {
        if (ask(vl, x)) {
            waste_l.eb(x);
        } else {
            waste_r.eb(x);  
        } 
    }

    vector<int> vals_l, vals_r;

    for (auto x : vals) {
        int r1 = ask(vl, x);
        int r2 = ask(vr, x);

        if (r1 and r2) {
            waste_l.eb(x);
            waste_r.eb(x);
        } else if (r1 and !r2) {
            vals_l.eb(x);
        } else if (!r1 and r2) {
            vals_r.eb(x);
        }
    }

    siz -= waste_l.size();

    if (siz & 1) {
        return go(l, mid, vals_l, waste_l);
    } else {
        return go(mid + 1, r, vals_r, waste_r);
    }
};

void solve() {
    int n = read();
    int ans = go(1, 2 * n - 1, range(1, n), {});
    cout << "! " << ans << endl;
}

C - Limited Edition Shop

如果物品 $x$ 在 $A$ 里面的优先级高于 $y$，那么如果想只拿 $y$ 不拿 $x$，那么必须 $B$ 里面也是这个相对优先级顺序

因此可以令

$$
dp_{(i, j)} = \text{Alice 在前 } i \text{ 个物品中能够取得的最大总和，且 Bob 所选物品的 } pos_x \text{ 最大值为 } j
$$

转移方式：

• 我们允许 Alice 拿物品 $i+1$ 当且仅当 $pos_i > j$。
• Bob 可以无条件拿物品 $i+1$，此时 $j$ 更新为 $\max(j, pos_{i+1})$。

然后我们用线段树来优化存储状态 $j$。第一类转移对应一个区间加法操作，第二类转移可以拆分为 $j < pos_{i+1}$ 和 $j > pos_{i+1}$ 两种情况：前者不需要操作，后者需要做区间最大值查询。

所有这些操作都可以用懒标记线段树处理。时间复杂度是 $O(n \cdot \log n)$。

template<class Info, class Tag>
struct LazySegmentTree {
    int n;
    std::vector<Info> info;
    std::vector<Tag> tag;
    LazySegmentTree() : n(0) {}
    LazySegmentTree(int n_, Info v_ = Info()) {
        init(n_, v_);
    }
    template<class T>
    LazySegmentTree(std::vector<T> init_) {
        init(init_);
    }
    void init(int n_, Info v_ = Info()) {
        init(std::vector(n_, v_));
    }
    template<class T>
    void init(std::vector<T> init_) {
        n = init_.size();
        info.assign(4 << std::__lg(n), Info());
        tag.assign(4 << std::__lg(n), Tag());
        std::function<void(int, int, int)> build = [&](int p, int l, int r) {
            if (r - l == 1) {
                info[p] = init_[l];
                return;
            }
            int m = (l + r) / 2;
            build(2 * p, l, m);
            build(2 * p + 1, m, r);
            pull(p);
        };
        build(1, 0, n);
    }
    void pull(int p) {
        info[p] = info[2 * p] + info[2 * p + 1];
    }
    void apply(int p, const Tag &v) {
        info[p].apply(v);
        tag[p].apply(v);
    }
    void push(int p) {
        apply(2 * p, tag[p]);
        apply(2 * p + 1, tag[p]);
        tag[p] = Tag();
    }
    void modify(int p, int l, int r, int x, const Info &v) {
        if (r - l == 1) {
            info[p] = v;
            return;
        }
        int m = (l + r) / 2;
        push(p);
        if (x < m) {
            modify(2 * p, l, m, x, v);
        } else {
            modify(2 * p + 1, m, r, x, v);
        }
        pull(p);
    }
    void modify(int p, const Info &v) {
        modify(1, 0, n, p, v);
    }
    Info rangeQuery(int p, int l, int r, int x, int y) {
        if (l >= y || r <= x) {
            return Info();
        }
        if (l >= x && r <= y) {
            return info[p];
        }
        int m = (l + r) / 2;
        push(p);
        return rangeQuery(2 * p, l, m, x, y) + rangeQuery(2 * p + 1, m, r, x, y);
    }
    Info rangeQuery(int l, int r) {
        return rangeQuery(1, 0, n, l, r);
    }
    void rangeApply(int p, int l, int r, int x, int y, const Tag &v) {
        if (l >= y || r <= x) {
            return;
        }
        if (l >= x && r <= y) {
            apply(p, v);
            return;
        }
        int m = (l + r) / 2;
        push(p);
        rangeApply(2 * p, l, m, x, y, v);
        rangeApply(2 * p + 1, m, r, x, y, v);
        pull(p);
    }
    void rangeApply(int l, int r, const Tag &v) {
        return rangeApply(1, 0, n, l, r, v);
    }
    void half(int p, int l, int r) {
        if (info[p].act == 0) {
            return;
        }
        if ((info[p].min + 1) / 2 == (info[p].max + 1) / 2) {
            apply(p, {-(info[p].min + 1) / 2});
            return;
        }
        int m = (l + r) / 2;
        push(p);
        half(2 * p, l, m);
        half(2 * p + 1, m, r);
        pull(p);
    }
    void half() {
        half(1, 0, n);
    }
    
    template<class F>
    int findFirst(int p, int l, int r, int x, int y, F &&pred) {
        if (l >= y || r <= x) {
            return -1;
        }
        if (l >= x && r <= y && !pred(info[p])) {
            return -1;
        }
        if (r - l == 1) {
            return l;
        }
        int m = (l + r) / 2;
        push(p);
        int res = findFirst(2 * p, l, m, x, y, pred);
        if (res == -1) {
            res = findFirst(2 * p + 1, m, r, x, y, pred);
        }
        return res;
    }
    template<class F>
    int findFirst(int l, int r, F &&pred) {
        return findFirst(1, 0, n, l, r, pred);
    }
    template<class F>
    int findLast(int p, int l, int r, int x, int y, F &&pred) {
        if (l >= y || r <= x) {
            return -1;
        }
        if (l >= x && r <= y && !pred(info[p])) {
            return -1;
        }
        if (r - l == 1) {
            return l;
        }
        int m = (l + r) / 2;
        push(p);
        int res = findLast(2 * p + 1, m, r, x, y, pred);
        if (res == -1) {
            res = findLast(2 * p, l, m, x, y, pred);
        }
        return res;
    }
    template<class F>
    int findLast(int l, int r, F &&pred) {
        return findLast(1, 0, n, l, r, pred);
    }
    
    void maintainL(int p, int l, int r, int pre) {
        if (info[p].difl > 0 && info[p].maxlowl < pre) {
            return;
        }
        if (r - l == 1) {
            info[p].max = info[p].maxlowl;
            info[p].maxl = info[p].maxr = l;
            info[p].maxlowl = info[p].maxlowr = -inf;
            return;
        }
        int m = (l + r) / 2;
        push(p);
        maintainL(2 * p, l, m, pre);
        pre = std::max(pre, info[2 * p].max);
        maintainL(2 * p + 1, m, r, pre);
        pull(p);
    }
    void maintainL() {
        maintainL(1, 0, n, -1);
    }
    void maintainR(int p, int l, int r, int suf) {
        if (info[p].difr > 0 && info[p].maxlowr < suf) {
            return;
        }
        if (r - l == 1) {
            info[p].max = info[p].maxlowl;
            info[p].maxl = info[p].maxr = l;
            info[p].maxlowl = info[p].maxlowr = -inf;
            return;
        }
        int m = (l + r) / 2;
        push(p);
        maintainR(2 * p + 1, m, r, suf);
        suf = std::max(suf, info[2 * p + 1].max);
        maintainR(2 * p, l, m, suf);
        pull(p);
    }
    void maintainR() {
        maintainR(1, 0, n, -1);
    }
};

struct Tag {
    int x = 0;
    void apply(const Tag &t) & {
        x += t.x;
    }
};

struct Info {
    int x = -inf;
    void apply(const Tag &t) & {
        x += t.x;
    }
};

Info operator+(const Info &a, const Info &b) {
    return {std::max(a.x, b.x)};
}


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

    vector<int> v(n);
    for (auto &x : v) x = read();

    vector<int> a(n), rka(n);
    for (int i = 0; i < n; i++) {
        int x = read() - 1;
        a[i] = x, rka[x] = i;
    }

    vector<int> b(n), rkb(n);
    for (int i = 0; i < n; i++) {
        int x = read() - 1;
        b[i] = x, rkb[x] = i;
    }

    LazySegmentTree<Info, Tag> seg(n + 1);
    seg.modify(0, {0});

    for (int i = 0; i < n; i++) {
        int x = rkb[a[i]];

        auto t = seg.rangeQuery(0, x + 1);
        seg.modify(x + 1, t);

        seg.rangeApply(0, x + 1, {v[a[i]]});
    }

    auto [ans] = seg.rangeQuery(0, n + 1);
    cout << ans << '\n';
}

B - Grid Counting

翻译一下会发现限制很简单，dp 一下即可

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

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

    Z ans = 1;

    int len = -n;
    for (int i = n - 1; i >= 0; i--) {
        len += 2;
        if (len <= 0) {
            if (a[i]) {
                cout << "0\n";
                return;
            }
        } else {
            ans *= comb.binom(len, a[i]);
        }
        len -= a[i];
    }

    if (len != 0) ans = 0;
    cout << ans << '\n';
}

A - Incremental Path

直接模拟

void solve() {
    int n = read(), m = read();

    string s; cin >> s;
    vector<int> a(m);
    for (auto &x : a) x = read();

    auto b = a;

    int i = 0, x = 1;
    for (auto c : s) {
        if (c == 'A') {
            x++;
            b.eb(x);
        } else {
            while (i < m and a[i] <= x) {
                i++;
            }

            x++;

            while (i < m and a[i] == x) {
                x++;
                i++;
            }
            b.eb(x);

            x++;
            while (i < m and a[i] == x) {
                x++;
                i++;
            }
        }
    }

    ranges::sort(b);
    b.erase(unique(b.begin(), b.end()), b.end());
    cout << b.size() << '\n';
    for (auto x : b) {
        cout << x << " \n"[x == b.back()];
    }
}