链接
https://ac.nowcoder.com/acm/contest/38457/C
题意是说，给你n个形如a时b分 c时d分的条件限制，表示不能选取，给出m个询问某个值是否可以选取
思路
1.可以把x时y分转化成一个值 ( x*m+y ) ，这样就可以把原条件看成n个区间的限制，用差分思想可做
点击查看代码
#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define pb push_back
using namespace std;
const int N = 1e4+10;
int n,m,h,q;
vector<ll>v1,v2;
int main(){
int t;
// cin>>t;
t=1;
while(t--){
cin>>n>>h>>m>>q;
for(int i=1,a,b,c,d;i<=n;i++){
scanf("%d%d%d%d",&a,&b,&c,&d);
ll ta=a*m+b;
ll tb=c*m+d;
v1.pb(ta);
v2.pb(tb);
}
sort(v1.begin(),v1.end());
sort(v2.begin(),v2.end());
for(int i=1,x,y;i<=q;i++){
scanf("%d%d",&x,&y);
ll tem=x*m+y;
if(lower_bound(v1.begin(),v1.end(),tem)-v1.begin() ==
lower_bound(v2.begin(),v2.end(),tem)-v2.begin()) puts("Yes");
else puts("No");
}
}
system("pause");
return 0;
}
2.可以把a时b分看成一个值后，合并有重合部分的区间，把区间分成几个不相交的
点击查看代码
#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define pb push_back
using namespace std;
const int N = 1e4+10;
int n,m,h,q,l,r,mid,ans;
vector<pair<ll,ll> >v,tem;
void solve(){
sort(v.begin(), v.end());
ll st = -1,en = -1;
for (auto i:v) {
if(st==-1){
st=i.first;
en=i.second;
}
else{
if(i.first>en){
tem.pb({st,en});
st=i.first;
en=i.second;
}
else{
en=max(en,i.second);
}
}
}
tem.pb({st,en});
}
int main(){
cin>>n>>h>>m>>q;
for(int i=1,a,b,c,d;i<=n;i++){
scanf("%d%d%d%d",&a,&b,&c,&d);
ll ta=a*m+b;
ll tb=c*m+d;
v.pb({ta,tb});
}
solve();
// for(auto i:tem){
// cout<<i.first<<' '<<i.second<<endl;
// }
for(int i=1,x,y;i<=q;i++){
scanf("%d%d",&x,&y);
ll z=x*m+y;
l=0,r=tem.size()-1; ans=-1;
while(l<=r){
mid=(l+r)>>1;
if(tem[mid].second>z){
r=mid-1;
ans=mid;
}
else l=mid+1;
}
if(z>tem.back().second || z<tem[ans].first) puts("Yes");
else puts("No");
}
system("pause");
return 0;
}
3.把[a+1,c-1]都标记为1，表示整个小时都不能访问，另外维护每个小时的不能被访问的区间
点击查看代码
#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define pb push_back
using namespace std;
const int N = 1e4+10;
int n,m,h,q;
bool forbid[N];
int l[N],r[N],ml[N],mr[N];
int main(){
int t;
t=1;
while(t--){
cin>>n>>h>>m>>q;
for(int i=0;i<=h;i++) r[i]=m+1,l[i]=-1,ml[i]=mr[i]=-1;
for(int i=1,a,b,c,d;i<=n;i++){
scanf("%d%d%d%d",&a,&b,&c,&d);
if(a==c){
ml[a]=b;
mr[a]=d;
continue;
}
r[a]=min(r[a],b);
l[c]=max(l[c],d);
for(int j=a+1;j<=c-1;j++){
forbid[j]=1;
}
}
for(int i=1,x,y;i<=q;i++){
scanf("%d%d",&x,&y);
if(forbid[x]) puts("No");
else{
if(y<=l[x]||y>=r[x]||(ml[x]!=-1&&ml[x]<=y&&y<=mr[x])) puts("No");
else puts("Yes");
}
}
}
system("pause");
return 0;
}