From nfls 2025 Summer Camp S+
题目后的括号( a , b ) (a,b)(a,b)表示 (难度，考场思考率)
目录
- T3 矩形坑洞覆盖 （easy+,80%）
- T4 ABBA替换（mid-,60%）
- T5 [POI 2005] SAM-Toy Cars（mid-,95%）
- T7 [SCOI2006] zh_tree（mid+,40%）
- T8 CF627D Preorder Test （mid+,5%）
- 总结
T3 矩形坑洞覆盖 （easy+,80%）
link
题意
有一个长为h o l e H holeHholeH宽为h o l e W holeWholeW的矩形洞口。给定n nn块木板( h i , w i ) (h_i,w_i)(hi,wi)，木板之间可以重叠，叠木板时允许木板旋转90 ° 90°90°，但最终放置时必须与坑洞的边平行。选的每块木板的四个角点必须严格位于坑洞边界之外（即不允许任何角点接触坑洞边界）。求完全覆盖洞口所需的最小木板数，无解则− 1 -1−1。1 ≤ n ≤ 50 , 1 ≤ h o l e H , h o l e W , h i , w i ≤ 10 9 1 \le n \le 50 , 1 \le holeH,holeW,h_i,w_i \le 10^91≤n≤50,1≤holeH,holeW,hi,wi≤109
思路
手玩多组样例可得一个贪心结论：横向和纵向如果各使用一部分木板是没有意义的，所以只考虑全是横向或者全是纵向排列的情况。于是直接模拟即可。
反思
场上有点看错题了。（-40pts）太久忘记贪心了。
代码
#include<bits/stdc++.h>usingnamespacestd;constintmaxn=55;inth[maxn],w[maxn];structNODE{intx,y;}a[maxn];intmain(){inthh,ww,n;cin>>hh>>ww>>n;for(inti=1;i<=n;i++)cin>>a[i].x;cin>>n;for(inti=1;i<=n;i++)cin>>a[i].y;inthm=0,wm=0;for(inti=1;i<=n;i++){if(a[i].x>hh&&a[i].y>hh)w[++wm]=max(a[i].x,a[i].y);elseif(a[i].x>hh)w[++wm]=a[i].y;elseif(a[i].y>hh)w[++wm]=a[i].x;if(a[i].x>ww&&a[i].y>ww)h[++hm]=max(a[i].x,a[i].y);elseif(a[i].x>ww)h[++hm]=a[i].y;elseif(a[i].y>ww)h[++hm]=a[i].x;}sort(w+1,w+wm+1,[](inta,intb){returna>b;});intans
