题解：AT_agc026_f [AGC026F] Manju Game

一、题意简述

# 游戏规则

1. 两人轮流操作，每次操作选择一个未放置棋子的盒子放入自己的棋子。
2. 相邻限制：必须选择与对手上一次操作相邻的盒子（左右相邻均可）。
3. 特殊情况：
   • 如果没有满足条件的相邻盒子，可以任选一个未放置的盒子。
   • Sugim 的第一次操作可以任选盒子。
4. 游戏进行 $N$ 次后结束，每人获得自己棋子所在盒子的所有馒头。

二、核心观察

# 观察 1：游戏的奇偶性质

• Sugim 第一步选择位置 $p$。
• Sigma 必须选择 $p - 1$ 或 $p + 1$（相邻位置）。
• 之后每步都必须选择与上一步相邻的位置。
• 因此形成的序列必然是连续的，相邻位置的下标奇偶性不同。

• 如果 $N$ 为偶数，必然有一方取所有奇数位置，另一方取所有偶数位置。
• 如果 $N$ 为奇数，会在某处发生"转折"，改变奇偶归属。

# 观察 2：$N$ 为偶数时的简单性

• 设 $\text{odd} = \sum_{i \in \{1, 3, 5, \ldots, N\}} a_i$，$\text{even} = \sum_{i \in \{2, 4, 6, \ldots, N\}} a_i$。
• 由于 Sugim 先手，他可以选择取所有奇数位置或所有偶数位置。
• 最优策略：Sugim 取 $\max(\text{odd}, \text{even})$，Sigma 取 $\min(\text{odd}, \text{even})$。

三、$N$ 为奇数时的解法

# 3.1 问题建模

• $s[i]$ 表示前 $i$ 个位置按照"奇数位给 Sugim，偶数位给 Sigma"分配时，Sugim 相对于 Sigma 的优势值。
• 如果存在"转折点"，则某些偶数位置会被 Sugim 获得，奇数位置被 Sigma 获得。

# 3.2 二分答案

• Sugim 得分 $= \text{even} + \delta$
• Sigma 得分 $= \text{odd} - \delta$

• 如果能达到优势 $\delta$，尝试更大的 $\delta$。
• 否则缩小 $\delta$。

# 3.3 Check 函数详解

bool check(int delta) {
    int mn = 0;  // 记录可用的最小前缀和
    for (int i = 1; i <= n; i += 2) {
        if (s[i] - mn >= delta)  // 如果在位置 i 能达到优势 delta
            mn = min(mn, s[i + 1]);  // 更新最小前缀，允许在 i+1 处"转折"
    }
    return s[n] - mn >= delta;  // 最终检查是否达到 delta
}

1. 状态定义：mn 表示当前可选的最优"起始前缀和"。
2. 转折点选择：
   • 遍历所有奇数位置 $i$。
   • 如果 $s[i] - \text{mn} \geq \delta$，说明从某个"起始点"到 $i$ 能达到优势 $\delta$。
   • 此时可以选择在 $i + 1$ 处"转折"，即改变后续的奇偶归属。
   • 更新 $\text{mn} = \min(\text{mn}, s[i + 1])$，为后续提供更优的起始点。
3. 最终判定：检查 $s[n] - \text{mn} \geq \delta$。

• 游戏中可以有多次"转折"（重新选择不相邻的盒子）。
• 每次转折相当于选择一个新的起始点。
• 贪心地选择最优起始点（前缀和最小）可以最大化后续优势。
• DP 本质：dp[i] = true 表示能在位置 $i$ 达到优势 $\delta$。

四、算法流程

# 完整步骤

1. 输入处理：
   • 读入 $N$ 和数组 $a[]$。
   • 计算 $\text{odd}$ 和 $\text{even}$。
   • 构造差值序列 $s[]$。
2. $N$ 为偶数时：
   • 如果 $N \bmod 2 = 0$，直接输出 $\max(\text{odd}, \text{even})$ 和 $\min(\text{odd}, \text{even})$。
3. $N$ 为奇数时：
   • 二分答案 $\delta \in [0, \text{odd} + \text{even}]$。
   • 对每个 $\delta$，调用 check(delta) 验证可行性。
   • 找到最大的可行 $\delta$。
   • 输出 $\text{even} + \delta$ 和 $\text{odd} - \delta$。

五、代码实现

#include<bits/stdc++.h>

using namespace std;

#define endl '\n'
#define file(x) freopen(#x".in", "r", stdin), freopen(#x".out", "w", stdout)
#define fclose fclose(stdin), fclose(stdout)
#define debug(x) cerr << #x << " = " << (x) << endl

int n;
vector<int> a, s;
int odd, even;

bool check(int delta) {
    int mn = 0;
    for (int i = 1; i <= n; i += 2) {
        if (s[i] - mn >= delta)
            mn = min(mn, s[i + 1]);
    }
    return s[n] - mn >= delta;
}

void solve() {
    cin >> n;
    a.resize(n + 5);
    s.resize(n + 5);
    odd = even = 0;

    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)) {
        cout << max(odd, even) << " " << min(odd, even) << endl;
        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 << endl;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int T = 1;
    //cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

六、复杂度分析

# 时间复杂度

• 构造差值序列：$O(N)$。
• 二分答案：$O(\log S)$，其中 $S = \sum_{i = 1}^{N} a_i \leq N \times 1000 = 3 \times 10^8$。
• 每次 check：$O(N)$。
• 总复杂度：$O(N \log S) \approx O(N \times 28) = O(8.4 \times 10^6)$。

# 空间复杂度

• 数组存储：$O(N)$。
• 总复杂度：$O(N)$。

七、样例详解

# 样例 1

5
20 100 10 1 10

1. $N = 5$（奇数）。
2. $\text{odd} = a[1] + a[3] + a[5] = 20 + 10 + 10 = 40$。
3. $\text{even} = a[2] + a[4] = 100 + 1 = 101$。
4. 差值序列：
   • $s[0] = 0$
   • $s[1] = 0 + 20 = 20$
   • $s[2] = 20 - 100 = -80$
   • $s[3] = -80 + 10 = -70$
   • $s[4] = -70 - 1 = -71$
   • $s[5] = -71 + 10 = -61$
5. 二分过程：
   • 初始：$l = 0, r = 141$
   • 二分得到最大可行 $\delta = 19$
6. 最终答案：
   • Sugim $= 101 + 19 = 120$
   • Sigma $= 40 - 19 = 21$

# 样例 2

6
4 5 1 1 4 5

1. $N = 6$（偶数）。
2. $\text{odd} = 4 + 1 + 4 = 9$。
3. $\text{even} = 5 + 1 + 5 = 11$。
4. 直接输出：$\max(9, 11) = 11$，$\min(9, 11) = 9$。

八、关键要点总结

# 核心技巧

1. 奇偶性质：利用游戏的相邻限制，发现位置的奇偶交替规律。
2. 差值序列：将问题转化为优势值的计算。
3. 二分答案：将最优化问题转化为判定问题。
4. 贪心 DP：通过维护最优前缀和，判断是否能达到目标优势。

# 易错点

1. 边界处理：注意 $s[i + 1]$ 的访问，需要预留足够空间。
2. 奇偶判断：注意区分 $N$ 的奇偶性。
3. 二分边界：$\delta$ 的上界是 $\text{odd} + \text{even}$，不是 $\max(\text{odd}, \text{even})$。

# 推广

• 发现游戏的结构性质（如奇偶性）。
• 用差值序列建模优势关系。
• 二分 + 贪心验证可行性。

九、参考题目难度及算法标签（仅代表个人观点）

• 本题涉及的知识点：博弈论、二分答案、贪心、动态规划。
• 难度评级：省选 / NOI-（个人观点，认为应该是个中紫）。

附录、Updates

• 2025/11/14:
  1. 数学公式规范化
     • 移除公式中的中文，使用数学符号表达条件
     • 集合求和使用集合符号：$\sum_{i \in \{1, 3, 5, \ldots, N\}} a_i$
     • 条件判断使用数学表达式：$i \bmod 2 = 1$ 代替 "if $i$ 为奇数"
  2. 中英文间距
     • 在所有中文与英文、数字、公式之间添加了半角空格
     • 例如："有$N$个盒子" → "有 $N$ 个盒子"
  3. 标点符号统一
     • 全文统一使用中文标点符号
     • 确保每个句子都有句号结尾
  4. 术语规范化
     • "奇数情况" → "$N$ 为奇数时"
     • "偶数情况" → "$N$ 为偶数时"