【牛客小白月赛】54 C School
2022/8/13 6:23:25
本文主要是介绍【牛客小白月赛】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的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-04-26高性能表格工具VTable总体构成-icode9专业技术文章分享
- 2024-04-16软路由代理问题, tg 无法代理问题-icode9专业技术文章分享
- 2024-04-16程序猿用什么锅-icode9专业技术文章分享
- 2024-04-16自建 NAS 的方案-icode9专业技术文章分享
- 2024-04-14ansible 在远程主机上执行脚本,并传入参数-icode9专业技术文章分享
- 2024-04-14ansible 在远程主机上执行脚本,并传入参数, 加上remote_src: yes 配置-icode9专业技术文章分享
- 2024-04-14ansible 检测远程主机的8080端口,如果关闭,则echo 进程已关闭-icode9专业技术文章分享
- 2024-04-14result 成功怎么写-icode9专业技术文章分享
- 2024-04-14stopped 状态设置为变量,由外部传递进来-icode9专业技术文章分享
- 2024-04-14为什么ansible执行远程脚本需要放到后台-icode9专业技术文章分享