题意
现在必须恰好放下 k k k个水平的 1 ∗ 2 1*2 1∗2的长方块,和任意 2 ∗ 1 2*1 2∗1的垂直长方块
是否能填满 n ∗ m n*m n∗m的网格?
现特判掉 k = 0 k=0 k=0的情况
考虑当 n n n为奇数,那么填充完 k k k个水平方块后,所有列必须是偶数
也就是每一列必须被填充奇数个格子
Ⅰ.当 m m m为奇数无解,因为每次只能改变 2 2 2列的奇偶性,这样怎么填充都有一列和其他奇偶性质不同
Ⅱ.否则,我们先把第一行填满,也就是花费 m / 2 m/2 m/2个长方体,这样每列都是偶数了
于是余下的长方体 k − m / 2 k-m/2 k−m/2必须是偶数,因为每列必须填充偶数次才行
这样构造即可
考虑当 n n n为偶数
也就是每一列必须填充偶数个格子
Ⅰ.这种情况下,先计算 x = n ∗ ( m / 2 ) x=n*(m/2) x=n∗(m/2),最多能填充 x x x个水平长方体,和 k k k比一下看是否满足
Ⅱ.满足的话,考虑到每列都是偶数,那么 k k k必须为偶数,否则最后会出现两列奇数
Ⅲ.都满足的话就开始构造,也就是一直给
1
,
2
1,2
1,2列放
2
2
2个水平长方体直到放不下
再给
3
,
4
3,4
3,4列放
2
2
2个长方体…以此类推
这里只贴以下 D 1 D1 D1怎么判断,具体怎么构造上面大概已经说了
不放代码的原因是赛中根本没想这么多,直接模拟玄学过去的
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2009;
int t,n,m,k,a[maxn];
int main()
{
cin >> t;
while( t-- )
{
cin >> n >> m >> k;
if( k==0 )
{
if( n&1 ) cout << "NO\n";
else cout << "YES\n";
}
else if( n&1 )//奇数行,每列都要放奇数个
{
if( m%2==0 && m/2<=k && (k-m/2)%2==0 ) cout << "YES\n";
else cout << "NO\n";
}
else//偶数行,所以每列需要放偶数个
{
int x = n*(m/2);
if( x>=k && k%2==0 ) cout << "YES\n";
else cout << "NO\n";
}
}
}