题解：CF2111F Puzzle

· · 题解

题解：CF2111F Puzzle

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

通过小学学习的知识“平移”，我们可以发现在一个长和宽固定的“L”型图案填充为一个长方形的过程中总周长不变，所以周长比面积更好列举和确定，显然通过周长判断面积是否可以满足题目要求是比较简单的，此时我们需要思考如何构造“L”型图案的横排与竖排长度。我们通过奇奇怪怪的常识（或者枚举）可知，当总周长一定时，长与宽越接近，填满后的面积越大。所以我们选择长与宽最接近的方案，就有周长为 p 时，长与宽相加等于 \frac{p}{2} ，为了使长与宽最接近，我们固定长是向上取整的 \frac{p}{4} ，宽是 \frac{p}{2}-⌈\frac{p}{4}⌉ 。（会发现长与宽的改变不影响最少的方块数量（面积），其恒为 x + y-1 ）

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

如果要求的小方块数小于满足周长最小要求的单纯组成“L”型的图案的小方块数，说明无论如何都不能满足条件，输出无解；否则一定有解，如果当前图形完全填充，面积等于 x\times y 的时候不满足要求，说明整体太小了，我们就不断枚举面积和周长最简比的倍数，直到找到其实际的周长和面积为止（这也是需要先求最简比值的原因，这样既能在答案是最简比值找到，实际答案为其倍数时之后也能枚举找到）。

代码和具体解释如下：

#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;
}

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