题解：P10358 [PA2024] Obrazy

EMO_smile · 2024-07-30 13:57:03 · 题解

P10358 [PA2024] Obrazy

题目传送门

题意分析：

1.特判

我们很容易能够想到本题的特殊判断：即当最小的画框都不可能覆盖整个矩形墙面时，输出 -1。

2.常规

若我们将墙面的长设为 l，宽设为 r,画框最小边长为 a[i]，画框可覆盖面积为 ans（因为需要保证画框的完整性，不能让一个 2\times2 的画框变为 1\times4），易得：

当 ans < l\times r 时，输出 -1。

我们可用一个变量 tmp 来表示当前画框可覆盖面积， a1[i] 来判断第 i 个画框的面积，判断当前有多少个 a1[i-1] 面积的画框可以被 a1[i] 整除即可：

tmp=(l-(l%a[i]))*(r-(r%a[i]));
ans-=tmp/a1[i-1];//较小画框可换数量
ans+=tmp/a1[i];//较大画框可换数量

代码：

//#pragma GCC optimize(3,"Ofast","inline")
#include<bits/stdc++.h>
using namespace std;
inline long long read(){//快读
    long long x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-'){
            f=-1;
        }
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        x=(x<<1)+(x<<3)+(c^'0');
        c=getchar();
    }
    return x*f;
}
void write(int x){//快写（虽然不经常用）
    if(x<0){
        putchar('-');
        x=-x;
    }
    if(x>9){
        write(x/10);
    }
    putchar(x%10+'0');
    return;
}
long long a[1145141],f[1145141],n,m,l,r,a1[1145141];
int main(){
    l=read();r=read();
    m=l*r;//计算总面积
    n=read();
    long long ans=0;
    for(int i=1;i<=n;i++){
        a[i]=read();
        a1[i]=a[i]*a[i];
        if(i==1){//特判：最小画框有无可能全部覆盖
            ans=(l-(l%a[i]))*(r-(r%a[i]));
            ans=ans/a1[i];
            if(ans*a1[i]<m){
                cout<<-1;
                exit(0);//=return 0;
            }
        }else{
            long long tmp=(l-(l%a[i]))*(r-(r%a[i]));//tmp表示当前画框可覆盖面积
            ans-=tmp/a1[i-1];//较小画框可换数量
            ans+=tmp/a1[i];//较大画框可换数量
        }
    }
    cout<<ans;
    return 0;
}