2026年团体程序设计天梯赛真题试题详解与题解

2026年团体程序设计天梯赛真题试题详解与题解第一部分：算法设计（共3题，每题20分）1.最短路径问题（20分）题目描述：给定一个包含n个节点（编号1到n）和m条边的无向图，每条边有一个权重。请设计一个算法，计算从节点1到节点n的最短路径长度。图采用邻接矩阵表示，权重可能为无穷大（表示不直接相连）。输入：第一行：两个整数n和m（1≤n≤1000，0≤m≤10000）。接下来m行，每行三个整数u、v、w（1≤u,v≤n，1≤w≤10^6），表示一条从u到v的边，权重为w。若u和v之间没有边，则邻接矩阵中对应值为无穷大。输出：一个整数，表示从节点1到节点n的最短路径长度。若无路径可达，输出-1。示例：输入：4412223234114100输出：4答案与解析：答案：cppinclude<bits/stdc++.h>usingnamespacestd;constintINF=1e9;intmain(){intn,m;cin>>n>>m;vector<vector<int>>dist(n+1,vector<int>(n+1,INF));for(inti=1;i<=n;i++)dist[i][i]=0;for(inti=0;i<m;i++){intu,v,w;cin>>u>>v>>w;dist[u][v]=min(dist[u][v],w);dist[v][u]=min(dist[v][u],w);}for(intk=1;k<=n;k++)for(inti=1;i<=n;i++)for(intj=1;j<=n;j++)if(dist[i][k]+dist[k][j]<dist[i][j])dist[i][j]=dist[i][k]+dist[k][j];cout<<(dist[1][n]==INF?-1:dist[1][n]);}解析：采用Floyd-Warshall算法求解所有对最短路径问题。时间复杂度为O(n^3)，适合节点数量不超过1000的情况。核心思想通过动态规划更新三重循环中的最短路径。2.背包问题（20分）题目描述：给定n件物品和一个容量为C的背包。每件物品有一个重量w和价值v。请设计一个算法，计算背包能装入的最大总价值。输入：第一行：两个整数n和C（1≤n≤200，1≤C≤2000）。接下来n行，每行两个整数w和v（1≤w≤2000，1≤v≤10^6）。输出：一个整数，表示背包的最大总价值。示例：输入：47310352719输出：22答案与解析：答案：cppinclude<bits/stdc++.h>usingnamespacestd;intmain(){intn,C;cin>>n>>C;vector<int>w(n+1),v(n+1);for(inti=1;i<=n;i++)cin>>w[i]>>v[i];vector<vector<int>>dp(n+1,vector<int>(C+1,0));for(inti=1;i<=n;i++)for(intj=0;j<=C;j++)dp[i][j]=dp[i-1][j];if(j>=w[i])dp[i][j]=max(dp[i][j],dp[i-1][j-w[i]]+v[i]);cout<<dp[n][C];}解析：采用01背包动态规划解法。状态dp[i][j]表示前i件物品在容量为j时的最大价值。通过遍历更新dp数组，最终dp[n][C]即为答案。3.并查集应用（20分）题目描述：给定n个节点和m个合并操作，每次操作将两个节点合并。请设计一个算法，统计所有合并操作后形成的连通分量的数量。输入：第一行：两个整数n和m（1≤n≤10^5，1≤m≤10^5）。接下来m行，每行两个整数u和v，表示合并u和v。输出：一个整数，表示连通分量的数量。示例：输入：551223451534输出：1答案与解析：答案：cppinclude<bits/stdc++.h>usingnamespacestd;structUnionFind{vector<int>fa;UnionFind(intn):fa(n+1){for(inti=0;i<=n;i++)fa[i]=i;}intfind(intx){returnx==fa[x]?x:fa[x]=find(fa[x]);}voidmerge(intx,inty){intfx=find(x),fy=find(y);if(fx!=fy)fa[fx]=fy;}};intmain(){intn,m;cin>>n>>m;UnionFinduf(n);for(inti=0;i<m;i++){intu,v;cin>>u>>v;uf.merge(u,v);}unordered_set<int>s;for(inti=1;i<=n;i++)s.insert(uf.find(i));cout<<s.size();}解析：采用并查集数据结构，通过路径压缩和按秩合并优化查询和合并效率。最后统计根节点的数量即为连通分量的数量。第二部分：数据结构（共3题，每题20分）4.堆排序实现（20分）题目描述：给定一个包含n个整数的无序数组，请设计一个算法，通过堆排序将其升序排列。堆采用最大堆实现。输入：一行：n个整数（1≤n≤10000，-10^6≤数值≤10^6）。输出：一行：排序后的数组。示例：输入：63-12640输出：-102346答案与解析：答案：cppinclude<bits/stdc++.h>usingnamespacestd;voidheapify(vector<int>&arr,intn,inti){intlargest=i,l=2i+1,r=2i+2;if(l<n&&arr[l]>arr[largest])largest=l;if(r<n&&arr[r]>arr[largest])largest=r;if(largest!=i){swap(arr[i],arr[largest]);heapify(arr,n,largest);}}voidheapSort(vector<int>&arr){intn=arr.size();for(inti=n/2-1;i>=0;i--)heapify(arr,n,i);for(inti=n-1;i>=0;i--){swap(arr[0],arr[i]);heapify(arr,i,0);}}intmain(){intn;cin>>n;vector<int>arr(n);for(auto&x:arr)cin>>x;heapSort(arr);for(inti=0;i<n;i++)cout<<arr[i]<<(i<n-1?'':'\n');}解析：堆排序的核心是维护最大堆的性质。首先将数组调整为大根堆，然后依次将堆顶与末尾交换并重新调整堆，最终得到升序排列。5.哈希表应用（20分）题目描述：给定一个字符串s和一个整数k，统计s中所有长度为k的子串在s中出现的次数。请设计一个算法，使用哈希表高效统计。输入：第一行：字符串s（1≤|s|≤10^5）。第二行：整数k（1≤k≤|s|）。输出：一个整数，表示长度为k的子串的出现次数。示例：输入：ababa2输出：4答案与解析：答案：cppinclude<bits/stdc++.h>usingnamespacestd;typedeflonglongll;constintBASE=257,MOD=1e9+7;intmain(){strings;cin>>s;intk;cin>>k;if(k>s.size())cout<<0;else{unordered_map<ll,int>cnt;llhash=0,power=1;for(inti=0;i<k;i++)hash=(hashBASE+s[i])%MOD,power=(powerBASE)%MOD;cnt[hash]++;for(inti=k;i<s.size();i++){hash=(hashBASE+s[i])%MOD;hash=(hash-powers[i-k])%MOD;if(hash<0)hash+=MOD;cnt[hash]++;}cout<<cnt.size();}}解析：采用滚动哈希算法计算子串哈希值。通过初始子串的哈希值和后续子串的哈希值快速转移，统计不同哈希值的数量即为不同子串的数量。6.树的应用（20分）题目描述：给定一棵n个节点的树，每个节点有一个权值。请设计一个算法，计算树中所有简单路径的最大权值和。输入：第一行：两个整数n和root（1≤n≤1000，root为根节点编号，1≤root≤n）。接下来n行，每行一个整数表示节点的权值（1≤权值≤10^6）。接下来n-1行，每行两个整数u和v，表示一条边。输出：一个整数，表示所有简单路径的最大权值和。示例：输入：511234512232445输出：12答案与解析：答案：cppinclude<bits/stdc++.h>usingnamespacestd;structEdge{intto,next;}edges[10000];intn,root,val[1001],head[1001],ans=0;voiddfs(intu,intfa,intsum){ans=max(ans,sum);for(inti=head[u];i;i=edges[i].next){intv=edges[i].to;if(v==fa)continue;dfs(v,u,sum+val[v]);}}intmain(){cin>>n>>root;for(inti=1;i<=n;i++)cin>>val[i];for(inti=1;i<=n-1;i++){intu,v;cin>>u>>v;edges[++n]=Edge{v,head[u]};head[u]=n;edges[++n]=Edge{u,head[v]};head[v]=n;}dfs(root,-1,val[root]);cout<<ans;}解析：采用深度优先搜索（DFS）遍历树，通过累加路径权值计算所有路径的和。由于树中没有环，所有路径权值之和即为最大权值和。第三部分：编程实现（共2题，每题30分）7.数据统计（30分）题目描述：给定一个包含n个学生的成绩列表，每个学生包含学号、姓名和成绩。请设计一个算法，统计每个成绩段的学生人数，并按学号升序输出所有学生信息。输入：第一行：整数n（1≤n≤10000）。接下来n行，每行三个字符串：学号（唯一）、姓名（长度不超过10）和成绩（0≤成绩≤100）。输出：第一行：5个整数，分别表示0-59、60-69、70-79、80-89、90-100分段的学生人数。接下来n行：按学号升序输出学生信息。示例：输入：5001Alice85002Bob92003Charlie58004David77005Eve63输出：01121001Alice85004David77005Eve63002Bob92003Charlie58答案与解析：答案：cppinclude<bits/stdc++.h>usingnamespacestd;structStudent{stringid,name;intscore;booloperator<(constStudent&x)const{returnid<x.id;}};intmain(){intn;cin>>n;vector<Student>students(n);vector<int>cnt(5,0);for(auto&s:students)cin>>s.id>>>>s.score;sort(students.begin(),students.end(),[&](constStudent&x,constStudent&y){if(x.score/10!=y.score/10)returnx.score/10<y.score/10;returnx.id<y.id;});for(auto&s:students){if(s.score<=59)cnt[0]++;elseif(s.score<=69)cnt[1]++;elseif(s.score<=79)cnt[2]++;elseif(s.score<=89)cnt[3]++;elsecnt[4]++;}for(inti=0;i<5;i++)cout<<cnt[i]<<(i<4?'':'\n');for(auto&s:students)cout<<s.id<<''<<<<''<<s.score<<'\n';}解析：首先读取学生信息并存储在结构体数组中，然后按成绩分段统计人数。接着按学号升序排序输出学生信息。8.文件处理（30分）题目描述：给定一个包含n行文本的文件，每行可能包含多个单词。请设计一个算法，统计每个单词出现的次数，并按出现次数降序输出前10个最常见的单词。输入：第一行：整数n（1≤n≤10000）。接下来n行：每行一个字符串，表示一行文本（长度不超过1000）。输出：第一行：10个整数，表示前10个单词的出现次数。第二行：10个字符串，表示前10个最常见的单词。示例：输入：5helloworldhelloworldhellohelloworldhi输出：3211111111helloworldworldhellohi答案与解析：答案：cppin