练习赛 Round 153 题解

A 字符插入

知识点：子序列计数、贡献、贪心

插入的字符固定为 $\texttt{6}$ ，原串中已有的 $\texttt{2026}$ 数量与插入位置无关，因此只需最大化新产生的 $\texttt{2026}$ 数量。若把 $\texttt{6}$ 插在前 $i$ 个字符之后，那么新增贡献正好等于前缀 $s_1\sim s_i$ 中子序列 $\texttt{202}$ 的个数。

随着 $i$ 从左到右增大，前缀中的 $\texttt{202}$ 数量不会减少，因此最优位置一定可以取 $i=|s|$ ，即插在最后。

时间复杂度 $\mathcal{O}(1)$ 。

void solve() {
    string s;
    cin >> s;
    cout << s.size() << endl;
}

B 前缀和

知识点：贡献拆分、前缀和、贪心

原序列中 $a_j$ 对所有前缀和总和的贡献系数为 $n-j+1$ 。若删除第 $i$ 个数：

$i$ 前面的每个数贡献系数都会少 $1$ ，总损失为 $\sum_{j<i} a_j$ ；
$a_i$ 本身被删除，损失为 $(n-i+1)a_i$ ；
$i$ 后面的数虽然位置前移，但贡献系数不变。

因此删除第 $i$ 个位置后的答案等于原答案减去

\sum_{j<i} a_j+(n-i+1)a_i

要让剩余前缀和总和最大，只需找到上式最小的位置。扫描时维护前缀和即可。

时间复杂度 $\mathcal{O}(n)$ 。

void solve() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) cin >> a[i];
    int S = 0, mn = INF, loc = -1;
    for (int i = 0; i < n; ++i) {
        S += a[i];
        if (S + (n - i - 1) * a[i] < mn) mn = S + (n - i - 1) * a[i], loc = i;
    }
    cout << loc + 1 << endl;
}

C 博弈

知识点：奇偶性、最大子段和、分类讨论

一次操作中，第 $l,l+2,l+4,\dots$ 个被选中的位置会改变奇偶性，其他位置奇偶性不变。也就是说，Alice 实际上可以在原数组下标奇偶性相同的一类位置中，选择一段连续子段并翻转这些位置的奇偶性。

设当前奇数个数为 $x$ 。对每个会被翻转的位置，若原来是偶数，则奇数个数增加 $1$ ；若原来是奇数，则奇数个数减少 $1$ 。于是把同奇偶下标上的元素看成一个序列，偶数记为 $+1$ ，奇数记为 $-1$ ，问题变为在两类下标中取最大子段和，得到最大增量 $g$ 。

若 $2(x+g)>n$ ，则 $\texttt{Alice}$ 可以使奇数严格多于偶数，输出 $\texttt{Alice}$ ；否则输出 $\texttt{Alice}$ 。不操作相当于增量为 $0$ ，最大子段和取非负即可。

时间复杂度 $\mathcal{O}(n)$ 。

void solve() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) cin >> a[i];
    int x = 0;
    for (int i = 0; i < n; ++i) x += a[i] & 1;
    auto ssolve = [&](int st) {
        int cur = 0, mx = 0;
        for (int i = st; i < n; i += 2) {
            cur += (a[i] & 1) ? -1 : 1;
            cur = max(cur, 0LL);
            mx = max(mx, cur);
        }
        return mx;
    };
    if (2 * (x + max(ssolve(0), ssolve(1))) > n)
        cout << "Alice" << endl;
    else
        cout << "Bob" << endl;
}

D 异或和I

知识点：动态规划、前缀异或、计数 DP

记前缀异或为 $pre_i$ 。若最后一段异或和为 $x$ ，上一段结束位置的前缀异或必须是 $pre_i\oplus x$ ；同时为了满足非降，上一段的最后一段异或和必须不超过 $x$ 。

设 $best[p][v]$ 表示：在已经处理过的某个前缀中，前缀异或为 $p$ ，且最后一段异或和不超过 $v$ 时，能得到的最多段数； $ways[p][v]$ 表示达到该段数的方案数。初始空前缀满足 $best[0][v]=0$ 。

处理到当前位置、当前前缀异或为 $pre$ 时，枚举新最后一段的异或和 $x$ ：

elen[x]=best[pre\oplus x][x]+1

这表示接上一段异或和不超过 $x$ 的最优划分。随后对 $elen$ 做前缀最大值及方案数累加，得到“最后一段异或和不超过 $v$ ”的状态，再用当前前缀异或更新 $best[pre][v]$ 。最后 $v$ 取异或值上界即可得到答案。

由于 $a_i\le 3000$ ，所有异或值都小于 $4096$ 。

时间复杂度 $\mathcal{O}(4096n)$ 。

array<int, 4096> best[4096], clen, elen;
array<Z, 4096> ways[4096], ccnt, ecnt;

void solve() {
    int n, _;
    cin >> n >> _;
    Z::setMod(_);
    for (int i = 0; i < 4096; ++i) best[i].fill(-INF), ways[i].fill(0);
    best[0].fill(0), ways[0].fill(1);
    int pre = 0;
    for (int i = 0; i < n; ++i) {
        int a;
        cin >> a;
        pre ^= a;
        elen.fill(-INF), ecnt.fill(0);
        for (int j = 0; j < 4096; ++j) {
            int ps = pre ^ j;
            if (best[ps][j] == -INF) continue;
            elen[j] = best[ps][j] + 1, ecnt[j] = ways[ps][j];
        }

        int mx = -INF;
        Z cnt = 0;
        for (int j = 0; j < 4096; ++j) {
            if (elen[j] > mx)
                mx = elen[j], cnt = ecnt[j];
            else if (elen[j] == mx && mx != -INF)
                cnt += ecnt[j];
            clen[j] = mx, ccnt[j] = cnt;
        }

        for (int j = 0; j < 4096; ++j) {
            if (clen[j] > best[pre][j])
                best[pre][j] = clen[j], ways[pre][j] = ccnt[j];
            else if (clen[j] == best[pre][j])
                ways[pre][j] += ccnt[j];
        }
    }
    cout << clen[4095] << " " << ccnt[4095] << endl;
}

E 异或和II

知识点：Lucas 定理、组合数奇偶性、按位贡献

异或答案可以逐位考虑。某一位为 $1$ 的子序列 OR 值会对答案这一位贡献一次，因此只关心这类子序列数量的奇偶性。

设当前有 $n$ 个数，其中第 $b$ 位为 $0$ 的数有 $z$ 个。长度不超过 $k$ 的非空子序列总数奇偶性记为 $F(n,k)$ ，其中第 $b$ 位 OR 为 $0$ 的子序列只能从这 $z$ 个数中选，数量奇偶性为 $F(z,k)$ 。所以答案第 $b$ 位为

F(n,k)\oplus F(z,k)

利用恒等式

\sum_{i=1}^{k}\binom{n}{i}\equiv \binom{n-1}{k}-1 \pmod 2

再由 Lucas 定理， $\binom{n-1}{k}$ 为奇数当且仅当 $k$ 的每个二进制 $1$ 位都包含在 $n-1$ 中，即 $(k\ \&\ \sim(n-1))=0$ 。因此 $F(n,k)$ 可以 $\mathcal{O}(1)$ 求出。

维护每一位当前为 $1$ 的个数即可支持单点修改。每次询问枚举 $0\sim 30$ 位计算答案。

时间复杂度： $\mathcal{O}(31(n+q))$ 。

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

    vector<int> a(n + 1);
    array<int, 31> cnt{};

    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        for (int j = 0; j < 31; ++j)
            if ((a[i] >> j) & 1) cnt[j]++;
    }

    while (q--) {
        int op;
        cin >> op;
        if (op == 1) {
            int x, y;
            cin >> x >> y;
            int old = a[x];
            if (old == y) continue;

            for (int i = 0; i < 31; ++i) {
                int o = (old >> i) & 1, ne = (y >> i) & 1;
                cnt[i] += ne - o;
            }
            a[x] = y;
        } else {
            int k;
            cin >> k;
            using ull = unsigned long long;
            auto F = [&](ull n, ull k) -> int { return 1 ^ ((k & (~(n - 1))) == 0); };
            int A = F(n, k), ans = 0;
            for (int i = 0; i < 31; ++i)
                if (A ^ F(n - cnt[i], k)) ans |= (1 << i);
            cout << ans << endl;
        }
    }
}

F 下棋

知识点：离线动态连通性、线段树分治、可回滚并查集

固定一种颜色 $c$ 计算其得分。只看所有状态不等于 $c$ 的格子，它们按四联通形成若干连通块；若某个连通块不接触边界，则其中颜色为 $3-c$ 的棋子都会被 $c$ 提走。于是对每个连通块，只需维护两个信息：是否接触边界、其中对方棋子的数量。颜色 $c$ 的得分就是所有“不接触边界”的连通块权值之和。

由于有修改操作，直接在线维护删边很困难。把时间看成 $0\sim q$ ，离线处理每个对象的存在区间：

若某个格子在一段时间内颜色为 $3-c$ ，则在这段时间给该格子所在连通块增加权值 $1$ ；
若相邻两个格子在一段时间内都不等于 $c$ ，则在这段时间加入这条边。

把这些区间加入时间线段树，DFS 线段树时用可回滚并查集维护当前时间段内的连通性和权值和。进入节点时加入该节点上的所有点权和边，离开节点时回滚；到叶子时即可得到该时刻颜色 $c$ 的得分。分别对 $c=1,2$ 做一遍，得到黑白双方在每个时刻的分数并比较输出即可。

时间复杂度 $\mathcal{O}((nm+q)\log q\log(nm))$ 。