Codeforces 549C 是一道經典的「燒毀城市」博弈問題。Stannis 和 Daenerys 輪流燒毀一座城市，遊戲結束時恰好剩下 k 座城市。若倖存人口總和為偶數，Daenerys 勝；奇數則 Stannis 勝。Stannis 先手。給定 n 座城市的人口 a₁…aₙ，判斷誰有必勝策略。
odd = 奇數城市數，even = 偶數城市數。m = n - k 座城市。stannis_moves = (m + 1) / 2、daenerys_moves = m / 2 次行動（Stannis 先手多一次當 m 為奇）。遊戲本質是雙方搶奪「最後剩餘的奇數城市個數奇偶性」。關鍵在於：若某方能強迫對手在關鍵時刻無牌可打（只能燒特定奇偶性），即可掌控結局。
根據 k 的奇偶性與 m 的奇偶性（即誰走最後一步），分四大類：
| 情況 | 最後一步 | 關鍵判斷邏輯 |
|---|---|---|
| k 為奇 | Stannis 走最後一步 (m 奇) | Daenerys 能否在她的回合燒光所有奇數城市？ 若 daenerys_moves >= odd → Daenerys 勝（剩全偶）否則 Stannis 勝 |
| Daenerys 走最後一步 (m 偶) | Stannis 能否燒光所有偶數城市？ 需考慮 Daenerys 可能干擾： other = max(0, daenerys_moves - (odd - 1) - 1)（Daenerys 保留 1 奇、燒盡偶後的剩餘步數）若 stannis_moves + other >= even → Stannis 勝（能燒光偶）否則 Daenerys 勝 |
|
| k 為偶 | Stannis 走最後一步 (m 奇) | 雙方都有機會燒光對方關鍵棋子，需檢查兩種策略： 1. Stannis 燒光偶數： other = max(0, stannis_moves - (even - 1) - 1)，若 daenerys_moves + other >= odd 則 Daenerys 可反制2. Stannis 燒光奇數：同理 若存在任一種策略讓 Daenerys 贏 → Daenerys 勝，否則 Stannis 勝 |
| Daenerys 走最後一步 (m 偶) | Daenerys 總能保證剩餘奇數城市為偶個 → Daenerys 必勝 |
string solve(int n, int k, int odd, int even) {
int m = n - k;
int s_move = (m + 1) / 2; // Stannis 步數
int d_move = m / 2; // Daenerys 步數
if (k % 2 == 1) { // 最終剩奇數個城市
if (m % 2 == 1) { // Stannis 最後一步
if (d_move >= odd) return "Daenerys";
return "Stannis";
} else { // Daenerys 最後一步
int other = max(0, d_move - (odd - 1) - 1);
if (s_move + other >= even) return "Stannis";
return "Daenerys";
}
} else { // 最終剩偶數個城市
if (m % 2 == 1) { // Stannis 最後一步
bool flag = false;
int other = max(0, s_move - (even - 1) - 1);
if (d_move + other >= odd) flag = true;
other = max(0, s_move - (odd - 1) - 1);
if (d_move + other >= even) flag = true;
return flag ? "Daenerys" : "Stannis";
} else { // Daenerys 最後一步
return "Daenerys";
}
}
}3 1 / 1 2 1 → odd=2, even=1, m=2, k=1(奇), m偶 → Daenerys 最後一步，other=max(0,1-(2-1)-1)=0，s_move+other=1+0=1 < even(1)? 否，相等 → Stannis 勝 ✓3 1 / 2 2 1 → odd=1, even=2 → other=max(0,1-(1-1)-1)=0，1+0 < 2 → Daenerys 勝 ✓6 3 / 5 20 12 7 14 101 → odd=3, even=3, m=3, k=3(奇), m奇 → Stannis 最後一步，d_move=1 < odd(3) → Stannis 勝 ✓O(n) 統計奇偶，判斷 O(1)。O(1)。本題核心在於將複雜博弈抽象為「奇偶棋子搶奪」，通過枚舉誰走最後一步、誰先耗盡關鍵資源，構建完整決策樹。掌握「先手/後手、奇/偶城市數、剩餘步數」三要素的組合關係，即可秒殺同類奇偶博弈問題。
