题解 | #Tokitsukaze and Colorful Chessboard#

1. 数学模型：二分图视角

棋盘是一个经典的二分图。我们可以根据坐标和的奇偶性将所有格子分为两组：

• 组 ：所有满足 为偶数的格子，数量为 。
• 组 ：所有满足 为奇数的格子，数量为 。

二分图的性质决定了：同组内的任意两个格子都不相邻。 要使 个红色棋子和 个蓝色棋子满足互不相邻且位置不重叠，只需满足以下条件之一：

• 且
• 且

通过归纳证明，这等价于：

由于 ，对于整数 ，上述条件完全等价于：

• （整数除法）
• 

2. 最优化策略：二分查找

由于棋盘边长 越大，能容纳的棋子越多，答案具有明显的单调性。

• 搜索空间： 的最小可能值为 1（当 时），最大可能值约为 。考虑到 ，线性扫描会超时。
• 计算范式：使用二分查找在 范围内寻找满足条件的最小 。