CF493D Vasya and Chess 题解

myster1ous · 2022-03-14 15:01:18 · 题解

题目传送门

题目大意

在 n \times n 的棋盘上，有白后和黑后（国际象棋）分别在 (1, 1) 和 (1, n)，其余全是中立的兵，白方先手，问谁能必胜 ?

解题思路

结论

若 n 为偶数，先手必胜。若 n 为奇数，后手必胜。

证明

case 1： n 为奇数

无论白怎么走，黑都可以模仿白，比如白走到 (1, 2)，黑就走到 (1, n - 1)

如果白走到了最中间的那一列(即第 \frac{n + 1}{2} 列)时，由于黑一直是白的镜像，所以黑一定在白的那一列，所以黑一定能吃掉白。

case 2: n 为偶数

这个很简单，只要白先走到 (1, 2)，然后就跟之前一模一样了，由于是镜像，所以白不会在走到第 1 列了!（最后一行不影响）

所以当 n 为偶数的时候，白只要走到 (1, 2) 就可以必胜，而且这样还满足题目中 "如果有多解，请输出 r 最小的解，如果还有多解，请输出 c 最小的解" 的要求。

代码

说了这么多了，其实核心代码就一行。

cout << (n & 1 ? "black" : "white\n1 2");

AC 代码

#include <iostream>
using namespace std;
int n;
int main() {
    cin >> n;
    cout << (n & 1 ? "black" : "white\n1 2"); // 核心判断
    return 0;
}