【2021团体程序设计天梯赛】L2部分（PTA，L2-037到L2-040）题解代码&复盘
【摘要】
概述
都是模拟，没啥好说的。T1注意轨道空了的时候按钮没反应的，考场一遍过了复盘的时候给忘了改了好久。T2题目没说清楚可以从任意节点出发，以为只有0出发改了好久最后都没改出来，最后只拿了17分，不然就国...
概述
- 都是模拟，没啥好说的。
- T1注意轨道空了的时候按钮没反应的，考场一遍过了复盘的时候给忘了改了好久。
- T2题目没说清楚可以从任意节点出发，以为只有0出发改了好久最后都没改出来，最后只拿了17分，不然就国二了，复盘的时候套个循环就A了，害。另外补充了一种并查集的解法。
- T3用STL模拟，30行就可以敲出来，考场的时候因为忘记输出最开始的长度4，然后交上去一直全WA，想了好久没想出来qaq
- T4就是建个图直接模拟就行，好像去年也有这种题。
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;
}
- 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
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;
}
- 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
- 53
- 54
//给出一棵树，求最长链
//并查集不要路径压缩，统计每个点所在的链 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;
}
- 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
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
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;
}
- 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
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;
}
- 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
文章来源: gwj1314.blog.csdn.net，作者：小哈里，版权归原作者所有，如需转载，请联系作者。
原文链接：gwj1314.blog.csdn.net/article/details/116176841
【版权声明】本文为华为云社区用户转载文章，如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱：
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论（0）