Codeforces 264C Gargari and Bishops 找規律題解

Codeforces Round #264 Div.2 C 題解：Gargari and Bishops

題目大意： n×n 棋盤，每格有權值。放兩個主教，要求它們攻擊的格子不重疊（即一個在黑格、一個在白格），最大化兩主教攻擊格子權值之和。輸出最大值及兩主教位置。

關鍵觀察

• 主教攻擊範圍為其所在的兩條對角線（主對角線 i-j 恆定，副對角線 i+j 恆定）。
• 兩主教攻擊格子不重疊 ⇔ 它們顏色不同（一個黑格、一個白格），即 (x+y) % 2 不同。
• 因此可分別預處理黑格、白格每個位置的攻擊總和，取各自最大值即可。

算法步驟

1. 輸入 n 及棋盤權值 g[i][j]。
2. 預處理兩個對角線陣列：
   • zhu[i - j + n] 存主對角線和（偏移 n 避免負下標）。
   • fu[i + j] 存副對角線和。
3. 遍歷所有格子 (i,j)：
   • 計算 sum = zhu[i-j+n] + fu[i+j] - g[i][j]（減去自身重複計算）。
   • 根據 (i+j)%2 更新黑格最大值 b 或白格最大值 w，記錄位置。
4. 輸出 b + w 及兩主教座標（1-based）。

參考代碼

#include <cstdio>
#include <cstring>
const int N = 2005;
typedef long long ll;
int n;
ll g[N][N], zhu[N + N], fu[N + N];
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            scanf("%lld", &g[i][j]);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            zhu[i - j + n] += g[i][j];
            fu[i + j] += g[i][j];
        }
    }
    ll b = -1, w = -1;
    int bx, by, wx, wy;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            ll sum = zhu[i - j + n] + fu[i + j] - g[i][j];
            if ((i + j) % 2 == 0) {
                if (b < sum) { b = sum; bx = i + 1; by = j + 1; }
            } else {
                if (w < sum) { w = sum; wx = i + 1; wy = j + 1; }
            }
        }
    }
    printf("%lld\n", b + w);
    printf("%d %d %d %d\n", bx, by, wx, wy);
    return 0;
}

複雜度分析

時間 O(n²)，空間 O(n)。n ≤ 2000，完全滿足限制。

常見陷阱

• 忘記減去 g[i][j] 導致雙計自身權值。
• 未使用 long long 存儲對角線和與答案（權值上限 10⁹，n=2000 時和可達 4×10¹²）。
• 對角線下標越界：主對角線範圍 -(n-1) ~ (n-1)，偏移 n 後下標 1 ~ 2n-1，開陣列 2n+5 即可。