题解：AT_agc026_f [AGC026F] Manju Game

SevenElevenThirteen · 2025-09-08 23:17:30 · 题解

没有独立切的妙妙题！感觉是普及组，但是它的位置不太普及（符合 AGC 刻板印象（？

下文中，先 / 后手指人，先 / 后行指具体的先后次序。我的 \sout{\LaTeX} 水平显著提高（

自然地，把奇数位和偶数位上的数分开，分别记作 o, e。

• n$ 是偶数：$o, e, o, e, \dots, o, e, o, e

  先手取最左（右）边的数，得分 \sum o（\sum e），因此得分 \geqslant \max\{ \sum o, \sum e \}.

  如果先手从中间取，不妨取到 o。此时序列分成两段，左侧有偶数个，右侧有奇数个。后手先取 o 左边的数，这样把左侧取完，并且在右侧变为先行。再取最右端，这样后手取走所有的 e。记先手红色，后手蓝色。

  \begin{matrix} &\underbrace{\colorbox{white}{o} \quad \colorbox{white}{e}}_{\text{even}} \quad &\mathop{\colorbox{red}{o}}\limits^{\downarrow} \quad &\underbrace{\colorbox{white}{e} \quad \colorbox{white}{o} \quad \colorbox{white}{e} \quad \colorbox{white}{o} \quad \colorbox{white}{e}}_{\text{odd}} \\ &\underbrace{\colorbox{white}{o} \quad \mathop{\colorbox{blue}{e}}\limits^{\downarrow}}_{\text{even}} \quad &\colorbox{red}{o} \quad &\underbrace{\colorbox{white}{e} \quad \colorbox{white}{o} \quad \colorbox{white}{e} \quad \colorbox{white}{o} \quad \colorbox{white}{e}}_{\text{odd}} \\ &\underbrace{\colorbox{red}{o} \quad \colorbox{blue}{e}}_{\text{even}} \quad &\colorbox{red}{o} \quad &\underbrace{\colorbox{white}{e} \quad \colorbox{white}{o} \quad \colorbox{white}{e} \quad \colorbox{white}{o} \quad \mathop{\colorbox{blue}{e}}\limits^{\downarrow}}_{\text{odd}} \\ &\underbrace{\colorbox{red}{o} \quad \colorbox{blue}{e}}_{\text{even}} \quad &\colorbox{red}{o} \quad &\underbrace{\colorbox{blue}{e} \quad \colorbox{red}{o} \quad \colorbox{blue}{e} \quad \colorbox{red}{o} \quad \colorbox{blue}{e}}_{\text{odd}} \end{matrix}

  同理，若先手取到中间的 e，后手可以取走所有 o。

  因此，若先手在中间取，后手得分总 \geqslant \min\{ \sum o, \sum e \}，故先手得分 \leqslant sum - \min\{ \sum o, \sum e \} = \max\{ \sum o, \sum e \}。

  综上，最终必然先手取 \max，后手取 \min。

• n$ 是奇数：$o, e, o, e, \dots, o, e, o, e, o

  先手取两端，得分都是 \sum o。如果取中间？

  • 取 o

    \underbrace{o \quad e \quad o \quad e}_{\text{even}} \quad \mathop{\colorbox{red}{o}}\limits^{\downarrow} \quad \underbrace{e \quad o \quad e \quad o}_{\text{even}}

    左右两段均为偶数，因此左右均为后手先行。偶数的子问题上面已经讨论过，每一段先手所得为 \min\{ \sum o, \sum e \} \leqslant \sum o，因此先手总得分 \leqslant \sum o。

    不优于先手直接取端点，故必不会在中间取 o。

  • 取 e

    \underbrace{o \quad e \quad o}_{\text{odd}} \quad \mathop{\colorbox{red}{e}}\limits^{\downarrow} \quad \underbrace{o \quad e \quad o \quad e \quad o}_{\text{odd}}

    左右两端均为奇数。后手选一段取走其中的 \sum o，留下 \sum e 给先手。另一段仍为先手先行，递归为子问题，直至先手通过取端点拿走 \sum o 结束游戏。整个过程形成一棵树：

    \begin{matrix} \mathop{\boxed{\quad \quad \quad \quad \quad}}\limits_{\downarrow} &\color{red}{e} &\mathop{\boxed{\quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad}}\limits_{\downarrow} \\ {\color{blue}\sum o} \quad {\color{red}\sum e} &\quad &{\begin{matrix} \mathop{\boxed{\quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad}}\limits_{\downarrow} &\color{red}{e} &\mathop{\boxed{\quad \quad \quad \quad}}\limits_{\downarrow} \\ {\begin{matrix} \mathop{\boxed{\quad \quad \quad \quad}}\limits_{\downarrow} &\color{red}e &\mathop{\boxed{\quad \quad \quad \quad}}\limits_{\downarrow} \\ {\color{blue}\sum o} \quad {\color{red}\sum e} &\quad &\underbrace{{\color{red}\sum o} \quad {\color{blue}\sum e}}_{\text{终止节点}} \end{matrix}} &\quad &{{\color{blue}\sum o} \quad {\color{red}\sum e}} \end{matrix}} \end{matrix}

    不妨认为先手初始得分 \sum e。先手将序列切成若干段，最终取一段得到另外的 \sum o - \sum e，最大化得分。记 \delta = \sum o - \sum e。如果先手要获得 \delta 的加分，必须保证每个叶子节点 \sum o - \sum e \geqslant \delta，因为后手必然会尽力将终止节点向 < \delta 的方向移动。若所有叶子均满足条件，则后手是否遵循划分都无影响，因为先手可以将未选择的那一侧作为终止，易知最终答案不变。

    不难看出 \delta 可二分。设 dp_i 表示 1 \sim i 能否划分，显然 i 为奇数。其为真当且仅当有 dp_j = \text{true} \; \land \; w(j + 2, i) \geqslant \delta。因此，对所有 dp_j = \text{true} 的位置，维护最小前缀和 s_{j + 1}。这样甚至不用显式存储 dp。

  取两端也是一种取中间，不过把全局当叶子。

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;

// #define Debug
// #define LOCAL
// #define TestCases

constexpr int N = 3e5;

int n;
int a[N + 5];

int Odd, Even;
int s[N + 5];

bool check(int delta)
{
    int Min = 0;
    for (int i = 1; i <= n; i += 2)
    {
        if (s[i] - Min >= delta)//dp[i] = true
            Min = min(Min, s[i + 1]);//dp[i] <- dp[j], sum(i, j + 2) >= delta -> s[i] - s[j + 1] >= delta
    }
    return s[n] - Min >= delta;//dp[n]
}

void solve()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];

        if (i & 1)
            Odd += a[i], s[i] = s[i - 1] + a[i];
        else
            Even += a[i], s[i] = s[i - 1] - a[i];
    }

    if (!(n & 1))//even
    {
        cout << max(Odd, Even) << " " << min(Odd, Even) << '\n';
        return ;
    }

    int l = 0, r = Odd + Even, delta = 0;
    while (l <= r)
    {
        int mid = (l + r) >> 1;
        if (check(mid))
        {
            delta = mid;
            l = mid + 1;
        }
        else
            r = mid - 1;
    }

    cout << Even + delta << " " << Odd - delta << '\n';
    return ;
}

int main()
{
    #ifdef LOCAL
    freopen("data.in", "r", stdin);
    freopen("mycode.out", "w", stdout);
    #endif

    ios :: sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);

    int T = 1;

    #ifdef TestCases
    cin >> T;
    #endif

    while (T--)
        solve();
    return 0;
}