C/C++教程

【牛客小白月赛】54 C School

本文主要是介绍【牛客小白月赛】54 C School，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

链接

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;
}
这篇关于【牛客小白月赛】54 C School的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
您可能喜欢
栏目导航