2021/4/24团队设计天梯赛L2题目集及题解_团队设计天梯赛题目及答案大全

2021/4/24团队设计天梯赛L2题目集及题解：

以下题解都是通过PTA测试的，大致保证正确性：
查看题目戳此：：PTA题目集

L2-01 包装机(25分)

题目描述：
一种自动包装机的结构如图 1 所示。首先机器中有 N 条轨道，放置了一些物品。轨道下面有一个筐。当某条轨道的按钮被按下时，活塞向左推动，将轨道尽头的一件物品推落筐中。当 0 号按钮被按下时，机械手将抓取筐顶部的一件物品，放到流水线上。图 2 显示了顺序按下按钮 3、2、3、0、1、2、0 后包装机的状态。

一种特殊情况是，因为筐的容量是有限的，当筐已经满了，但仍然有某条轨道的按钮被按下时，系统应强制启动 0 号键，先从筐里抓出一件物品，再将对应轨道的物品推落。此外，如果轨道已经空了，再按对应的按钮不会发生任何事；同样的，如果筐是空的，按 0 号按钮也不会发生任何事。

现给定一系列按钮操作，请你依次列出流水线上的物品。

输入格式：
输入第一行给出 3 个正整数 N（≤100）、M（≤1000）和 S​max（≤100），分别为轨道的条数（于是轨道从 1 到 N 编号）、每条轨道初始放置的物品数量、以及筐的最大容量。随后 N 行，每行给出 M 个英文大写字母，表示每条轨道的初始物品摆放。

最后一行给出一系列数字，顺序对应被按下的按钮编号，直到 −1 标志输入结束，这个数字不要处理。数字间以空格分隔。题目保证至少会取出一件物品放在流水线上。

输出格式：
在一行中顺序输出流水线上的物品，不得有任何空格。

输入样例：

3 4 4
GPLT
PATA
OMSA
3 2 3 0 1 2 0 2 2 0 -1
1
2
3
4
5

输出样例：

MATA
1

代码：每一个轨道上的用string存储，用STL中的stack模拟,删除轨道物品的时候,调用erase函数，只不过要注意上面的黑体字，在按下按钮时需要判断一些条件

#include <iostream>
#include <stack>
#include <vector>
using namespace std;
int main(){
    int n,m,smax;
    cin >> n >> m >> smax;
    //存储轨道物品
    vector<string> p(n+1);
    for(int i=1;i<=n;i++) cin >> p[i];
    //栈模拟框
    stack<char> s;
    //存储结果
    string a;
    while(cin >> n && n!=-1){
          //判断轨道是否还有物品
          if(n&&p[n].size()){
              //框满的时候
              if(s.size()>=smax)
              {a+=s.top(); s.pop();}
              s.push(p[n][0]);
              //清除对应轨道的第一个物品
              p[n].erase(p[n].begin());
          }
          else if(n==0){
               //框不为空
              if(s.size()){
                  a+=s.top(); s.pop();
              }
          }
    }
    cout << a;
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

L2-02 病毒溯源 (25 分)

题目描述：
病毒容易发生变异。某种病毒可以通过突变产生若干变异的毒株，而这些变异的病毒又可能被诱发突变产生第二代变异，如此继续不断变化。

现给定一些病毒之间的变异关系，要求你找出其中最长的一条变异链。

在此假设给出的变异都是由突变引起的，不考虑复杂的基因重组变异问题 —— 即每一种病毒都是由唯一的一种病毒突变而来，并且不存在循环变异的情况。

输入格式：
输入在第一行中给出一个正整数 N（≤10^​4），即病毒种类的总数。于是我们将所有病毒从 0 到 N−1 进行编号。

随后 N 行，每行按以下格式描述一种病毒的变异情况：

k 变异株1 …… 变异株k

其中 k 是该病毒产生的变异毒株的种类数，后面跟着每种变异株的编号。第 i 行对应编号为 i 的病毒（0≤i<N）。题目保证病毒源头有且仅有一个。

输出格式：
首先输出从源头开始最长变异链的长度。

在第二行中输出从源头开始最长的一条变异链，编号间以 1 个空格分隔，行首尾不得有多余空格。如果最长链不唯一，则输出最小序列。

注：我们称序列 { a​1 ,⋯,a​n} 比序列 { b1,⋯,bn} “小”，如果存在 1≤k≤n 满足 a​i=bi对所有 i<k 成立，且 a​k<bk。

输入样例：

10
3 6 4 8
0
0
0
2 5 9
0
1 7
1 2
0
2 3 1
1
2
3
4
5
6
7
8
9
10
11

输出样例：

4
0 4 9 1
1
2

代码：这道题目可以看做一个有向图，也就是让你找最长的路径，就dfs就行了,但是要进行剪枝（就是当一个点入度不为0，那么这个点必定不是起点，因为指向该点的另一个点可以当做起点，距离更大），然后设定一个全局变量记录当前最大路径长度，一个result存储最终路径,一个now存储当前路径，从小点往大点遍历（遵守最小序列），如果有更长的点再更新。

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
int n,mx;
//邻接表存储有向图
vector<vector<int> >p;
vector<int> result;
vector<int> now;
void dfs(int a,int time){
    now.push_back(a);
    //只有大于才更新,因为顺序从小打到访问,不存在路径长度相同的更小序列
     if(time>mx){
       mx=time;
       result=now;
     }
    for(int i=0;i<(int)p[a].size();i++){
            dfs(p[a][i],time+1);
    }
    now.pop_back();
}
int main(){
    int m,k;
    cin >> n;
    //描述入度
    int q[n];
    memset(q,0,sizeof q);
    p.resize(n);
    for(int i=0;i<n;i++){
        cin >> m;
        while(m--){
            cin >> k;
            q[k]++;
            p[i].push_back(k);
        }
        //排序还是为了最小序列，保证从小到大遍历
        sort(p[i].begin(),p[i].end());
    }
    for(int i=0;i<n;i++){
     //只从入度为0的点深搜
        if(q[i]==0)
        dfs(i,1);
    }
    cout << mx <<endl;
    for(int i=0;i<result.size();i++){
        if(i)
            cout << " ";
        cout << result[i];
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

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

题目描述：

图片:

上图转自新浪微博：“阿里代码库有几亿行代码，但其中有很多功能重复的代码，比如单单快排就被重写了几百遍。请设计一个程序，能够将代码库中所有功能重复的代码找出。各位大佬有啥想法，我当时就懵了，然后就挂了。。。”

这里我们把问题简化一下：首先假设两个功能模块如果接受同样的输入，总是给出同样的输出，则它们就是功能重复的；其次我们把每个模块的输出都简化为一个整数（在 int 范围内）。于是我们可以设计一系列输入，检查所有功能模块的对应输出，从而查出功能重复的代码。你的任务就是设计并实现这个简化问题的解决方案。

输入格式：
输入在第一行中给出 2 个正整数，依次为 N（≤10^4）和 M（≤10^​2），对应功能模块的个数和系列测试输入的个数。

随后 N 行，每行给出一个功能模块的 M 个对应输出，数字间以空格分隔。

输出格式：
首先在第一行输出不同功能的个数 K。随后 K 行，每行给出具有这个功能的模块的个数，以及这个功能的对应输出。数字间以 1 个空格分隔，行首尾不得有多余空格。输出首先按模块个数非递增顺序，如果有并列，则按输出序列的递增序给出。

注：所谓数列 { A​1​​ , …, A​M } 比 { B1​​ , …, B​M} 大，是指存在 1≤i<M，使得 A1=B1，…，A​i=Bi成立，且 A​i+1>B​i+1
​​

输入样例1：

7 3
35 28 74
-1 -1 22
28 74 35
-1 -1 22
11 66 0
35 28 74
35 28 74
1
2
3
4
5
6
7
8

输出样例1：

4
3 35 28 74
2 -1 -1 22
1 11 66 0
1 28 74 35
1
2
3
4
5

代码：用map存储同一数组出现的次数，然后把map输出赋值给pair<vector,int>类型的vector，因为map不能用sort，我们要对value排序再对key排序,最后输出Vector就行了，这里用cin，cout输入输出要加ios::sync_with_stdio(false) 不然会超时

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;
typedef pair<vector<int>,int> PVI;
//自定义排序
struct cmp{
    bool operator () (const PVI& a,const PVI& b)const{
        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];
        }
        return true;
    }
};
int main(){
    ios::sync_with_stdio(false);
    int n,m;
    cin >> n >> m;
    //map容器
    map<vector<int>,int> p;
    vector<int> q;
    while(n--){
        for(int i=0;i<m;i++){
            int a;
            cin >> a;
            q.push_back(a);
        }
        if(p.count(q)) p[q]++;
        else p[q]=1;
        q.clear();
    }
    vector<PVI> s(p.begin(),p.end());
    sort(s.begin(),s.end(),cmp() );
    cout << s.size()<<endl;
    for(int i=0;i<s.size();i++){
            q=s[i].first;
            cout << s[i].second;
        for(int j=0;j<q.size();j++){
            cout <<" ";
            cout << q[j];
        }
        if(i+1!=s.size())
        cout <<endl;
    }
    return 0;
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

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

题目描述：
哲哲是一位硬核游戏玩家。最近一款名叫《达诺达诺》的新游戏刚刚上市，哲哲自然要快速攻略游戏，守护硬核游戏玩家的一切！

为简化模型，我们不妨假设游戏有 N 个剧情点，通过游戏里不同的操作或选择可以从某个剧情点去往另外一个剧情点。此外，游戏还设置了一些存档，在某个剧情点可以将玩家的游戏进度保存在一个档位上，读取存档后可以回到剧情点，重新进行操作或者选择，到达不同的剧情点。

为了追踪硬核游戏玩家哲哲的攻略进度，你打算写一个程序来完成这个工作。假设你已经知道了游戏的全部剧情点和流程，以及哲哲的游戏操作，请你输出哲哲的游戏进度。

输入格式：
输入第一行是两个正整数 N 和 M (1≤N,M≤10
​5)，表示总共有 N 个剧情点，哲哲有 M 个游戏操作。

接下来的 N 行，每行对应一个剧情点的发展设定。第 i 行的第一个数字是 K​i，表示剧情点 i 通过一些操作或选择能去往下面 K​i个剧情点；接下来有 K​i个数字，第 k 个数字表示做第 k 个操作或选择可以去往的剧情点编号。

最后有 M 行，每行第一个数字是 0、1 或 2，分别表示：

0 表示哲哲做出了某个操作或选择，后面紧接着一个数字 j，表示哲哲在当前剧情点做出了第 j 个选择。我们保证哲哲的选择永远是合法的。
1 表示哲哲进行了一次存档，后面紧接着是一个数字 j，表示存档放在了第 j 个档位上。
2 表示哲哲进行了一次读取存档的操作，后面紧接着是一个数字 j，表示读取了放在第 j 个位置的存档。
约定：所有操作或选择以及剧情点编号都从 1 号开始。存档的档位不超过 100 个，编号也从 1 开始。游戏默认从 1 号剧情点开始。总的选项数（即 ∑Ki）不超过 106 。

接下来 N 行，每行有一个实数 P​i（−1000.0<Pi<1000.0），表示一条价格记录。

输出格式：
对于每个 1（即存档）操作，在一行中输出存档的剧情点编号。

最后一行输出哲哲最后到达的剧情点编号。

输入样例1：

10 11
3 2 3 4
1 6
3 4 7 5
1 3
1 9
2 3 5
3 1 8 5
1 9
2 8 10
0
1 1
0 3
0 1
1 2
0 2
0 2
2 2
0 3
0 1
1 1
0 2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

输出样例1：

1
3
9
10
1
2
3
4

样例解释:
简单给出样例中经过的剧情点顺序：

1 -> 4 -> 3 -> 7 -> 8 -> 3 -> 5 -> 9 -> 10。

档位 1 开始存的是 1 号剧情点；档位 2 存的是 3 号剧情点；档位 1 后来又存了 9 号剧情点。

代码：简单的模拟题,不懂得多读读题，读懂了你自然就会了，事实告诉我们不要怕字多的题,说不定更好做呢，千万不要死脑筋卡一道题(博主亲测，脑瘫)

#include <iostream>
#include <vector>
using namespace std;
int main(){
    int n,m;
    cin >> n >> m;
    vector<vector<int> > p(n+1);
    for(int i=1;i<=n;i++){
        int k;
        cin >> k;
        p[i].resize(k+1);
        for(int j=1;j<=k;j++){
            cin >> p[i][j];
        }
    }
    int now=1,q[105],a,b;
    while(m--){
        cin >> a >> b;
        if(a==0)
           now=p[now][b];
        if(a==1){
            q[b]=now;
            cout << now<<endl;
        }
        if(a==2)
           now=q[b];
    }
    cout << now;
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

L2的题目集到此结束，感觉今年的L2太模拟了相比去年简单一些，如果对你有帮助留下你的赞吧！不忘初心，方得始终。