【2021团体程序设计天梯赛】L2部分（PTA，L2-037到L2-040）题解代码

概述

• 都是模拟，没啥好说的。

L2-037 包装机 25 69 257 0.27
L2-038 病毒溯源 25 72 277 0.26
L2-039 清点代码库 25 47 487 0.10
L2-040 哲哲打游戏 25 39 223 0.17

L2-037 包装机 (25分)

#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e4+10;
string ss[1010];
int f[1010];
int main(){
    int n, m, s;
    cin>>n>>m>>s;
    for(int i = 1; i <= n; i++){
        cin>>ss[i];
    }
    stack<char>stk;
    int x;  
    while(cin>>x && x!=-1){
        if(x==0){
            if(stk.size()==0){
                continue;
            }
            cout<<stk.top(); stk.pop();
        }else{
            if(f[x]>=ss[x].size())continue;
            if(stk.size()==s){
                cout<<stk.top();  stk.pop();
                //if(f[x]<ss[x].size())
                //    stk.push(ss[x][f[x]++]);
            }
            //if(f[x]<ss[x].size())
                stk.push(ss[x][f[x]++]);
        }
    }
    return 0;
}

L2-038 病毒溯源 (25分)

#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e4+10;
vector<int>G[maxn];
int ans = 0, ans2=0, root=0;
void dfs(int u, int h){
    ans = max(ans,h);
    for(int v:G[u]){
        dfs(v,h+1);
    }
}

int ok = 0;
vector<int>vc;
void dfs2(int u,int h){
    if(ok==1)return ;
    if(h==ans2 && ok==0){
        ok = 1;
        for(int i = 0; i < ans2; i++){
            if(i!=0)cout<<" "<<vc[i];
            else cout<<vc[i];
        }
        return ;
    }
    for(int v:G[u]){
        vc.push_back(v);
        dfs2(v,h+1);
        vc.pop_back();
    }
}

int main(){
    int n;  cin>>n;
    for(int i = 0; i < n; i++){
        int k;  cin>>k;
        for(int j = 0; j < k; j++){
            int x;  cin>>x;
            G[i].push_back(x);
        }
        if(G[i].size()!=0)sort(G[i].begin(),G[i].end());
    }
    for(int i = 0; i < n; i++){
        dfs(i,1);
        if(ans>ans2){
            ans2 = ans; root = i;
        }
    }
    
    cout<<ans2<<"\n";
    vc.push_back(root);
    dfs2(root,1);
    return 0;
}

//给出一棵树，求最长链
//并查集不要路径压缩，统计每个点所在的链 ps. 可以不是从0开始
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5+10;

int fa[maxn+10];
inline void init(int n){for(int i = 0; i < n; i++)fa[i]=i;}
inline int find(int x){return x==fa[x]?x:find(fa[x]);}
inline void merge(int x, int y){ if(x!=y)fa[y] = x;}

int cc[maxn+10];
inline int size(int x){//TLE5
    int ans = 1;
    while(x!=fa[x])x=fa[x],ans++;
    return ans;
}
bool cmp(vector<int>a, vector<int>b){
    for(int i = 0; i < a.size(); i++)
        if(a[i]!=b[i])return a[i]<b[i];
}
int main(){
    int n;  cin>>n;  init(n);
    for(int i = 0; i < n; i++){
        int k;  scanf("%d",&k);
        for(int j = 1; j <= k; j++){
            int x;  scanf("%d",&x);
            merge(i,x);
        }
    }
    //先找最长链
    int len = 1;
    for(int i = 0; i < n; i++){
        cc[i] = size(i);
        len = max(len, cc[i]);
    }
    //存储所有路径，排序输出最短
    vector<vector<int> >ans;
    for(int i = 0; i < n; i++){
        if(cc[i]!=len)continue;
        vector<int>vc;
        int x = i;
        while(x!=fa[x]){
            vc.push_back(x);
            x = fa[x];
        }
        vc.push_back(x);
        reverse(vc.begin(),vc.end());
        ans.push_back(vc);
    }
    sort(ans.begin(),ans.end(),cmp);
    //cout<<ans[0].size()<<"\n"; TLE5
    int nn = ans[0].size();
    printf("%d\n",nn);
    for(int i = 0; i < nn; i++){
        if(i!=0)printf(" %d",ans[0][i]);
        else printf("%d",ans[0][i]);
    }
    return 0;
}

L2-039 清点代码库 (25分)

#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e4+10;
bool cmp(pair<vector<int>, int> a, pair<vector<int>, int> b){
    if(a.second!=b.second)return a.second>b.second;
    for(int i = 0; i < a.first.size(); i++){
        if(a.first[i]!=b.first[i])
            return a.first[i]<b.first[i];
    }
}
int main(){
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int n, m;  cin>>n>>m;
    map<vector<int>, int>ma;
    for(int i = 1; i <= n; i++){
        vector<int>vc;
        for(int j = 1; j <= m; j++){
            int x;  cin>>x;  vc.push_back(x);
        }
        ma[vc]++;
    }
    vector<pair<vector<int>, int> >vc(ma.begin(), ma.end());
    sort(vc.begin(),vc.end(), cmp);
    cout<<vc.size()<<"\n";
    for(int i = 0; i < vc.size(); i++){
        cout<<vc[i].second;
        for(int j = 0; j < vc[i].first.size(); j++){
            cout<<" "<<vc[i].first[j];
        }
        cout<<"\n";
    }
    return 0;
}

L2-040 哲哲打游戏 (25分)

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5+10;
vector<int>G[maxn];
int back[110];
int main(){
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int n, m;  cin>>n>>m;
    for(int i = 1; i <= n; i++){
        int k;  cin>>k;
        for(int j = 1; j <= k; j++){
            int x;  cin>>x;
            G[i].push_back(x);
        }
    }
    int now = 1;
    for(int i = 1; i <= m; i++){
        int op, x;  cin>>op>>x;
        if(op==0){
            now = G[now][x-1];
        }else if(op==1){
            back[x] = now;
            cout<<now<<"\n";
        }else{
            now = back[x];
        }
    }
    cout<<now<<"\n";
    return 0;
}