天梯赛数据结构合集

1.集合操作：PTA | 程序设计类实验辅助教学平台

主要是注意set的取交集操作，AC代码：

#include<bits/stdc++.h>
using namespace std;
int n,m,k;
set<int> a[60];
int main(){cin>>n;for(int i=1;i<=n;i++){cin>>m;for(int j=1;j<=m;j++){int x;cin>>x;a[i].insert(x);}}cin>>k;for(int i=1;i<=k;i++){int u,v;cin>>u>>v;set<int> ss;set_intersection(a[u].begin(), a[u].end(),a[v].begin(), a[v].end(),inserter(ss,ss.begin()));double cnt=ss.size();printf("%.2lf",cnt/(a[u].size()+a[v].size()-cnt)*100.0);cout<<"%"<<endl;}
}

2.map+vector:PTA | 程序设计类实验辅助教学平台

一开始以为是一道水题，但是后来发现虽然意思简单，但是实现方式还是蛮有意义的，我们可以开一个map，利用vcetor作为key，再通过for(auto &s:map)即可遍历map，得到答案。AC代码如下：

#include<bits/stdc++.h>
using namespace std;const int N = 10010, M = 110;
map<vector<int>, int> cnt;
vector<pair<int, vector<int> > > ans;
int n, m;int main()
{scanf("%d%d", &n, &m);for (int i = 0; i < n; i++){vector<int> temp;for (int j = 0; j < m; j++){int x;scanf("%d", &x);temp.push_back(x);}cnt[temp]++;}for (auto &u : cnt) ans.push_back({ -u.second, u.first });//for (auto &[u, v] : cnt) ans.push_back({ -v, u });//C++新特性，PTA不支持sort(ans.begin(), ans.end());printf("%d\n", cnt.size());for (auto &u : ans){printf("%d", -u.first);for (auto &v : u.second)printf(" %d", v);puts("");}

3.并查集：PTA | 程序设计类实验辅助教学平台

非常有意思的一道题，只要观察到一点就非常容易了，也就是最短路是2*(节点数-1)-最长链的长度，证明非常容易，只是要想注意到还是需要多画图模拟，知道了这个后那就是常规的dfs预处理+并查集维护了，下面是AC代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m,die[200010],dep[200010],fa[200010],siz[200010],hh=0;
vector<int> edge[200010];
int find(int u){if(fa[u]==u) return u;return fa[u]=find(fa[u]);
}
void merge(int u,int v){if(find(u)==find(v)) return;siz[find(v)]+=siz[find(u)];fa[find(u)]=find(v);
}
void dfs(int x,int cnt){dep[x]=cnt;for(int i=0;i<edge[x].size();i++){dfs(edge[x][i],cnt+1);}
}
signed main(){cin>>n>>m;int root=-1;for(int i=1;i<=n;i++){fa[i]=i;siz[i]=1;cin>>die[i];if(die[i]!=-1){edge[die[i]].push_back(i);}if(die[i]==-1) root=i;}dfs(root,0);int ans=0;while(m--){int x;cin>>x;if(find(x)==root){if(m>0) cout<<ans<<endl;else cout<<ans;}else{//找到最近的int pos=x,cnt=0;hh=max(hh,dep[pos]);while(find(pos)!=root){merge(pos,root);pos=die[pos];}ans=2*siz[root]-2-hh;if(m>0) cout<<ans<<endl;else cout<<ans;}}
}

4.线段树：PTA | 程序设计类实验辅助教学平台

PTA目前唯一一道做到的权值线段树，配合上堆模拟即可，下面是AC代码：

#include<bits/stdc++.h>
using namespace std;
struct node{int ln,rn,sum;
}tr[2001000];
stack<int> S;
int n;
void build(int l,int r,int root){tr[root].ln=l;tr[root].rn=r;tr[root].sum=0;if(l==r) return;int mid=(l+r)/2;build(l,mid,root<<1);build(mid+1,r,root<<1|1);
}
int query(int val,int root){int l=tr[root].ln,r=tr[root].rn;int mid =l+r>>1;if(l==r) return l;int ans;if(tr[root<<1].sum>=val) ans=query(val,root<<1);else ans=query(val-tr[root<<1].sum,root<<1|1);return ans;
}
void update(int pos,int val,int root){int l=tr[root].ln;int r=tr[root].rn;if(l==r){tr[root].sum+=val;return;}int mid=l+r>>1;if(pos<=mid) update(pos,val,root<<1);else update(pos,val,root<<1|1);tr[root].sum=tr[root<<1].sum+tr[root<<1|1].sum;
}
int main(){cin>>n;build(1,1e5+10,1);while(n--){string tmp;cin>>tmp;if(tmp=="Push"){int val;scanf("%d",&val);S.push(val);update(val,1,1);}else if(tmp=="PeekMedian"){if(S.size()==0) printf("Invalid\n");else{int k=(S.size()+1)/2;printf("%d\n",query(k,1));}}else if(tmp=="Pop"){if(S.size()==0) printf("Invalid\n");else{int val=S.top();S.pop();printf("%d\n",val);update(val,-1,1);}}}
}

5.并查集：PTA | 程序设计类实验辅助教学平台

我们对每一个爱好开一个vcetor，存有这个爱好的人，然后遍历vector进行合并即可，下面是AC代码：

#include<bits/stdc++.h>
using namespace std;
int fa[200010],n;
int siz[200010];
vector<int> like[1001];
int find(int x){if(x==fa[x]) return x;return find(fa[x]);
}
void merge(int u,int v){if(find(u)==find(v)) return;siz[find(v)]+=siz[find(u)];fa[find(u)]=find(v);
}
int change(string s){int num=0;for(int i=0;i<s.size()-1;i++){num=10*num+s[i]-'0';}return num;
}
int main(){cin>>n;for(int i=1;i<=n;i++) fa[i]=i;for(int i=1;i<=n;i++) siz[i]=1;for(int i=1;i<=n;i++){string s;cin>>s;int k;k=change(s);int w;for(int j=1;j<=k;j++){cin>>w;like[w].push_back(i);}}for(int i=1;i<=1000;i++){for(int j=1;j<like[i].size();j++){merge(like[i][j],like[i][j-1]);}}vector<int> ans;int cnt=0;for(int i=1;i<=n;i++){if(fa[i]==i){cnt++;ans.push_back(siz[i]);}}int www=ans.size();sort(ans.begin(),ans.end());cout<<cnt<<endl;for(int i=ans.size()-1;i>=1;i--) cout<<ans[i]<<" ";cout<<ans[0];
}

6.拓扑排序：PTA | 程序设计类实验辅助教学平台

一道比较好的拓扑排序好题，我们按照字典序关系建好图再拓扑一下即可，这里有一个比较有意思的trick是他用优先队列，保证了字典序，下面是AC代码：

#include<bits/stdc++.h>
using namespace std;
int cnt,head[100010],ver[200010],nxt[200010];
void add(int u,int v){ver[++cnt]=v;nxt[cnt]=head[u];head[u]=cnt;
}
unordered_map<string,int> ID;
unordered_map<int,string> findbyID;
int n,strtot;
int ind[200010];
typedef pair<string,int> node;
vector<string> ans;
int main(){cin>>n;for(int i=0;i<=100000;i++) head[i]=-1;vector<string> pre,now;for(int i=1;i<=n;i++){string str;cin>>str;for(int p=0;p<str.size();p++){string nows;while(p<str.size()&&str[p]!='.') nows+=str[p++];if(ID[nows]==0){ID[nows] = ++strtot;findbyID[strtot] = nows;}now.push_back(nows);}if(pre.size()==now.size()){int p=0;while(pre[p]==now[p]) p++;add(ID[pre[p]],ID[now[p]]);ind[ID[now[p]]]++;}pre.swap(now);now.clear();}priority_queue<node, vector<node>, greater<node>> q;for(auto& [str, id] : ID) {if(!ind[id]) q.emplace(str, id);}while(!q.empty()){ans.push_back(q.top().first);int u=q.top().second;q.pop();for(int i=head[u];i!=-1;i=nxt[i]){int v=ver[i];ind[v]--;if(!ind[v]) q.push({findbyID[v],v});}}cout<<ans[0];for(int i=1;i<ans.size();i++) cout<<"."<<ans[i];
}