西南民族大学 春季 2023 训练赛 6-补题
#include<bits/stdc++.h> using namespace std; typedef pair<int,int>PII; const int N=1e3+5,M=525605,INF=0x3f3f3f3f,Mod=1e6; const double eps=1e-8; typedef long long ll; string s="2022-04-23"; int main(){ ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); cout<<"I'm gonna win! Today!\n"; cout<<s; return 0; }
#include<bits/stdc++.h> using namespace std; typedef pair<int,int>PII; const int N=1e3+5,M=525605,INF=0x3f3f3f3f,Mod=1e6; const double eps=1e-8; typedef long long ll; int a,b; int main(){ ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); cin>>a>>b; cout<<a/b; return 0; }
思路:判断每种情况
#include<bits/stdc++.h> using namespace std; typedef pair<int,int>PII; const int N=1e3+5,M=525605,INF=0x3f3f3f3f,Mod=1e6; const double eps=1e-8; typedef long long ll; int a,b,x,y; int main(){ ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); cin>>a>>b>>x>>y; if(x<a&&y<a){ cout<<x<<"-N "<<y<<"-N\n"; cout<<"zhang da zai lai ba"; return 0; } if(x>=a&&y>=a){ cout<<x<<"-Y "<<y<<"-Y\n"; cout<<"huan ying ru guan"; return 0; } if((x<a&&y>=b)||(y<a&&x>=b)){ int aa,bb; if(x<a)aa=1,bb=2; else aa=2,bb=1; cout<<x<<"-Y "<<y<<"-Y\n"; cout<<"qing "<<bb<<" zhao gu hao "<<aa; return 0; } int aa; if(x>a){aa=1;cout<<x<<"-Y "<<y<<"-N\n"; } else { aa=2;cout<<x<<"-N "<<y<<"-Y\n"; } cout<<aa<<": huan ying ru guan"; return 0; }
#include<bits/stdc++.h> using namespace std; typedef pair<int,int>PII; const int N=1e3+5,M=525605,INF=0x3f3f3f3f,Mod=1e6; const double eps=1e-8; typedef long long ll; int a,b; int main(){ ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); cin>>a>>b; int res=1; for(int i=2;i<=a+b;++i)res*=i; cout<<res; return 0; }
#include<bits/stdc++.h> using namespace std; typedef pair<int,int>PII; const int N=1e3+5,M=525605,INF=0x3f3f3f3f,Mod=1e6; const double eps=1e-8; typedef long long ll; int a[6]; int k; int main(){ ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); for(int i=0;i<6;++i)cin>>a[i]; cin>>k; k=6-k+1; for(int i=0;i<6;++i){ if(a[i]>=k)cout<<k-1; else cout<<k; if(i!=5)cout<<' '; } return 0; }
#include<bits/stdc++.h> using namespace std; typedef pair<int,int>PII; const int N=1e3+5,M=525605,INF=0x3f3f3f3f,Mod=1e6; const double eps=1e-8; typedef long long ll; string a,b,x,y; int main(){ ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); x=y=""; cin>>a>>b; for(int i=1;i<a.size();++i){ if(a[i]%2==a[i-1]%2)x+=max(a[i],a[i-1]); } for(int i=1;i<b.size();++i){ if(b[i]%2==b[i-1]%2)y+=max(b[i],b[i-1]); } if(x==y)cout<<x; else cout<<x<<'\n'<<y; return 0; }
思路:二维差分和
#include<bits/stdc++.h> using namespace std; typedef pair<int,int>PII; const int N=1e3+5,M=525605,INF=0x3f3f3f3f,Mod=1e6; const double eps=1e-8; typedef long long ll; int n,m,q; void add(vector<vector<int>>&ve,int x1,int y1,int x2,int y2,int c){ ve[x1][y1]+=c,ve[x2+1][y1]-=c,ve[x1][y2+1]-=c,ve[x2+1][y2+1]+=c; } int main(){ ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); cin>>n>>m>>q; vector<vector<int>>ve(n+5,vector<int>(m+5,0)); int op,x; while(q--){ cin>>op>>x; if(op==0){ add(ve,x,1,x,m,1); } else{ add(ve,1,x,n,x,1); } } int res=0; for(int i=1;i<=n;++i) for(int j=1;j<=m;++j){ ve[i][j]+=(ve[i-1][j]+ve[i][j-1]-ve[i-1][j-1]); if(ve[i][j]==0)res++; } cout<<res; return 0; }
思路:过175分且pat成绩到达分数线的一定可以选入,将剩余的过175分的人数记录,统计人数,若某个分段的人数大于k,加k即可
#include<bits/stdc++.h> using namespace std; typedef pair<int,int>PII; const int N=1e3+5,M=525605,INF=0x3f3f3f3f,Mod=1e6; const double eps=1e-8; typedef long long ll; int n,k,s,res; int aa[300]; int main(){ ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); cin>>n>>k>>s; int a,b; for(int i=0;i<n;++i){ cin>>a>>b; if(a>=175){ if(b>=s)res++; else aa[a]++; } } for(int i=175;i<=290;++i){ if(aa[i]<=k)res+=aa[i]; else res+=k; } cout<<res; return 0; }
思路:stack模拟
#include<bits/stdc++.h> using namespace std; typedef pair<int,int>PII; const int N=1e3+5,M=525605,INF=0x3f3f3f3f,Mod=1e6; const double eps=1e-8; typedef long long ll; stack<int>stk; int n,m,k,a[N]; int main(){ ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); cin>>n>>m>>k; for(int i=0;i<n;++i)cin>>a[i]; int j=0,i=0,x; vector<int>ans; while(1){ x=100; while(!stk.empty()){ if(j>=k)break; if(stk.top()<=x){ ans.push_back(stk.top());x=stk.top(); stk.pop();j++; }else break; } if(j<k){ while(j<k&&i<n){ int u=a[i++]; if(u<=x){ ans.push_back(u);x=u;j++; } else if(stk.size()<m)stk.push(u); else{ i--;break; } } } for(int u=0;u<ans.size();++u){ cout<<ans[u]; if(u!=ans.size()-1)cout<<' '; } if(i<n||!stk.empty())cout<<'\n'; else break; j=0;ans.clear(); } return 0; }
思路:直接转化为秒排,或者直接排也行
#include<bits/stdc++.h> using namespace std; typedef pair<int,int>PII; const int N=86400+5,M=1e3+5,INF=0x3f3f3f3f,Mod=1e6; const double eps=1e-8; typedef long long ll; int n; struct E{ int a,b,c; }; vector<pair<E,E>>ve; bool cmp(pair<E,E>a,pair<E,E>b){ E x=a.first,y=b.first; if(x.a==y.a){ if(x.b==y.b)return x.c<y.c; return x.b<y.b; } return x.a<y.a; } bool cmpp(E a,E b){ if(a.a==b.a){ if(a.b==b.b)return a.c>b.c; return a.b>b.b; } return a.a>b.a; } void ppp(int x){ if(x==0)cout<<"00"; else if(x<10)cout<<"0"<<x; else cout<<x; } void pp(E a,E b){ ppp(a.a);cout<<":"; ppp(a.b);cout<<":"; ppp(a.c);cout<<" - "; ppp(b.a);cout<<":"; ppp(b.b);cout<<":"; ppp(b.c); } int main(){ ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); cin>>n; char d; for(int i=0;i<n;++i){ int a,b,c,aa,bb,cc; cin>>a>>d>>b>>d>>c>>d>>aa>>d>>bb>>d>>cc; ve.push_back({{a,b,c},{aa,bb,cc}}); } sort(ve.begin(),ve.end(),cmp); E h={0,0,0},rr={23,59,59}; vector<pair<E,E>>ans; for(int i=0;i<n;++i){ E x=ve[i].first,y=ve[i].second; if(cmpp(x,h))ans.push_back({h,x}); h=y; } if(h.a!=rr.a||h.b!=rr.b||h.c!=rr.c)ans.push_back({h,rr}); for(int i=0;i<ans.size();++i){ pp(ans[i].first,ans[i].second); if(i!=ans.size()-1)cout<<"\n"; } return 0; }
思路:并查集维护当前需要经过的个数和每个点到根节点(外卖站)的距离,由于最后一次不用返回起点,最短路程为:(fa[sta]+1)*(-2)-maxdis
#include<bits/stdc++.h> using namespace std; typedef pair<int,int>PII; const int N=1e5+5,M=1e3+5,INF=0x3f3f3f3f,Mod=1e6; const double eps=1e-8; typedef long long ll; int n,m,g[N],sta=-1,fa[N],dis[N],ma; int find(int x){ if(fa[x]<0)return x; return fa[x]=find(fa[x]); } void dfs(int x){ if(find(x)==sta)return ; dfs(g[x]); dis[x]=dis[g[x]]+1;ma=max(ma,dis[x]); fa[sta]+=fa[x],fa[x]=sta; return ; } int main(){ ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); cin>>n>>m; for(int i=1;i<=n;++i){ cin>>g[i]; if(g[i]==-1)sta=i; } int x; memset(fa,-1,sizeof fa); while(m--){ cin>>x; if(find(x)!=sta)dfs(x); cout<<-2*(fa[sta]+1)-ma<<'\n'; } return 0; }
思路:floyed求最短距离,分别统计男女生的“大众情人”
#include<bits/stdc++.h> using namespace std; typedef pair<int,int>PII; const int N=5e2+5,INF=0x3f3f3f3f,Mod=1e6; const double eps=1e-8; typedef long long ll; int n,d[N][N]; char sex[N]; vector<int>f,m; int main(){ ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); cin>>n; memset(d,0x3f,sizeof d); for(int i=1;i<=n;++i){ cin>>sex[i]; if(sex[i]=='F')f.push_back(i); else m.push_back(i); int k,x,w; char c; cin>>k; while(k--){ cin>>x>>c>>w; d[i][x]=min(d[i][x],w); } } for(int k=1;k<=n;++k){ for(int i=1;i<=n;++i){ if(i==k||d[i][k]==INF)continue; for(int j=1;j<=n;++j) { if(i==j||k==j||d[k][j]==INF)continue; d[i][j]=min(d[i][j],d[i][k]+d[k][j]); } } } vector<int>F,M; for(int i=1;i<=n;++i){ int v=-1; if(sex[i]=='F'){ for(auto j:m){ v=max(v,d[j][i]); } if(F.empty())F.resize(2),F[0]=v,F[1]=i; else if(F[0]==v)F.push_back(i); else if(F[0]>v)F.resize(2),F[0]=v,F[1]=i; } else{ for(auto j:f){ v=max(v,d[j][i]); } if(M.empty())M.resize(2),M[0]=v,M[1]=i; else if(M[0]==v)M.push_back(i); else if(M[0]>v)M.resize(2),M[0]=v,M[1]=i; } } for(int i=1;i<F.size();++i){ cout<<F[i]; if(i!=F.size()-1)cout<<' '; }cout<<'\n'; for(int i=1;i<M.size();++i){ cout<<M[i]; if(i!=M.size()-1)cout<<' '; } return 0; }