CF1819B The Butcher 题解

前言

感觉大家写麻烦了，提供一种更为简单的方法。

正文

0x00 题目分析

正向思考，去拼凑出一个矩形显然很困难麻烦，不好做。不妨考虑反向思考，观察这个过程，若第一刀竖着切，那么舍去那一片必然是有最长的边，反向的说这样情况下，最长的长边一定是原始纸片的长边，确定了原始长边自然能确定原始宽边，用总面积除一下即可；反之第一刀横切也是一样。

现在问题转化为一个给定长宽的矩形，是否能用一些小矩形拼凑出，而且只有 $2$ 中情况需要检查（第一次横切或者竖切）。现在就很简单了，与刚才同理第一刀切出来的纸片一定有着最长的长边或者宽边，那么用一个数据结构维护，在剩下的纸片中寻找一个最长的长或者宽，若匹配当前的长或者宽则弹出这个纸片，若无匹配则当前情况不符合，并且算出剩下部分的长和宽，继续看能否拼凑出剩下的矩形。发现是相似的过程，循环递推即可。

0x01 代码实现

用两个 set 维护即可，注意两种情况可能相同。

#include<bits/stdc++.h>
// #define ONLINE_JUDGE
#define INPUT_DATA_TYPE int
#define OUTPUT_DATA_TYPE long long
INPUT_DATA_TYPE read(){register INPUT_DATA_TYPE x=0;register char f=0,c=getchar();while(c<'0'||'9'<c)f=(c=='-'),c=getchar();while('0'<=c&&c<='9')x=(x<<3)+(x<<1)+(c&15),c=getchar();return f?-x:x;}void print(OUTPUT_DATA_TYPE x){register char s[20];register int i=0;if(x<0){x=-x;putchar('-');}if(x==0){putchar('0');return;}while(x){s[i++]=x%10;x/=10;}while(i){putchar(s[--i]+'0');}return;}

struct Paper{
    long long x,y;
}ps[200010];

struct NODE{
    long long val;
    int id;
    bool operator < (const NODE o) const{
        return val==o.val?id<o.id:val<o.val;
    }
};

int n;
std::set<NODE> stx,sty;

bool check(register long long nowx,register long long nowy){
    register int i,id;
    stx.clear(),sty.clear();
    for(i=0;i<n;++i) stx.insert((NODE){ps[i].x,i}),sty.insert((NODE){ps[i].y,i});
    while(!(stx.empty()&&sty.empty())){
        if(!stx.empty()&&stx.rbegin()->val==nowx){
            id=stx.rbegin()->id;
            nowy-=ps[id].y;
            sty.erase((NODE){ps[id].y,id});
            stx.erase(--stx.end());
        }else if(!sty.empty()&&sty.rbegin()->val==nowy){
            id=sty.rbegin()->id;
            nowx-=ps[id].x;
            stx.erase({ps[id].x,id});
            sty.erase(--sty.end());
        }else return false;
    }
    return true;
}

int main(){
	#ifndef ONLINE_JUDGE
	freopen("name.in", "r", stdin);
	freopen("name.out", "w", stdout);
	#endif

    int t=read();
    register int i;
    register long long sumar,maxx,maxy,x,y;
    register char a,b;
    while(t--){
        n=read();
        maxx=maxy=sumar=a=b=x=y=0;
        for(i=0;i<n;++i){
            ps[i].x=read();
            ps[i].y=read();
            sumar+=ps[i].x*ps[i].y;
            maxx=std::max(maxx,ps[i].x);
            maxy=std::max(maxy,ps[i].y);
        }
        if(!(sumar%maxx)&&check(maxx,sumar/maxx)) a=1,x=maxx,y=sumar/maxx;
        if(!(sumar%maxy)&&check(sumar/maxy,maxy)&&(sumar/maxy!=x&&maxy!=y)) b=1;
        print(a+b);putchar('\n');
        if(a) print(maxx),putchar(' '),print(sumar/maxx),putchar('\n');
        if(b) print(sumar/maxy),putchar(' '),print(maxy),putchar('\n');;
        
    }

	#ifndef ONLINE_JUDGE
	fclose(stdin);
	fclose(stdout);
	#endif
    return 0;
}

总结

这样的题要反向思考，抓住不变和可以确定的量，进而去解题，例如本题中的最长边和最宽边以及面积总和，这些不变量便是解题切入点。