Loading... ## 前言 感觉大家写麻烦了,提供一种更为简单的方法。 ## 正文 ### 0x00 题目分析 正向思考,去拼凑出一个矩形显然很困难麻烦,不好做。不妨考虑反向思考,观察这个过程,若第一刀竖着切,那么舍去那一片必然是有最长的边,反向的说这样情况下,最长的长边一定是原始纸片的长边,确定了原始长边自然能确定原始宽边,用总面积除一下即可;反之第一刀横切也是一样。 现在问题转化为一个给定长宽的矩形,是否能用一些小矩形拼凑出,而且只有 $2$ 中情况需要检查(第一次横切或者竖切)。现在就很简单了,与刚才同理第一刀切出来的纸片一定有着最长的长边或者宽边,那么用一个数据结构维护,在剩下的纸片中寻找一个最长的长或者宽,若匹配当前的长或者宽则弹出这个纸片,若无匹配则当前情况不符合,并且算出剩下部分的长和宽,继续看能否拼凑出剩下的矩形。发现是相似的过程,循环递推即可。 ### 0x01 代码实现 用两个 set 维护即可,注意两种情况可能相同。 ```AC #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; } ``` ## 总结 这样的题要反向思考,抓住不变和可以确定的量,进而去解题,例如本题中的最长边和最宽边以及面积总和,这些不变量便是解题切入点。 最后修改:2023 年 11 月 10 日 © 允许规范转载 打赏 赞赏作者 赞 如果觉得我的文章对你有用,请随意赞赏