话不多说,先上代码:
时间复杂度:O(T)
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
接下来,进入正题......
先放个基本框架输入输出:
题目大意:判断能否将任意个1×4,2×3的长方形填满一个X×Y的大长方形。
很容易想到一些结论:
结论一:当X,Y分别是1,4的倍数时,可以填满。
(其实就是任意一边是4的倍数)
结论二:当X,Y分别是2,3的倍数时,可以填满。
然后从面积方面考虑,由于1×4,2×3的长方形面积皆为偶数,因此大长方形
面积必为偶数。
得到结论三:当X×Y为奇数时,不可以填满。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
得到以上三个结论后,就可以更深入地分析了。
我们将1,2,3,4进行组合。
假设X=m+2n,Y=3p+4q(m,n,p,q为非负整数);
红 绿 蓝 黄
红:m×3p,绿:m×4q,蓝:2n×4q,黄:2n×3p;
根据结论1,2,易证明黄,绿,蓝区域都可填满,因此考虑红色区域。
*1.如果3p为4的倍数,根据结论1,红色区域即可填满;
*2.如果m为偶数,根据结论2,红色区域即可填满;
显然,*2更有研究价值。
分析:∵X=m+2n,m为偶数;∴X为偶数;
∴当X为偶数,Y可表示为3p+4q时,可以填满。
但是,事实上Y并不一定可表示为3p+4q;
因此,考虑何时Y可表示为3p+4q,我们可以以Ymod3的情况为突破口;
(1)Y%3=0时,可设Y=3k=3k+4×0;
(2)Y%3=1时,可设Y=3k+1=3(k-1)+4×1;∵k-1>=0,∴k>=1,Y>=4;
(3)Y%3=2时,可设Y=3k+2=3(k-2)+4×2;∵k-2>=0,∴k>=2,Y>=8;
综上所述:
结论四:当一数为偶数,一数为除1,2,5以外的任意数,可以填满。
分割线
接下来就是枚举了:
1)Y=1,那么仅当X为4的倍数时,可以填满。
2)Y=2,根据结论4,仅当(1,2),(2,2),(2,5)时,不可填满。
3)Y=5,
① X为奇数,根据结论3,不可填满。
② X为偶数,设X=2n,将Y拆成2和3;
红 绿
红色区域,根据结论4,仅有n=1,即X=2时,不可填满。
绿色区域,根据结论2,必然可以填满。
∴仅(2,5)时不可填满。
综上我们得到结论:
结论五:当一数为1,一数不为4的倍数时,不可填满。
结论六:当(2,2)(2,5)时不可填满。((1,2)包括在结论5中)
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
最后总结:
结论一:当X,Y分别是1,4的倍数时,可以填满。
结论二:当X,Y分别是2,3的倍数时,可以填满。
结论三:当X×Y为奇数时,不可以填满。(即X与Y都为奇数)
结论四:当一数为偶数,一数为除1,2,5以外的任意数,可以填满。
结论五:当一数为1,一数不为4的倍数时,不可填满。
结论六:当(2,2)(2,5)时不可填满。
由此可见,仅当1.X×Y为奇数 2.一数为1,一数不为4的倍数 3.(X,Y)为(2,2)(2,5)不可填满,其他情况皆可以。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
最后,再上一遍注释版代码: