团体程序设计天梯赛-练习集

L2-002 链表去重

#include <bits/stdc++.h>
#define ios ios::sync_with_stdio(0),cin.tie(0)
#define PII pair<int,int>
typedef long long ll;
const int N=1e6+10;
const int inf=0x3f3f3f3f;using namespace std;
struct node{int data,next;
}a[N];
vector<int>ans,fw;
bool st[N];
int h,n;
void solve()
{cin>>h>>n;for(int i=0;i<n;i++){int u,v,w;cin>>u>>v>>w;a[u]={v,w};}int p=h;while(p!=-1){int x=a[p].data,next=a[p].next;if(!st[abs(x)]) {ans.push_back(p);ans.push_back(x);st[abs(x)]=1;}else{fw.push_back(p);fw.push_back(x);}p=next;}ans.push_back(-1);fw.push_back(-1);for(int i=0;i<ans.size();i+=2){if(ans[i]!=-1) printf("%05d ",ans[i]);else break;printf("%d ",ans[i+1]);if(ans[i+2]!=-1) printf("%05d\n",ans[i+2]);else printf("-1\n");}for(int i=0;i<fw.size();i+=2){if(fw[i]!=-1) printf("%05d ",fw[i]);else break;printf("%d ",fw[i+1]);if(fw[i+2]!=-1) printf("%05d\n",fw[i+2]);else printf("-1\n");}
}
signed main()
{//freopen("input.txt","r",stdin);//freopen("output.txt","w",stdout);//ios;int _t=1;//cin>>_t;while(_t--) solve();system("pause");return 0;
}

L2-004 这是二叉搜索树吗？

思路：先假设为二叉搜索树，先设isMirror=false，根据二叉搜索树的性质由先序得到后序遍历的结果，若后序遍历数组的长度小于n，则说明出现矛盾。再设isMirror=true，根据镜像二叉搜索树的性质得到后序遍历的结果，若后序遍历数组长度仍小于n，则输出NO，否则YES

#include <bits/stdc++.h>
#define ios ios::sync_with_stdio(0),cin.tie(0)
#define PII pair<int,int>
typedef long long ll;
const int N=1e6+10;
const int inf=0x3f3f3f3f;using namespace std;
int n;
bool isMirror;
vector<int>pre,post;
void dfs(int root,int tail)
{if(root>tail) return ;int i=root+1,j=tail;if(!isMirror){while(i<=tail&&pre[i]<pre[root]) i++;while(j>root&&pre[j]>=pre[root]) j--;}else{while(i<=tail&&pre[i]>=pre[root]) i++;while(j>root&&pre[j]<pre[root]) j--;}if(i-j!=1) return ;dfs(root+1,i-1);//左子树（root+1, i-1）dfs(j+1,tail);//右子树（j+1, tail）post.push_back(pre[root]);//根
}
void solve()
{cin>>n;pre.resize(n);for(int i=0;i<n;i++) cin>>pre[i];dfs(0,n-1);if(post.size()!=n){isMirror=1;post.clear();dfs(0,n-1);}if(post.size()==n){cout<<"YES\n";for(int i=0;i<n;i++)cout<<post[i]<<" \n"[i==n-1];}else cout<<"NO\n";
}
signed main()
{//freopen("input.txt","r",stdin);//freopen("output.txt","w",stdout);//ios;int _t=1;//cin>>_t;while(_t--) solve();system("pause");return 0;
}

L2-006 树的遍历

思路：根据后续遍历找根，用根去划分中序遍历的左右子树。设定下标idx表示节点在二叉树顺序遍历中的下标，将<idx, 对应的值>存入map<int, int>，利用map有序的特点即为顺序遍历的结果。

#include <bits/stdc++.h>
#define ios ios::sync_with_stdio(0),cin.tie(0)
#define PII pair<int,int>
typedef long long ll;
const int N=1e6+10;
const int inf=0x3f3f3f3f;using namespace std;
int n;
vector<int>aft,mid;
map<int,int>ans;
void dfs(int root,int start,int end,int idx)//根节点在aft中的下标 mid的遍历区间[start end] 顺序遍历的下标
{if(start>end) return ;int i=start;while(i<=end&&mid[i]!=aft[root]) i++;ans[idx]=aft[root];dfs(root-1-(end-i),start,i-1,idx*2+1);//左子树在mid的区间[start i-1]dfs(root-1,i+1,end,idx*2+2);//右子树在mid的区间[i+1 end]
}
void solve()
{cin>>n;aft.resize(n);mid.resize(n);for(int i=0;i<n;i++) cin>>aft[i];for(int i=0;i<n;i++) cin>>mid[i];dfs(n-1,0,n-1,0);auto it=ans.begin();cout<<it->second;while(++it!=ans.end()) cout<<" "<<it->second;
}
signed main()
{//freopen("input.txt","r",stdin);//freopen("output.txt","w",stdout);//ios;int _t=1;//cin>>_t;while(_t--) solve();system("pause");return 0;
}

L2-007 家庭房产

思路：两个结构体数组，一个用来存输入数据，一个用来存最终答案。使用并查集将家庭成员合并起来。st数组用来标记编号i是否有效，以便统计家族人数。对于每个节点的祖宗节点，people++统计人数。flag表示家族是否有效，以便统计家族个数。

#include <bits/stdc++.h>
#define ios ios::sync_with_stdio(0),cin.tie(0)
#define PII pair<int,int>
typedef long long ll;
const int N=1e6+10;
const int inf=0x3f3f3f3f;using namespace std;
int n;
struct DATA{int id,fid,mid,num,area;int cid[10];
}arr[N];
struct node{int id,people;double num,area;bool flag=0;
}ans[N];
int fa[N];
bool st[N];//编号i是否有效 用于统计家族人数
int find(int x)
{return fa[x]==x? x:fa[x]=find(fa[x]);
}
void merge(int a,int b)
{int faA=find(a);int faB=find(b);if(faA<faB) fa[faB]=faA;else fa[faA]=faB;
}
bool cmp(node a,node b)
{if(a.area!=b.area) return a.area>b.area;else return a.id<b.id;
}
void solve()
{cin>>n;for(int i=0;i<N;i++) fa[i]=i;for(int i=1;i<=n;i++){int k;cin>>arr[i].id>>arr[i].fid>>arr[i].mid>>k;st[arr[i].id]=1;if(arr[i].fid!=-1) {merge(arr[i].id,arr[i].fid);st[arr[i].fid]=1;}if(arr[i].mid!=-1){merge(arr[i].id,arr[i].mid);st[arr[i].mid]=1;}for(int j=1;j<=k;j++){cin>>arr[i].cid[j];st[arr[i].cid[j]]=1;merge(arr[i].id,arr[i].cid[j]);}cin>>arr[i].num>>arr[i].area;}for(int i=1;i<=n;i++)//统计家族情况{int id=find(arr[i].id);ans[id].id=id;ans[id].num+=arr[i].num;ans[id].area+=arr[i].area;ans[id].flag=1;//编号id是否有效}int cnt=0;for(int i=0;i<N;i++){if(ans[i].flag) cnt++;if(st[i]) ans[find(i)].people++;}for(int i=0;i<N;i++){if(ans[i].flag){ans[i].num=1.0*ans[i].num/ans[i].people;ans[i].area=1.0*ans[i].area/ans[i].people;}}sort(ans,ans+N,cmp);cout<<cnt<<'\n';for(int i=0;i<cnt;i++)printf("%04d %d %.3f %.3f\n",ans[i].id,ans[i].people,ans[i].num,ans[i].area);
}
signed main()
{//freopen("input.txt","r",stdin);//freopen("output.txt","w",stdout);//ios;int _t=1;//cin>>_t;while(_t--) solve();system("pause");return 0;
}

L2-032 彩虹瓶

思路：栈模拟

#include <bits/stdc++.h>
#define ios ios::sync_with_stdio(0),cin.tie(0)
#define PII pair<int,int>
typedef long long ll;
const int N=1e6+10;
const int inf=0x3f3f3f3f;using namespace std;
int n,m,k;bool check()
{stack<int>s;vector<int>v(n+1);for(int i=1;i<=n;i++)cin>>v[i];bool ok=1;int now=1,p=1;while(now<=n){if(s.size()&&s.top()==now){s.pop();now++;}else{while(p<=n&&v[p]!=now){s.push(v[p]);if(s.size()>m) return 0;p++;}if(p<=n&&v[p]==now){now++;p++;}else return 0;}}return 1;
}
void solve()
{cin>>n>>m>>k;for(int i=1;i<=k;i++){if(check()) cout<<"YES\n";else cout<<"NO\n";}
}
signed main()
{//freopen("input.txt","r",stdin);//freopen("output.txt","w",stdout);//ios;int _t=1;//cin>>_t;while(_t--) solve();system("pause");return 0;
}

L2-033 简单计算器

思路：按照题目用栈模拟

#include <bits/stdc++.h>
#define ios ios::sync_with_stdio(0),cin.tie(0)
#define PII pair<int,int>
typedef long long ll;
const int N=1e6+10;
const int inf=0x3f3f3f3f;using namespace std;
int n;
stack<int>num;
stack<char>op;
void solve()
{cin>>n;for(int i=1;i<=n;i++) {int x;cin>>x;num.push(x);}for(int i=1;i<n;i++){char x;cin>>x;op.push(x);}while(op.size()){int n1=num.top();num.pop();int n2=num.top();num.pop();char o=op.top();op.pop();if(o=='/'&&n1==0) {printf("ERROR: %d/0\n",n2);return ;}else if(o=='+') num.push(n2+n1);else if(o=='-') num.push(n2-n1);else if(o=='*') num.push(n2*n1);else if(o=='/') num.push(n2/n1);}cout<<num.top()<<'\n';
}
signed main()
{//freopen("input.txt","r",stdin);//freopen("output.txt","w",stdout);//ios;int _t=1;//cin>>_t;while(_t--) solve();system("pause");return 0;
}

L2-034 口罩发放

思路：样例输出第1 2 3行是第一天的结果，第4 5行是第二天的结果，第三天没有输出，第6行是第四天的输出。最后两行是输出记录合法（身份证是18 位的数字）且患病的人。

结构体存数据内容，模拟。

#include <bits/stdc++.h>
#define ios ios::sync_with_stdio(0),cin.tie(0)
#define PII pair<int,int>
typedef long long ll;
const int N=3e4+10;
const int inf=0x3f3f3f3f;using namespace std;
int d,p;
struct DATA{int idx;string name,id;bool f;int time;
}a[N];
map<string,int>last;
vector<DATA>ans;
map<string,bool>vis;
bool cmp(DATA a,DATA b)
{if(a.time!=b.time) return a.time<b.time;else return a.idx<b.idx;
}
bool check(string s)
{if(s.size()!=18) return 0;for(int i=0;i<18;i++)if(s[i]<'0'||s[i]>'9') return 0;return 1;
}
void solve()
{cin>>d>>p;for(int i=1;i<=d;i++){int t,s;cin>>t>>s;for(int j=0;j<t;j++){a[j].idx=j;cin>>a[j].name>>a[j].id>>a[j].f;int h,m;scanf("%d:%d",&h,&m);int t=h*60+m;a[j].time=t;if(check(a[j].id)&&!last.count(a[j].id)) last[a[j].id]=-30;if(check(a[j].id)&&a[j].f&&!vis[a[j].id]){ans.push_back(a[j]);vis[a[j].id]=1;}}sort(a,a+t,cmp);for(int j=0;j<t;j++){if(s&&check(a[j].id)&&i-last[a[j].id]>=(p+1)){s--;cout<<a[j].name<<' '<<a[j].id<<'\n';last[a[j].id]=i;}}}for(int i=0;i<ans.size();i++)cout<<ans[i].name<<' '<<ans[i].id<<'\n';
}
signed main()
{//freopen("input.txt","r",stdin);//freopen("output.txt","w",stdout);//ios;int _t=1;//cin>>_t;while(_t--) solve();system("pause");return 0;
}

L2-035 完全二叉树的层序遍历

思路：已知后序遍历的结果，按照后序遍历的规则（左右根）去dfs，将后序遍历的元素存到对应的下标处。

#include <bits/stdc++.h>
#define int long long
const int N=40;
using namespace std; 
int n;
int a[N]; 
int ans[N],cnt=1;
void dfs(int idx)
{if(idx>n) return ;dfs(idx<<1);dfs(idx<<1|1);ans[idx]=a[cnt++];
}
signed main()
{cin>>n;for(int i=1;i<=n;i++) cin>>a[i];dfs(1);for(int i=1;i<=n;i++)cout<<ans[i]<<" \n"[i==n];return 0;
}

L2-036 网红点打卡攻略

#include <bits/stdc++.h>
#define int long long
const int N=210;
using namespace std; 
int n,m,k;
int g[N][N];
signed main()
{cin>>n>>m;for(int i=0;i<=n;i++)for(int j=0;j<=n;j++)if(i==j) g[i][j]=0;else g[i][j]=2e9;for(int i=1;i<=m;i++){int a,b,c;cin>>a>>b>>c;g[a][b]=min(g[a][b],c);g[b][a]=g[a][b];}cin>>k;vector<pair<int,int>>ans;for(int i=1;i<=k;i++){int num;cin>>num;int cost=0,now=0;bool ok=1;map<int,int>mp;set<int>st;for(int j=1;j<=num;j++){int x;cin>>x;mp[x]++;st.insert(x);if(mp[x]>1) ok=0;cost+=g[now][x];if(cost>=2e9) ok=0;now=x;}cost+=g[now][0];if(cost>=2e9) ok=0;if(st.size()!=n) ok=0;if(ok) ans.push_back({cost,i});}sort(ans.begin(),ans.end());cout<<ans.size()<<'\n';cout<<ans[0].second<<' '<<ans[0].first<<'\n';return 0;
}

L2-037 包装机

#include <bits/stdc++.h>
#define int long long
const int N=210;
using namespace std; 
int n,m,s;signed main()
{cin>>n>>m>>s;vector<queue<char>>q(n+1);for(int i=1;i<=n;i++){string S;cin>>S;for(int j=0;j<S.size();j++)q[i].push(S[j]);}stack<char>st;vector<char>ans;int x;while(cin>>x){if(x==-1) break;if(x==0){if(st.size()) {char t=st.top();st.pop();ans.push_back(t);	} }else{if(q[x].size()) {char t=q[x].front();q[x].pop();if(st.size()==s){ans.push_back(st.top());st.pop();}st.push(t);}}}for(int i=0;i<ans.size();i++)cout<<ans[i];cout<<'\n';return 0;
}

L2-038 病毒溯源

思路：找到入度为0的点，为源头病毒，从源头病毒dfs，并记录深度和路径。

#include <bits/stdc++.h>
const int N=1e4+10;
using namespace std; 
int n;
int g[N][N];
stack<int>st,tem;
map<int,bool>vis;
int maxlen;
vector<int>ans;
int in[N];
void dfs(int x,int depth)
{if(depth>maxlen){maxlen=depth;tem=st;}for(int j=0;j<n;j++){if(g[x][j]==0) continue;if(vis[j]) continue;vis[j]=1;st.push(j);dfs(j,depth+1);vis[j]=0;st.pop();}
}
signed main()
{ios::sync_with_stdio(0);cin.tie(0);scanf("%d",&n);for(int i=0;i<n;i++){int k;scanf("%d",&k);for(int j=0;j<k;j++){int x;scanf("%d",&x);g[i][x]=1;in[x]++;}}int root=0;for(int i=0;i<n;i++)if(in[i]==0) root=i;st.push(root);dfs(root,1);st.pop();while(tem.size()){ans.push_back(tem.top());tem.pop();}reverse(ans.begin(),ans.end());printf("%d\n",ans.size());for(int i=0;i<ans.size();i++)printf("%d%c",ans[i]," \n"[i==ans.size()-1]);return 0;
}

L2-039 清点代码库

思路：把模块输出的结果存在vector<int>中，使用map<vector<int>, int>统计输出结果相同的模块个数。因为要先按照个数递减，再按输出序列递增排序。因为在map中是按照输出序列递增排序的，再使用multimap<int, vector<int>, greater<int>>按照个数递减，当个数相同时按照插入原始顺序。

#include <bits/stdc++.h>
const int N=1e4+10;
using namespace std; 
int n,m;
map<vector<int>,int>mp;
multimap<int,vector<int>,greater<int>>ans;
signed main()
{cin>>n>>m;vector<int>tem(m);for(int i=1;i<=n;i++){for(int j=0;j<m;j++)cin>>tem[j];mp[tem]++;}for(auto x:mp) ans.insert({x.second,x.first});cout<<ans.size()<<'\n';for(auto it:ans){cout<<it.first;for(auto it2:it.second)cout<<' '<<it2;cout<<'\n';}return 0;
}

L2-040 哲哲打游戏

思路：模拟

#include <bits/stdc++.h>
const int N=1e5+10;
using namespace std; 
int n,m;
vector<int>g[N];
map<int,int>record;
signed main()
{cin>>n>>m;for(int i=1;i<=n;i++){int k;cin>>k;g[i].resize(k+1);for(int j=1;j<=k;j++)cin>>g[i][j];}int now=1;for(int i=1;i<=m;i++){int op;cin>>op;if(op==0){int j;cin>>j;now=g[now][j];}else if(op==1){int j;cin>>j;record[j]=now;cout<<now<<'\n';}else{int j;cin>>j;now=record[j];}}cout<<now<<'\n';return 0;
}

L2-041 插松枝

思路：stack模拟。注意最后盒子和传送器用完时，将当前松枝加入到答案。

#include <bits/stdc++.h>
const int N=1e5+10;
using namespace std; 
int n,m,k;
queue<int>q;
stack<int>st;
vector<vector<int>>ans;
int last=1e9;
vector<int>tem;
void finish()
{ans.push_back(tem);last=1e9;tem.resize(0);
}
signed main()
{cin>>n>>m>>k;for(int i=1;i<=n;i++){int x;cin>>x;q.push(x);}while(q.size()||st.size()){if(st.size()!=0){int t=st.top();if(t<=last) //盒子满足条件 {tem.push_back(t);last=t;st.pop();if(tem.size()==k) finish();}else if(q.size()) //盒子不满足条件 推送器取 {while(q.size()){t=q.front();if(t>last) {if(st.size()==m)// 1 {finish(); break;}q.pop();st.push(t);}else {tem.push_back(t);last=t;q.pop();if(tem.size()==k){finish();break;}}}}else //盒子不满足条件 推送器为空 {finish(); }}else //盒子为空{if(q.size()) //推送器非空 {while(q.size()){int t=q.front();if(t>last) {if(st.size()==m)// 1 {finish(); break;}q.pop();st.push(t);}else {tem.push_back(t);last=t;q.pop();if(tem.size()==k){finish();break;}}}}else //推送器为空{finish();} } }if(tem.size()) finish(); for(int i=0;i<ans.size();i++)for(int j=0;j<ans[i].size();j++)cout<<ans[i][j]<<" \n"[j==ans[i].size()-1];return 0;
}

L2-042 老板的作息表

思路：排序

#include <bits/stdc++.h>
const int N=1e5+10;
using namespace std; 
int n;
vector<pair<int,int>>t;
void print(int a,int b)
{int sh=a/60/60,sm=a/60-sh*60,ss=a-sh*60*60-sm*60;int eh=b/60/60,em=b/60-eh*60,es=b-eh*60*60-em*60;printf("%02d:%02d:%02d - %02d:%02d:%02d\n",sh,sm,ss,eh,em,es);
}
signed main()
{cin>>n;for(int i=0;i<n;i++){int a,b,c,A,B,C;scanf("%d:%d:%d - %d:%d:%d",&a,&b,&c,&A,&B,&C);int t1=a*60*60+b*60+c,t2=A*60*60+B*60+C;t.push_back({t1,t2});}sort(t.begin(),t.end());int last=0;for(int i=0;i<n;i++){int t1=t[i].first,t2=t[i].second;if(t1!=last) print(last,t1);last=t2;}if(last!=23*60*60+59*60+59) print(last,23*60*60+59*60+59);return 0;
}

L2-043 龙龙送外卖

思路：对于所有需要到达的点，其连到父节点的边一定是要经历的，而且从根节点到达子节点路径是唯一的，所以所有从根节点到某一子节点上路径涉及到的边一定都需要经历。由于是从根节点出发有些边会经历两次。又因为不必回到根节点，所以有一条从根节点到子节点的路径是多余的，可以反过来考虑，从根节点到所有子节点的路径全经历2次，然后删掉最长的一条从根节点到子节点的路径。

到达节点的距离可以用dfs/bfs来解决。在计算答案时，每多出来一个节点就累加未累加过的边权两倍，并不断更新最长路径的距离。

#include <bits/stdc++.h>
const int N=1e5+10;
using namespace std;
int n,m;
int fa[N];
int h[N],e[N],ne[N],idx;
int dis[N]; 
bool st[N];
void add(int a,int b)
{e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
void dfs(int u,int depth)
{dis[u]=depth;for(int i=h[u];~i;i=ne[i]){int j=e[i];dfs(j,depth+1);}
}
signed main()
{memset(h,-1,sizeof h);cin>>n>>m;int root=0;for(int i=1;i<=n;i++){int x;cin>>x;fa[i]=x;if(x==-1) root=i;else add(x,i);} dfs(root,0);int maxlen=0,ans=0;for(int i=1;i<=m;i++){int x;cin>>x;maxlen=max(maxlen,dis[x]);int now=x;while(now!=root&&!st[now]){st[now]=1;ans+=2;now=fa[now];}cout<<ans-maxlen<<'\n';}return 0;
}