A - Circuits
不難發(fā)現(xiàn)x坐標(biāo)根本沒用，只需要存儲(chǔ)y坐標(biāo)。
題目所求的兩條直線y1=ay_1=ay1?=a，y2=b(a<b)y_2=b\ (a<b)y2?=b?(a<b)
我們枚舉y2=by_2=by2?=b這條線，這條線一定可以是矩形的邊界，于是我們掃描矩形邊界差分計(jì)算當(dāng)前這條線覆蓋的矩形個(gè)數(shù)，對(duì)于這條線沒有覆蓋的矩形把它丟到線段樹中（維護(hù)區(qū)間+和區(qū)間max即可）然后區(qū)間查詢y1=ay_1=ay1?=a覆蓋的最大矩形即可。兩種相加即是當(dāng)前的情況的最大數(shù)量。
#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0)
#pragma GCC optimize(2)
#include<set>
#include<map>
#include<cmath>
#include<stack>
#include<queue>
#include<random>
#include<bitset>
#include<string>
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<unordered_map>
#include<unordered_set>
using namespace std
;
typedef long long ll
;
typedef pair
<int,int> pii
;
const ll mod
=998244353;
const int N
=200010;
int n
,m
;
struct line
{int id
,v
,op
;bool operator
<(const line
&o
) const{if(v
==o
.v
) return op
<o
.op
;return v
<o
.v
;}
}q
[N
];
int y
[N
];
pii a
[N
];
int find(int x
)
{return lower_bound(y
+1,y
+1+m
,x
)-y
;
}
struct node
{int l
,r
;int v
,lazy
;}tree
[N
*4];
void pushup(int u
)
{tree
[u
].v
=max(tree
[u
<<1].v
,tree
[u
<<1|1].v
);
}
void build(int u
,int l
,int r
)
{tree
[u
]={l
,r
};if(l
==r
) {tree
[u
].v
=0;return;}int mid
=l
+r
>>1;build(u
<<1,l
,mid
),build(u
<<1|1,mid
+1,r
);pushup(u
);
}
void pushdown(int u
)
{if(!tree
[u
].lazy
) return;tree
[u
<<1].lazy
+=tree
[u
].lazy
;tree
[u
<<1|1].lazy
+=tree
[u
].lazy
;tree
[u
<<1].v
+=tree
[u
].lazy
;tree
[u
<<1|1].v
+=tree
[u
].lazy
;tree
[u
].lazy
=0;}
void modify(int u
,int l
,int r
,int v
)
{if(l
>r
) return;if(tree
[u
].l
>=l
&&tree
[u
].r
<=r
){tree
[u
].lazy
+=v
;tree
[u
].v
+=v
;return;}pushdown(u
);int mid
=tree
[u
].l
+tree
[u
].r
>>1; l
+tree
[u
].r
>>1;if(l
<=mid
) modify(u
<<1,l
,r
,v
);if(r
>mid
) modify(u
<<1|1,l
,r
,v
);pushup(u
);
}
int main()
{IO
;int T
=1;while(T
--){cin
>>n
;for(int i
=1;i
<=n
;i
++){int t1
,t2
;cin
>>t1
>>y
[i
];cin
>>t2
>>y
[i
+n
];a
[i
]={y
[i
+n
],y
[i
]};y
[i
]++;q
[i
]={i
,y
[i
],-1};q
[i
+n
]={i
,y
[i
+n
],+1};}sort(y
+1,y
+1+2*n
);m
=unique(y
+1,y
+1+2*n
)-y
-1;build(1,1,m
);sort(q
+1,q
+1+2*n
);int pre
=0;int res
=0;for(int i
=1;i
<=2*n
;i
++){pre
+=q
[i
].op
;res
=max(res
,pre
+tree
[1].v
);if(q
[i
].op
==-1){int id
=q
[i
].id
;modify(1,find(a
[id
].first
),find(a
[id
].second
+1)-1,1);}}cout
<<res
<<'\n';}return 0;
}
這題有一個(gè)錯(cuò)誤的貪心思路即求兩邊最大值。
先讓第一條線覆蓋最多的矩形，然后把這些矩形刪除，然后再求出第二條線覆蓋最多的矩形。
我也不知道這個(gè)貪心思路錯(cuò)在哪里（還沒舉出反例
先貼一個(gè)隊(duì)友寫的錯(cuò)誤代碼
反例：湊合看吧（懂得都懂
#include<cstdio>
#include<cstring>
#include<iostream>
#include<cmath>
#define N 20000005
using namespace std
;
const int m
= 10000000,inf
= 20000000;
int n
;
struct operation
{int c1
,c2
,r1
,r2
;
}op
[100005];
int x
[N
],y
[N
],cans1
,cans2
;
int read(){char ch
= getchar();int re
= 0,fl
= 1;while(ch
<'0'||ch
>'9') {if(fl
== '-')fl
= -1; ch
= getchar();}while(ch
>='0'&&ch
<='9') {re
= (re
<<1)+(re
<<3)+ch
-'0'; ch
= getchar();}return re
*fl
;
}
int main(){int r1
,r2
,c1
,c2
,rf
= inf
,rl
= 0,cf
= inf
,cl
= 0;int pre
= 0,fd
= 0; n
= read();for(int i
=1;i
<=n
;++i
){r1
= read()+m
; c1
= read()+m
;r2
= read()+m
; c2
= read()+m
;y
[c1
+1]--; y
[c2
]++;op
[i
].c1
= c1
; op
[i
].c2
= c2
; op
[i
].r1
= r1
; op
[i
].r2
= r2
;}pre
= 0; fd
= -1;for(int i
=0;i
<=2*m
;++i
){pre
+= y
[i
];if(pre
>= cans1
){cans1
= pre
; fd
= i
;}}for(int i
=1;i
<=n
;++i
)if(op
[i
].c1
>= fd
&& op
[i
].c2
<= fd
){y
[op
[i
].c1
+1]++; y
[op
[i
].c2
]--;}pre
= 0;for(int i
=0;i
<=2*m
;++i
){pre
+= y
[i
];cans2
= max(cans2
,pre
);}printf("%d\n",cans1
+cans2
);return 0;
}
總結(jié)
以上是生活随笔為你收集整理的2018-2019 ACM-ICPC, Asia Seoul Regional Contest——A - Circuits的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。
