AT_arc171_a 题解

yyrwlj · 2024-02-05 17:35:04 · 题解

只切了这道题，刚开始表现分直接 1949，实际分是三位数。

题意简述

有一个 n \times n 的棋盘，要在上面放 a 个车和 b 个卒，车会攻击同行同列的其它棋子，卒会攻击同一列的下一行的棋子。

是否存在一种让它们互不攻击的方案。

思路

显然每行每列最多只能放一个车，那么如果 a > n 就直接无解了。

否则放完 a 个车后，还剩 n-a 行。卒不会攻击同一行的棋子，所以每行都可以放满 n-a 个卒。

考虑如何最大化能使用的行数，不能让两个行挨在一起，所以让车隔一行放一个。

当 a < \lfloor \frac{n}{2} \rfloor，光隔一行放一个还会有剩下的。出现这种情况就正常隔着放就行，除了车隔出来的 a 行以外，最多还能放 \lceil \frac{n-2a}{2} \rceil 行。

最后看还能放的格子数和卒的数量的大小关系即可。

Code

if (a > n || a == n && b)
    puts("No");
int col = n - a, row = col;
if (a < n / 2)
    row = a + ((n - a) * 2 + 1) / 2;
if (col * row < b)
    puts("No");
else
    puts("Yes");