题意:
给出你n * m的方阵 , 然后让你放置1 * 2的小矩形,可以水平放置,也可以竖直放置,保证n*m是偶数.问你是否可以放置k个水平的,剩下的竖直放置.
思路:
首先我们看题意,从中我们得到应该是模拟的题型,我们想把特殊的边界值找出来,
- k==0的时候:
- n是奇数那么肯定必须要有水平的,不然这个奇数无法处理
- n是偶数那么我们直接竖直放置即可,不需要水平放置.
- k=n*m/2也就是整个方阵都是水平的.
- m是奇数那么肯定必须要有竖直方的,不然奇数无法处理
- m是偶数那么我们直接水平放置即可,不需要竖直放置.
- k处于0~n*m/2之间
- 先看n与m都是偶数的情况,这种情况最好分析,就是尽量将2个12的转成1个22的这样剩下的,行和列都还是偶数,都还可以竖直放置或者水平放置,所以我们只需要满足,k是偶数就满足条件.
- n是奇数,m是偶数,我们看到m是偶数那么可以想到用水平的将1行填上,那么n就边成了偶数,就转化成了上面那种情况,而如果1行填不满,肯定有奇数行的,肯定无法满足条件.
- m是奇数,n是偶数,这个样子我们就无法像2那样转化了,但是换种思路题中让求k个水平,那么也就是让我们求(n*m/2-k)个竖直,我们先把第一列填上,就变成了n和m都是偶数,那么就转化成第一种情况了,我们直接判断剩下的竖直是不是偶数即可,如果第一列填不满肯定有奇数列,肯定无法满足条件.(这个3是通过刚写2的时候推出来的,后面是赛时的想法)敢看了一下,其实赛时想得再看一下就是我上面写的,
然后D2是让你把符合条件的一种画出来.
代码:
void solve()
{
scanf("%lld%lld%lld", &n, &m, &k);
if((k == 0 && n %2==0) || (k * 2 == n * m && m %2== 0))
{
puts("Yes");
return ;
}
if((k==0&&n%2==1)||(k*2==n*m&&m%2==1)) {
puts("No");
return ;
}
if(n == 1 || m == 1)
{
puts("No");
return;
}
if(n % 2 == 1)
{
ll num = m / 2;
if(k<num) puts("No");
else {
n--;
k-=num;
if(k%2) puts("No");
else puts("Yes");
}
}
else if(m%2==1)
{
ll sum=n*m/2;
ll num=n/2;
ll res=sum-num;
if(k%2||res<k) puts("No");
else puts("Yes");
}else {
if(k%2) puts("No");
else puts("Yes");
}
}