2023天梯赛记录

L2-001 紧急救援

#include<iostream>
#include<cstring>
using namespace std;const int MAX=520;
int jiu[MAX],g[MAX][MAX];
int n,m,s,d;
//num为最短路径条数，ans是最大救援队数量
int ds[MAX],num[MAX],ans[MAX];
bool vis[MAX];
int last[MAX];//每次找出最短路径，如果不唯一更新num,然后选出人最多的那一条路，更新ans，然后将那个节点加入到e当中去，当遇到m时则停止
void dis(){memset(ds,0x3f,sizeof ds);ds[s]=0;num[s]=1;ans[s]=jiu[s];for(int i=0;i<n;i++){int t=-1;for(int j=0;j<n;j++){if(!vis[j]&&(t==-1||ds[t]>ds[j])) t=j;}vis[t]=1;//  cout<<t<<endl;for(int j=0;j<n;j++){//     cout<<j<<" "<<t<<endl;if(ds[j]==ds[t]+g[t][j]&&ds[j]!=0x3f3f3f3f){num[j]+=num[t];//     cout<<" j="<<j<<" "<<num[j]<<" "<<ds[j]<<" t="<<t<<endl;if(ans[t]>ans[j]-jiu[j]){ans[j]=ans[t]+jiu[j];last[j]=t;}}if(ds[j]>ds[t]+g[t][j]){ds[j]=ds[t]+g[t][j];num[j]=num[t];ans[j]=ans[t]+jiu[j];last[j]=t;//cout<<j<<" "<<num[j]<<" "<<ds[j]<<endl;}}}return ;
}void prin(int i){if(i==s) return ;prin(last[i]);cout<<last[i]<<" ";
}int main(){cin>>n>>m>>s>>d;for(int i=0;i<n;i++) cin>>jiu[i];memset(g,0x3f,sizeof g);for(int i=0;i<m;i++){int a,b,c;cin>>a>>b>>c;g[a][b]=g[b][a]=c;}dis();cout<<num[d]<<" "<<ans[d]<<endl;// cout<<s<<" ";prin(d);cout<<d;return 0;
}

L2-002 链表去重

#include<bits/stdc++.h>
using namespace std;const int N = 1e5+100;struct hh{int num,last;
}h[N];
int v[N];
int list1[N],list2[N];int main(){int str,n;cin>>str>>n;for(int i=0;i<n;i++){int a,b,c;cin>>a>>b>>c;h[a]={b,c};}int k = str;int j1=0,j2=0;while(k!=-1){int m = abs(h[k].num);if(!v[m]){list1[j1++] = k;v[m]=1;}else{list2[j2++] = k;}k=h[k].last;}for(int i=0;i<j1;i++){if(i!=j1-1) printf("%05d %d %05d\n",list1[i],h[list1[i]].num,list1[i+1]);else printf("%05d %d -1\n",list1[i],h[list1[i]].num);}for(int i=0;i<j2;i++){if(i!=j2-1) printf("%05d %d %05d\n",list2[i],h[list2[i]].num,list2[i+1]);else printf("%05d %d -1\n",list2[i],h[list2[i]].num);}return 0;
}

L2-004 这是二叉搜索树吗？

#include<bits/stdc++.h>
using namespace std;const int N=1100;
int a[N];
int post[N];
int k=0;
int cnt=0;
bool B=0;void check(int l,int r){//cout<<l<<" r="<<r<<endl;if(l>r){//post[k++]=a[l];return;}int i=l+1,j=r;//3 2int root = a[l];//5if(!B){while(a[i]<root&&i<=r) i++;while(a[j]>=root&&j>l) j--;}else{while(a[i]>=root&&i<=r) i++;while(a[j]<root&&j>l) j--;}if(i-j!=1) return;check(l+1,j);check(j+1,r);cnt++;//cout<<root<<endl;post[k++]=root;
}int main(){int n;cin>>n;for(int i=1;i<=n;i++) cin>>a[i];check(1,n);if(cnt!=n){B=1;cnt=0;check(1,n);}if(cnt!=n) cout<<"NO";else{cout<<"YES"<<endl;cout<<post[0];for(int i=1;i<n;i++) cout<<" "<<post[i];}return 0;
}

L2-005 集合相似度

#include<bits/stdc++.h>
using namespace std;set<int> v[100];
set<int>::iterator it;int main(){int n;cin>>n;for(int i=1;i<=n;i++){int k;cin>>k;while(k--){int x;cin>>x;v[i].insert(x);}}int k;cin>>k;while(k--){int x,y;cin>>x>>y;set<int> st;double ans=0;for(it=v[x].begin();it!=v[x].end();it++){if(v[y].find(*it) != v[y].end()) ans++;}ans/=v[x].size()+v[y].size()-ans;printf("%.2f%\n",ans*100);//cout<<ans<<endl;}return 0;
}

L2-006 树的遍历

#include<bits/stdc++.h>
using namespace std;const int N=50;
int post[N],in[N];
map<int,int> c;void solve(int root,int l,int r,int idx){if(l>r) return;int i=l;while(i<r&&in[i]!=post[root]) i++;c[idx]=post[root];solve(root-r+i-1,l,i-1,idx*2);solve(root-1,i+1,r,idx*2+1);
}int main(){int n;cin>>n;for(int i=1;i<=n;i++) cin>>post[i];for(int i=1;i<=n;i++) cin>>in[i];solve(n,1,n,1);auto it = c.begin();printf("%d",it->second);it++;for(it;it!=c.end();it++){printf(" %d",it->second);}return 0;
}

L2-007 家庭房产

#include<bits/stdc++.h>
using namespace std;const int N = 20000;
int f[N],minn[N],homes[N],homev[N],siz[N];
int nums[N],v[N];int find(int x){if(x==f[x]) return x;return f[x]=find(f[x]);
}void merge(int x,int y){x=find(x),y=find(y);if(x==y) return; minn[y] = min(minn[x],minn[y]);f[x]=y;homes[y]+=homes[x];homev[y]+=homev[x];siz[y]+=siz[x];
}struct hh{int min_num;int sum;double ave_homes;double ave_homev;
}ans[N];bool cmp(hh x,hh y){if(x.ave_homev==y.ave_homev) return x.min_num<y.min_num;return x.ave_homev>y.ave_homev;
}int main(){int n;cin>>n;for(int i=0;i<=12000;i++) f[i]=i,minn[i]=i,siz[i]=1;int m=0;for(int i=0;i<n;i++){int num,fa,mo,k,hms,hmv;cin>>num>>fa>>mo>>k;nums[m++]=num;if(fa!=-1) merge(fa,num);if(mo!=-1) merge(mo,num);while(k--){int x;cin>>x;merge(x,num);}num=find(num);cin>>hms>>hmv;//cout<<num<<" "<<minn[num]<<" "<<homes[num]<<" "<<homev[num]<<endl;homes[num] += hms;homev[num] +=hmv;//cout<<num<<" "<<minn[num]<<" "<<homes[num]<<" "<<homev[num]<<endl;}m=0;for(int i=0;i<n;i++){int k = find(nums[i]);if(!v[k]){v[k]=1;ans[m++]={minn[k],siz[k],(double)homes[k]/siz[k],(double)homev[k]/siz[k]};}}sort(ans,ans+m,cmp);cout<<m<<endl;for(int i=0;i<m;i++){printf("%04d %d %.3lf %.3lf\n",ans[i].min_num,ans[i].sum,ans[i].ave_homes,ans[i].ave_homev);}return 0;
}

L2-010 排座位

#include<bits/stdc++.h>
using namespace std;const int N = 320;
int f[N];
int emy[110][110];int get(int x){if(x==f[x]) return x;return f[x]=get(f[x]);
}void merge(int x,int y){x=get(x),y=get(y);f[x] = y;
}int main(){int n,m,k;cin>>n>>m>>k;for(int i=1;i<=n*3;i++) f[i]=i;while(m--){int a,b,c;cin>>a>>b>>c;if(c==1) merge(a,b);else emy[a][b]=1,emy[b][a]=1;}while(k--){int a,b;cin>>a>>b;//cout<<get(a)<<" "<<get(b)<<" "<<emy[a][b]<<endl;if(get(a)==get(b)&&emy[a][b]!=1) cout<<"No problem"<<endl;else if(get(a)!=get(b)&&emy[a][b]==1) cout<<"No way"<<endl;else if(get(a)==get(b)&&emy[a][b]==1) cout<<"OK but..."<<endl;else cout<<"OK"<<endl;}return 0;
}

L2-011 玩转二叉树

#include<bits/stdc++.h>
using namespace std;const int N=50;
int in[N],pre[N];
map<int,int> c;void solve(int root,int l,int r,int idx){if(l>r) return;int i=l;while(i<r&&in[i]!=pre[root]) i++;c[idx]=pre[root];solve(root+1,l,i-1,idx*2+1);solve(root+i-l+1,i+1,r,idx*2);
}int main(){int n;cin>>n;for(int i=1;i<=n;i++) cin>>in[i];for(int i=1;i<=n;i++) cin>>pre[i];solve(1,1,n,1);auto it=c.begin();printf("%d",it->second);it++;for(it;it!=c.end();it++){printf(" %d",it->second);}return 0;
}

L2-012 关于堆的判断

#include<bits/stdc++.h>
using namespace std;const int N = 1100;
int h[N];void up(int x){while(x/2&&h[x/2]>h[x]){swap(h[x/2],h[x]);x/=2;}
}int getnum(string s,int k){int ans=0;for(int i=k;i<s.size();i++){if(s[i]>='0'&&s[i]<='9') ans = ans*10+s[i]-'0';}if(s[k]=='-') ans*=(-1);return ans;
}int main(){int n,m;cin>>n>>m;for(int i=1;i<=n;i++) cin>>h[i],up(i);while(m--){int x,i,j;cin>>x;for(j=1;j<=n;j++){if(h[j]==x) break;}string s;getline(cin,s);bool A=0;if(s[1]=='a'){int num = getnum(s,5);for(i=1;i<=n;i++){if(h[i]==num) break;}if(abs(i-j)==1) A=1;}else{if(s[8]=='r'){if(j==1) A=1;}else if(s[8]=='p'){int num = getnum(s,18);for(i=1;i<=n;i++){if(h[i]==num) break;}if(h[i/2]==h[j]) A=1;}else{int num = getnum(s,15);for(i=1;i<=n;i++){if(h[i]==num) break;}if(h[i*2]==h[j]||h[i*2+1]==h[j]) A=1;}} //cout<<x<<endl;if(A) cout<<'T'<<endl;else cout<<'F'<<endl;}return 0;
}

L2-013 红色警报

#include<bits/stdc++.h>
using namespace std;const int N = 550;
int g[N][N],v[N];
int n,m;void gdfs(int x){v[x]=1;for(int i=0;i<n;i++){if(!v[i]&&g[x][i]) gdfs(i);}
}int dfs(){int cnt=0;memset(v,0,sizeof v);for(int i=0;i<n;i++){if(!v[i]){cnt++;gdfs(i);}}return cnt;
}bool check(int x){int a = dfs();for(int i=0;i<n;i++) g[x][i]=g[i][x]=0;int b = dfs();if(b-a<=1) return 1;else return 0;
}int main(){cin>>n>>m;while(m--){int x,y;cin>>x>>y;g[x][y]=g[y][x]=1;}int k;cin>>k;for(int i=0;i<k;i++){int x;cin>>x;bool A=check(x);if(A) cout<<"City "<<x<<" is lost."<<endl;else cout<<"Red Alert: City "<<x<<" is lost!"<<endl;}if(k==n) cout<<"Game Over.";return 0;
}

L2-014 列车调度

#include<bits/stdc++.h>
using namespace std;int main(){int n;cin>>n;set<int> st;while(n--){int x;cin>>x;auto it = st.lower_bound(x);if(it!=st.end()){st.erase(*it);}st.insert(x);}cout<<st.size();
}

L2-016 愿天下有情人都是失散多年的兄妹

#include<bits/stdc++.h>
using namespace  std;const int N = 110000;
struct hh{char sex;int fa,mo;
}h[N];void check(int x,set<int> &st,int cnt){if(x==-1||cnt>5||x==0) return;st.insert(x);check(h[x].fa,st,cnt+1);check(h[x].mo,st,cnt+1);
}int main(){int n;cin>>n;for(int i=0;i<n;i++){int id;char sex;int fa,mom;cin>>id>>sex>>fa>>mom;//cout<<id<<" "<<sex<<" "<<fa<<" "<<mom<<endl;h[id]={sex,fa,mom};//1 3 4样例：未出现在输入，但出现在输出判断男女上if(fa!=-1) h[fa].sex='M';if(mom!=-1) h[mom].sex = 'F';}int k;cin>>k;while(k--){int x,y;cin>>x>>y;if(h[x].sex == h[y].sex) cout<<"Never Mind"<<endl;else{set<int> a,b;//cout<<"x="<<x<<" y="<<y<<endl;check(x,a,1);check(y,b,1);bool A=0;//cout<<a.size()<<" b.size()="<<b.size()<<endl;for(auto it = a.begin();it!=a.end();it++){//cout<<"it = "<<*it<<endl;if(b.find(*it)!=b.end()) A=1,cout<<"No"<<endl;if(A) break;}if(!A) cout<<"Yes"<<endl;}}return 0;
}

L2-019 悄悄关注

#include<bits/stdc++.h>
using namespace std;map<string,double> mp,mpp;int main(){int n,k,m=0;cin>>n;string s;while(n--){cin>>s;mp[s]=0;}cin>>n;double ans=0;for(int i=0;i<n;i++){cin>>s>>k;if(mp.find(s)!=mp.end()) ans+=k,k=0,m++;mpp[s]=k;}ans=ans/(double)m;bool A=1;for(auto i=mpp.begin();i!=mpp.end();i++){if(i->second>ans) A=0,cout<<i->first<<endl;}if(A) cout<<"Bing Mei You";return 0;
}

L2-020 功夫传人

#include<bits/stdc++.h>
using namespace std;vector<vector<int>> v;
const int N = 1e5+100;
double dedao[N];
double ans;
double n,z,r;void bfs(){queue<int>q;q.push(0);while(!q.empty()){int k=q.front();q.pop();for(int i=0;i<v[k].size();i++){int m=v[k][i];q.push(m);if(dedao[m]>1) dedao[m]=dedao[m]*dedao[k]*(1-r*0.01),ans+=dedao[m]*z;else dedao[m]=dedao[k]*(1-r*0.01);}}
}int main(){cin>>n>>z>>r;v.resize(n);if(n==1){int k,x;cin>>k>>x;cout<<z*x;return 0;}for(int i=0;i<n;i++){int k,x;cin>>k;dedao[i]=1;if(k==0) cin>>x,dedao[i]=x;else{while(k--) cin>>x,v[i].push_back(x);}}bfs();cout<<(long long)ans;return 0;
}

L2-025 分而治之

#include<bits/stdc++.h>
using namespace std;const int N=1e4+100;
int h[N],e[N*2],ne[N*2],idx=0;
int a[N];
int n,m;void add(int a,int b){e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}bool check(){bool A=1;for(int i=1;i<=n;i++){if(a[i]) continue;for(int j=h[i];j!=-1;j=ne[j]){int k=e[j];if(!a[k]){//cout<<i<<endl;A=0;break;}}}return A;
}int main(){cin>>n>>m;memset(h,-1,sizeof h);for(int i=0;i<m;i++){int x,y;cin>>x>>y;add(x,y),add(y,x);}int k;cin>>k;while(k--){int v,x;cin>>v;memset(a,0,sizeof a);for(int i=0;i<v;i++)cin>>x,a[x]=1;if(check()) cout<<"YES"<<endl;else cout<<"NO"<<endl;}return 0;
}

L2-026 小字辈

#include<bits/stdc++.h>
using namespace std;const int N = 1e5+100;
vector<vector<int>> v;
int a[N],bei[N],maxx,maxn;void bfs(){queue<int> q;q.push(0);while(!q.empty()){int k=q.front();a[k]=1;q.pop();for(int j=0;j<v[k].size();j++){int m=v[k][j];if(a[m]) continue;q.push(m);bei[m]=bei[k]+1;if(bei[m]>maxx) maxx=bei[m],maxn=0;if(maxx==bei[m]) maxn++;}}
}int main(){int n,x;cin>>n;v.resize(n+1);for(int i=1;i<=n;i++){cin>>x;if(x==-1) x=0;v[i].push_back(x);v[x].push_back(i);}bfs();cout<<maxx<<endl;for(int i=1;i<=n;i++)if(bei[i]==maxx){cout<<i;maxn--;if(maxn!=0) cout<<" ";}
}

L2-029 特立独行的幸福

#include<bits/stdc++.h>
using namespace std;const int N=1e4;
int v[N];
map<int,int> ans;bool isprim(int x){bool A=1;for(int i=2;i*i<=x;i++)if(x%i==0){A=0;break;}return A;
}int main(){int a,b;cin>>a>>b;for(int i=a;i<=b;i++){set<int> st;int n=i;while(n!=1){int num=0;while(n){int k=n%10;num+=k*k;n/=10;}if(st.find(num)!=st.end()) break;st.insert(num);n=num;v[num]=1;}if(n==1) ans[i]=st.size();}if(!ans.size()) cout<<"SAD";else{for(auto it=ans.begin();it!=ans.end();it++){int k = it->first;if(v[k]) continue;if(isprim(k)) cout<<k<<" "<<2*(it->second);else cout<<k<<" "<<it->second;cout<<endl;}}return 0;
}

L2-031 深入虎穴

#include<bits/stdc++.h>
using namespace std;int n;
vector<vector<int>> v1,v2;
int str=-1,endd=0;void bfs(vector<vector<int>> v,int x){queue<int> q;q.push(x);while(!q.empty()){int k=q.front();//cout<<"k="<<k<<endl;q.pop();//if(q.empty()&&endd==-1) endd=k;if(q.empty()) str=k;for(int i=0;i<v[k].size();i++){q.push(v[k][i]);}}
}int main(){cin>>n;v1.resize(n+10);v2.resize(n+10);for(int i=0;i<n;i++){int k;cin>>k;while(k--){int x;cin>>x;v1[i+1].push_back(x);v2[x].push_back(i+1);}}bfs(v2,1);//cout<<str;bfs(v1,str);cout<<str;return 0;
}

L2-035 完全二叉树的层序遍历

#include<bits/stdc++.h>
using namespace std;const int N=50;
int n;
int post[N];void cinn(int x){if(x>n) return;cinn(x*2);cinn(x*2+1);cin>>post[x];
}int main(){cin>>n;cinn(1);for(int i=1;i<=n;i++){if(i>1) cout<<" ";cout<<post[i];}return 0;
}

L2-036 网红点打卡攻略

#include<bits/stdc++.h>
using namespace std;int n,m;
const int N=220;
int g[N][N];
int v[N],lis[N];int main(){cin>>n>>m;while(m--){int a,b,c;cin>>a>>b>>c;g[a][b]=g[b][a]=c;}int k;cin>>k;int ans=0,minn=0x3f3f3f3f,w;for(int j=1;j<=k;j++){memset(v,0,sizeof v);int x;cin>>x;bool A=0;int num=0;for(int i=1;i<=x;i++){cin>>lis[i];if(!v[lis[i]]) v[lis[i]]=1,num++;else A=1;}if(A||num!=n) continue;if(!g[0][lis[1]]||!g[0][lis[x]]) continue;int sum=0;sum+=g[0][lis[1]];for(int i=2;i<=n;i++){if(!g[lis[i-1]][lis[i]]) sum+=0x3f3f3f3f;sum+=g[lis[i-1]][lis[i]];}sum+=g[lis[n]][0];if(minn>sum){minn=sum;w=j;}//cout<<j<<" "<<sum<<" "<<minn<<endl;ans++;}cout<<ans<<endl;cout<<w<<" "<<minn;return 0;
}

L2-038 病毒溯源

#include<bits/stdc++.h>
using namespace std;int n;
const int N=1e4+100;
vector<int> v[N];
int a[N];
vector<int> temp,ans;void dfs(int x){if(temp.size()<ans.size()){temp.clear();temp=ans;}for(int i=0;i<v[x].size();i++){ans.push_back(v[x][i]);dfs(v[x][i]);ans.pop_back();}
}int main(){cin>>n;for(int i=0;i<n;i++){int k;cin>>k;while(k--){int x;cin>>x;v[i].push_back(x);a[x]=1;}if(v[i].size()) sort(v[i].begin(),v[i].end());}for(int i=0;i<n;i++){if(!a[i]){ans.push_back(i);dfs(i);}}cout<<temp.size()<<endl;for(int i=0;i<temp.size();i++){if(i) cout<<" ";cout<<temp[i];}return 0;
}

L2-039 清点代码库

#include <bits/stdc++.h>
using namespace std;
int n, m, t;
vector<int> temp;
map<vector<int>, int> A;
multimap<int, vector<int>, greater<int> > B;
int main() {scanf("%d%d", &n, &m);temp.resize(m);for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) scanf("%d", &temp[j]);A[temp]++;}for (auto it : A) B.insert({it.second, it.first});printf("%d\n", A.size());for (auto it : B) {printf("%d", it.first);for (auto it2 : it.second) printf(" %d", it2);printf("\n");}return 0;
}

L2-040 哲哲打游戏

#include<bits/stdc++.h>
using namespace std;
const int N=100004;
vector<int> v[N];
int dan[N],p=1;
int main()
{int n,m;cin>>n>>m;for(int i=1;i<=n;++i){int k;cin>>k;while(k--){int x;cin>>x;v[i].push_back(x);}}while(m--){int x,y;cin>>x>>y;if(x==0){p=v[p][y-1];}else if(x==1){dan[y]=p;cout<<p<<endl;}else {p=dan[y];}}cout<<p;return 0;
}

L2-042 老板的作息表

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int main()
{int n;cin>>n;vector<pair<string,string>> s;for(int i=0;i<n;i++){string a,b,c;cin>>a>>c>>b; s.push_back({a,b});}sort(s.begin(),s.end());string la="-1";for(auto &p:s){if(la=="-1"){la=p.second;if(p.first!="00:00:00")cout<<"00:00:00 - "<<p.first<<endl;}else{if(la!=p.first) cout<<la<<" - "<<p.first<<endl;la=p.second;}}if(la!="23:59:59") cout<<la<<" - 23:59:59"<<endl;return 0;
}