#734 (Div. 3) 1551. D1,2. Domino (思维,构造easy/hard version)

LINK

题意

现在必须恰好放下 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";
		} 
	}
}
上一篇:[LeetCode] 895. Maximum Frequency Stack_Hard tag: stack


下一篇:【CF802O】April Fools' Problem (hard)