HDU 4925 Apple Tree 重複題目分析：棋盤染色貪心策略

題目重述與核心策略

本文為 HDU 4925《Apple Tree》的另一份解題報告，核心思路與前文一致：採用黑白棋盤染色（交錯佈局）使每棵蘋果樹的四鄰格盡可能為施肥格，從而最大化翻倍效果。兩種染色方案（奇數行從第 1 列或第 2 列開始種樹）取最大值。

實作細節差異

本版本使用 g[i][j] = 1/-1 表示施肥/種樹，deal() 函數計算單棵樹產出：

int deal(int x, int y) {
    int sum = 1;
    if (g[x][y-1] == 1) sum <<= 1;
    if (g[x][y+1] == 1) sum <<= 1;
    if (g[x-1][y] == 1) sum <<= 1;
    if (g[x+1][y] == 1) sum <<= 1;
    return sum;
}

佈局邏輯針對 M 奇偶分別處理：M 為奇數時逐行交替；M 為偶數時每行結束額外翻轉 flag 以確保相鄰行錯位。

完整代碼

#include <cstdio>
#include <cstring>
using namespace std;
const int MAXN = 105;
int g[MAXN][MAXN];

int deal(int x, int y) {
    int sum = 1;
    if (g[x][y-1] == 1) sum <<= 1;
    if (g[x][y+1] == 1) sum <<= 1;
    if (g[x-1][y] == 1) sum <<= 1;
    if (g[x+1][y] == 1) sum <<= 1;
    return sum;
}

int main() {
    int cas, n, m;
    scanf("%d", &cas);
    while (cas--) {
        scanf("%d%d", &n, &m);
        if (n == 1 && m == 1) { puts("1"); continue; }
        memset(g, 0, sizeof(g));
        int flag = 1;
        if (m % 2) {
            for (int i = 1; i <= n; ++i)
                for (int j = 1; j <= m; ++j)
                    g[i][j] = flag, flag = -flag;
        } else {
            for (int i = 1; i <= n; ++i) {
                for (int j = 1; j <= m; ++j)
                    g[i][j] = flag, flag = -flag;
                flag = -flag;
            }
        }
        long long ans = 0;
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= m; ++j)
                if (g[i][j] == -1) ans += deal(i, j);
        printf("%lld\n", ans);
    }
    return 0;
}

關鍵點總結

• 特判 1×1 情況輸出 1
• 位運算 sum <<= 1 實現乘 2，效率更高
• 兩種 parity 佈局邏輯覆蓋所有 N, M 組合
• 時間 O(T·N·M)，空間 O(N·M)，極易通過