📖 题目大意

棋盘是 2 行 n 列的矩阵，每格有一个分数 a[i][j]。游戏规则： Mandy 从左上角 (0,0) 开始，brz 从右下角 (1,n-1) 开始。 一开始，两人各自获取自己位置上的分数，然后该格分数消失。 Mandy 先手，每次可向上下左右移动（不能出界、不能移动到分数为 0 的格子），或者选择不动。 移动到的格子，获得该格分数，分数消失。 轮到对方，直到双方都无法移动游戏结束。 谁得分高谁赢，如果得分相同则平局。

💡 解题思路

• 核心算法：前缀和 + 遍历所有转折列的博弈策略。
• 步骤一：计算上行和下行的前缀和 preUp 和 preDown，快速求任意区间和。
• 步骤二：遍历每列 i 作为 Mandy 转折点：
  • Mandy 得分 = 上排 1..i + 下排 1..i-1
  • brZ 得分 = 上排 i+1..n + 下排 i..n
  • 根据大小标记胜负或平局
• 步骤三：处理平局或交错列，选中间列判断最终胜者。
• 步骤四：输出结果（Mandy / brz / draw）。
• 复杂度分析：时间 O(T * n)，空间 O(n)（前缀和数组）。

⚙️ AC 代码

#include <bits/stdc++.h>
using namespace std;

using int64 = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        vector<int64> up(n + 1), down(n + 1);
        for (int i = 1; i <= n; i++) cin >> up[i];
        for (int i = 1; i <= n; i++) cin >> down[i];

        vector<int64> preUp(n + 1, 0), preDown(n + 1, 0);
        for (int i = 1; i <= n; i++) {
            preUp[i] = preUp[i - 1] + up[i];
            preDown[i] = preDown[i - 1] + down[i];
        }

        bool mandyWin = false, brzWin = false, draw = false;

        for (int i = 1; i <= n; i++) {
            int64 mandy = preUp[i] + preDown[i - 1];
            int64 brz   = (preUp[n] - preUp[i]) + (preDown[n] - preDown[i - 1]);

            if (mandy > brz) mandyWin = true;
            else if (mandy < brz) brzWin = true;
            else draw = true;
        }

        if (draw) cout << "draw\n";
        else if (mandyWin && !brzWin) cout << "Mandy\n";
        else if (brzWin && !mandyWin) cout << "brz\n";
        else {
            int i1 = (n + 1) / 2;
            int i2 = (n + 2) / 2;

            auto calc = [&](int i) {
                int64 mandy = preUp[i] + preDown[i - 1];
                int64 brz   = (preUp[n] - preUp[i]) + (preDown[n] - preDown[i - 1]);
                if (mandy > brz) return 1;
                if (mandy < brz) return -1;
                return 0;
            };

            int r1 = calc(i1), r2 = calc(i2);
            int r = max(r1, r2);
            if (r > 0) cout << "Mandy\n";
            else if (r < 0) cout << "brz\n";
            else cout << "draw\n";
        }
    }

    return 0;
}

📚 今日总结

📚 今日总结

• 核心算法：前缀和 + 遍历所有转折列判断博弈结果。
• 易错点：不要贪心拿最大数字，注意前缀和下标一致性，处理交错列避免平局判断错误。
• C++ 语法
  • vector<int64> arr(n+1);：创建 1-based 动态数组，方便计算前缀和。
  • auto lambda = [<capture>](int i){…};：lambda 表达式，可捕获外部变量。
  • prefix[i] = prefix[i-1] + arr[i];：前缀和区间计算。
  • for(int i=1;i<=n;i++)：遍历列，注意循环边界。
• 复杂度：时间 O(T * n)，空间 O(n)。

---