1 条题解
-
0XzyStudio (admin) LV 8 MOD RP++ 机房蒟蒻 tayz @ 2024-10-20 19:59:00
每个地毯可以看作一个两边均平行于坐标轴的矩形,两个这样的矩形相交得到的也是有同样性质的矩形,那么归纳可得任意个这样的矩形相交都仍然得到平行于坐标轴的矩形,但是矩形的交是不可逆的,也即我们不能先将所有矩形交起来再去掉其中一个来得到n-1个矩形的交。
那么我们可以计算矩形序列的前缀交和后缀交(这些交都是矩形),对于第i个矩形,除了该矩形外其它所有矩形的交即为前i-1个矩形的前缀交再交上后n-i个矩形的后缓交,也即每n-1个矩形的交都可以这样计算出来,而这些交会重复的部分一定是n个矩形的交,所以单独进行去重即可。std
#include<cstdio> #include<iostream> #include<cmath> #include<cstring> #include<cstdlib> #include<ctime> #include<algorithm> #define ll long long #define MAXN 1000005 using namespace std; inline int read() { int num=0,sgn=1; char ch=getchar(); while (ch!='-'&&(ch<'0'||ch>'9'))ch=getchar(); if (ch=='-')sgn=-1,ch=getchar(); while (ch>='0'&&ch<='9')num*=10,num+=ch-'0',ch=getchar(); return num*sgn; } struct carpet { ll a,b,c,d; carpet(){} carpet(ll _a,ll _b,ll _c,ll _d) {a=_a;b=_b;c=_c;d=_d;} }cp[MAXN],pre[MAXN],suf[MAXN]; carpet operator+(carpet A,carpet B) { if ((A.a==-1)||(B.a==-1))return carpet(-1,-1,-1,-1); carpet S; S.a=max(A.a,B.a);S.b=max(A.b,B.b); S.c=min(A.c,B.c);S.d=min(A.d,B.d); if ((S.a>=S.c)||(S.b>=S.d))return carpet(-1,-1,-1,-1); return S; } int T,p,q,n; int a,b,c,d; ll ans; ll calc(carpet A) { if (A.a==-1)return 0; return (A.c-A.a)*(A.d-A.b); } int main() { T=read(); while (T--) { p=read();q=read();n=read(); for (int i=1;i<=n;i++) { a=read();b=read();c=read();d=read(); cp[i]=carpet(a,b,c,d); } pre[0]=carpet(0,0,p,q); for (int i=1;i<=n;i++) pre[i]=pre[i-1]+cp[i]; suf[n+1]=carpet(0,0,p,q); for (int i=n;i>=1;i--) suf[i]=suf[i+1]+cp[i]; ans=0; for (int i=1;i<=n;i++) ans+=calc(pre[i-1]+suf[i+1]);//n-1个地毯的交,枚举任何一块地毯不在其中的时候 //当不算第一块地毯的交,当不算第二块地毯的交。。。。 ans-=calc(pre[n])*(ll)(n-1); //第n块地毯的交一定是被重复计算了n次,而我们只需要计算1次 cout<<ans<<endl; } return 0; }
- 1
信息
- ID
- 1031
- 难度
- 9
- 分类
- (无)
- 标签
- 递交数
- 1
- 已通过
- 1
- 通过率
- 100%
- 上传者