arc172a 题解

Drind · 2024-02-18 22:16:35 · 个人记录

好听好玩。

题目解析

给定一个长宽为 h,w 的矩形，给定 n 个边长为 2^{a_i} 的正方形，问能不能不重叠地塞进矩形内。

因为我们发现，如果 h,w 有一个不是 2 的倍数，那么就会存在一条小缝，使得只有 1\times 1 的正方形能塞进去，所以直接无脑把缝塞满就好了，显然是不劣的。然后如果正方形用完了好说，如果没用完，只能占据别的大的方块的位置了，所以我们直接让他们四个四个地抱团，因为占着不满 2\times 2 的格子也是浪费。

好了我们把最小的处理完了，剩下的全部除以 2，重复这个过程就行了。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+10;

int a[N];

inline int qpow(int a,int index){
    int ans=1;
    while(index){
        if(index&1) ans=ans*a;
        a=a*a; index>>=1;
    }
    return ans;
}

int cnt[N];

inline void fake_main(){
    int h,w,n; cin>>h>>w>>n; int tot=0;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        cnt[a[i]+1]++;
    }
    for(int i=1;i<=40;i++){
        if(h*w==0&&cnt[i]!=0){//没地方放了
            cout<<"No\n";
            return;
        }
        int tmp=0;
        if(h%2==0&&w%2==1) tmp=h;//缝的大小
        if(h%2==1&&w%2==0) tmp=w;
        if(h%2==1&&w%2==1) tmp=h+w-1;
        h/=2; w/=2;
        if(cnt[i]<=tmp) continue;//放得下，好说
        cnt[i]-=tmp; cnt[i+1]+=(cnt[i]+3)/4; //放不下，抱团
    }
    cout<<"Yes\n";
}

signed main(){
    ios::sync_with_stdio(false);
    int t; t=1;
    while(t--) fake_main();
}