题解：CF2111F Puzzle

这是一道有一定思维难度但是代码非常简单的题目，非常适合我这样代码能力超低的人。 ~~（不代表我的思维就很好）~~

通过小学学习的知识“平移”，我们可以发现在一个长和宽固定的“L”型图案填充为一个长方形的过程中总周长不变，所以周长比面积更好列举和确定，显然通过周长判断面积是否可以满足题目要求是比较简单的，此时我们需要思考如何构造“L”型图案的横排与竖排长度。我们通过奇奇怪怪的常识（或者枚举）可知，当总周长一定时，长与宽越接近，填满后的面积越大。所以我们选择长与宽最接近的方案，就有周长为

p

时，长与宽相加等于

\frac{p}{2}

，为了使长与宽最接近，我们固定长是向上取整的

\frac{p}{4}

，宽是

\frac{p}{2}-⌈\frac{p}{4}⌉

。（会发现长与宽的改变不影响最少的方块数量（面积），其恒为

x

+

y-1

）

接下来，既然已经找到了长和宽，就要开始寻找合适的方案使面积达到要求了。

如果要求的小方块数小于满足周长最小要求的单纯组成“L”型的图案的小方块数，说明无论如何都不能满足条件，输出无解；否则一定有解，如果当前图形完全填充，面积等于

x\times y

的时候不满足要求，说明整体太小了，我们就不断枚举面积和周长最简比的倍数，直到找到其实际的周长和面积为止（这也是需要先求最简比值的原因，这样既能在答案是最简比值找到，实际答案为其倍数时之后也能枚举找到）。

代码和具体解释如下：

CPP

#include<bits/stdc++.h>
using namespace std;
int t,p,s;
int main(){
	cin>>t;
	while(t--){                                                                            
		cin>>p>>s;
		int gcd=__gcd(p,s);
		p/=gcd;
		s/=gcd;//化简成最简分数 （这样才能从最小开始找答案） 
		if(p%2==1)p*=2,s*=2;//周长必须是偶数
		int leng=(p/2)/2; 
		int wid=(p/2)-leng;//找到长与宽最接近的值，这样的面积最大值才是最大的 
		int i=2;
		while(leng*wid<s*(i-1)){
			leng=(p*i/2)/2;
			wid=((p*i)/2)-leng;
			i++;
		}//寻找合适的整体放大倍数 
		p*=(i-1);
		s*=(i-1);
		s-=leng+wid-1;//leng+wid-1是当前的最小面积，长和宽都只放一行 
		//cout<<leng<<" "<<wid<<endl;
		if(s<0)cout<<"-1"<<endl;//如果要求的面积太小了，周长要求达不到，则无解 
		else {
			cout<<s+leng+wid-1<<"\n";//输出全部方块数，要把之前减去的加上 
			for(int i=1;i<leng;i++)cout<<i<<" 0\n";//先铺第一行 
			for(int i=0;i<wid;i++)cout<<"0 "<<i<<"\n";//铺第一列 
			for(int i=1;i<leng;i++){//循环模拟放方块 
			    if(!s) break;//如果方块已经放完了，结束 
				for(int j=1;j<wid;j++){
					if(!s)break;
					s--;
					cout<<i<<" "<<j<<"\n";
				}
			}
		}
		
	}
	return 0;
}

感谢你观看我的第一篇题解。

题解：CF2111F Puzzle

文章操作

题解：CF2111F Puzzle

相关推荐

评论

题解：CF2111F Puzzle