2021天梯赛决赛补题报告

L2-1 包装机 (25 分)

1.题解

　　轨道用队列存，筐用栈存，按题意模拟即可。

2.代码

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int maxn = 1e3 + 5;
 4 int n, m, k;
 5 queue<char> que[maxn];
 6 stack<char> s;
 7 int main() {
 8     cin >> n >> m >> k;
 9     for(int i = 1; i <= n; i++) {
10         for(int j = 1; j <= m; j++) {
11             char c;
12             cin >> c;
13             que[i].push(c);
14         }
15     }
16         
17     int x;
18     while(cin >> x) {
19         if(x == -1)
20             break;
21         if(!x) {
22             if(!s.empty()) {
23                 cout << s.top();
24                 s.pop();
25             }
26         } else {
27             if(que[x].empty())
28                 continue;
29             if(s.size() == k) {
30                 cout << s.top();
31                 s.pop();
32             }
33             s.push(que[x].front());
34             que[x].pop();
35         }
36     }
37     
38     return 0;
39 }

View Code

L2-2 病毒溯源 (25 分)

1.题解

　　用vector数组存后代，dfs搜出每个病毒的最大感染长度，排序后，如果找到头，直接搜回去，记录最长序列。

2.代码

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int N = 10007;
 4 int n, m, dis[N], f[N], p;
 5 int maxn = -1;
 6 int a[N];
 7 int g = 0;
 8 vector<int> v[N];
 9 bool cmp(int a, int b) {
10     if(dis[a] == dis[b]) return a < b;
11     return dis[a] > dis[b];
12 }
13 int dfs(int x) {
14     if(dis[x]) {
15         return dis[x];
16     }
17     if(!v[x].size()) {
18         return dis[x] = 1;
19     }
20     int ret = 0;
21     for(int i = 0;i < v[x].size(); i++) {
22         ret = max(ret, dfs(v[x][i]) + 1);
23     }
24     return ret;
25 }
26 void cz(int p) {        
27         a[g] = p;
28         g++;
29         if(v[p].size() != 0) {
30             cz(v[p][0]);
31         }        
32 }
33 int main() {
34     scanf("%d", &n);
35     for(int i = 0; i < n; i++) {
36         scanf("%d", &m);
37         for(int j = 0; j < m; j++) {
38             int x;
39             scanf("%d", &x);
40             f[x] = 1;
41             v[i].push_back(x);
42         }
43     }
44     
45     for(int i = 0;i < n; i++) {
46         if(f[i] == 0) {
47             p = f[i];
48         }
49         dis[i] = dfs(i);
50         maxn = max(maxn, dis[i]);
51     }
52     cout << maxn << endl;
53     for(int i = 0; i < n; i++) {
54         sort(v[i].begin(), v[i].end(), cmp);
55     }
56     for(int i = 0;i < n; i++) {
57         if(maxn == dis[i]) {
58             cz(i);
59             break;
60         }
61     }
62     for(int i = 0; i < g; i++) {
63         if(i == 0) {
64             cout << a[i];
65         } else {
66             cout << " " << a[i];
67         }
68     }
69     cout << endl;
70     
71     return 0;
72 }

View Code