2025年第十届团队程序设计天梯赛c++题解L1-L3-1（附PTA网址）
这篇博客记录了作者参加天梯赛的经历和解题思路。从L1到L3级别的题目中，作者分享了多个编程题目的解法，包括字符串处理、模拟题、优先队列应用、图论算法等。每道题都附有代码实现，并简要说明了算法思路。作者回顾了比赛中的紧张时刻和有趣插曲，比如服务器故障带来的心态调整，以及对IOI赛制的喜爱。文章最后表达了从大一新生变成大二学长的感慨，以及对未来学习压力的思考。
·
开局感慨
第一场天梯赛，十个人一个队伍，一坑坑九个，赛前压力还是蛮大的。赛前学长说不到200跑回去，结果也是拉满了暴砍两百多。开赛一个小时服务器爆炸提交不了题，不过也确实缓和了一下心态吧，有点可惜的是差一丢丢个人国二，可惜兄弟可惜。IOI赛制我还是挺喜欢的，ACM打的是心惊肉跳，IOI压力没那么大，不过不让上厕所真的很难绷。
过了这么久（四个月了.....），终于把题补的差不多了，发个题解，也算是年后总结了，下一年大二，压力还是蛮大的，突然就从小登变成老登了......
L1
L1-1珍惜生命
直接cout要求的字符串
#include<bits/stdc++.h>
#define int long long
using namespace std;
bool tin = 0 ;
void solve()
{
cout<<"Always code as if the guy who ends up maintaining your code will be a violent psychopath who knows where you live.";
}
signed main()
{
ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);
int T=1;
if(tin)
cin>>T;
while(T--)
{
solve();
}
return 0;
}L1-2 偷感好重
直接输出三数加和
#include<bits/stdc++.h>
#define int long long
using namespace std;
bool tin = 0 ;
void solve()
{
int a,b,c;
cin>>a>>b>>c;
cout<<a+b+c;
}
signed main()
{
ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);
int T=1;
if(tin)
cin>>T;
while(T--)
{
solve();
}
return 0;
}L1-3高温补贴
先判断是否高温，再判断是否室内，四种情况逐个判断就行
#include<bits/stdc++.h>
#define int long long
using namespace std;
bool tin = 0 ;
void solve()
{
int a,b,c;
cin>>a>>c>>b;
if(a>=35&&b>=33)
{
if(c)
cout<<"Bu Tie";
else
cout<<"Shi Nei";
cout<<'\n'<<a;
}
else
{
if(c)
cout<<"Bu Re";
else
cout<<"Shu Shi";
cout<<"\n"<<b;
}
}
signed main()
{
ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);
int T=1;
if(tin)
cin>>T;
while(T--)
{
solve();
}
return 0;
}L1-4零头就抹了吧
找到最大的小于输入数的2的次方数，从1开始不断乘2，大于时退出，最后输出除以2的值即可
#include<bits/stdc++.h>
#define int long long
using namespace std;
bool tin = 0 ;
void solve()
{
int n;
cin>>n;
int ans=1;
while(ans<=n)
ans*=2;
cout<<ans/2;
}
signed main()
{
ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);
int T=1;
if(tin)
cin>>T;
while(T--)
{
solve();
}
return 0;
}L1-5这是字符串题
开个map存每个字符的贡献，分别求出输出后加个和，不保留小数直接输出即可
#include<bits/stdc++.h>
#define int long long
using namespace std;
bool tin = 0 ;
void solve()
{
string s;
cin>>s;
map<char,int> ma;
for(auto x:s)
ma[x]++;
double ans=0,x;
for(char i='a';i<='z';i++)
{
cin>>x;
ans+=ma[i]*x;
}
for(char i='a';i<='z';i++)
{
if(i!='a')
cout<<" ";
cout<<ma[i];
}
cout<<'\n';
cout<<fixed<<setprecision(0)<<ans;
}
signed main()
{
ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);
int T=1;
if(tin)
cin>>T;
while(T--)
{
solve();
}
return 0;
}L1-6这不是字符串题
L1-110 这不是字符串题 - 团体程序设计天梯赛-练习集
数据范围不大，纯字符串模拟，重要的是根据数据范围，1<=Ai<=26,将整数数组转化为字符串去处理，然后模拟即可，按照要求来就行，模拟还是挺考验代码能力的，赛时写了二十多分钟，给我紧张死了，压力
#include<bits/stdc++.h>
#define int long long
using namespace std;
bool tin = 0 ;
void solve()
{
int n,m;
cin>>n>>m;
string s="";
int x=0,op;
for(int i=0;i<n;i++)
{
cin>>x;
s+=(x-1+'a');
}
int n1,n2;
while(m--)
{
cin>>op;
if(op==1)
{
cin>>n1;
string s1="",s2="";
for(int i=0;i<n1;i++)
{
cin>>x;
s1+=(x-1+'a');
}
cin>>n2;
for(int i=0;i<n2;i++)
{
cin>>x;
s2+=(x-1+'a');
}
int b=s.find(s1);
if(b!=-1)
{
s.erase(b,n1);
s.insert(b,s2);
}
}
else if(op==2)
{
for(int i=1;i<s.size();i++)
{
int t=s[i-1]-'a'+1+s[i]-'a'+1;
string st="";
if(!(t&1))
{
t/=2;
st+=t-1+'a';
s.insert(i,st);
i++;
}
}
}
else
{
cin>>n1>>n2;
reverse(&s[n1-1],&s[n2]);
}
}
for(int i=0;i<s.size();i++)
{
if(i)
cout<<' ';
int u=s[i]+1-'a';
cout<<u;
}
}
signed main()
{
ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);
int T=1;
if(tin)
cin>>T;
while(T--)
{
solve();
}
return 0;
}L1-7大幂数
因为涉及次方，数据范围就不算大，也就是从最坏的情况，只有2开始求出最大的k的情况，然后往下依次枚举看这个k是否合法，可以写个快速幂优化一下
#include<bits/stdc++.h>
#define int long long
using namespace std;
bool tin = 0 ;
int qmi(int x,int y)
{
int ans=1;
while(y)
{
if(y&1)
ans*=x;
x*=x;
y/=2;
}
return ans;
}
void solve()
{
int n;
cin>>n;
int e=1;
int t=n;
while(t)
{
t/=2;
e++;
}
int kk=1;
for(int i=e;i&&kk;i--)
{
int j,ans=0;
for( j=1;ans<n;j++)
{
ans+=qmi(j,i);
}
if(ans==n)
{
kk=0;
for(int k=1;k<j;k++)
{
if(k!=1)
cout<<"+";
cout<<k<<"^"<<i;
}
}
}
if(kk)
cout<<"Impossible for "<<n<<".";
}
signed main()
{
ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);
int T=1;
if(tin)
cin>>T;
while(T--)
{
solve();
}
return 0;
}L1-8 现代战争
很明显的优先队列，先轰炸单个价值最大，也就是从大到小枚举就行，炸掉之后对行列进行标记即可，是否被轰炸就看所在行列是否被标记过就行。赛时可能还是紧张了没有优先队列优化，真心可惜.....
#include<bits/stdc++.h>
#define int long long
using namespace std;
bool tin = 0 ;
int h[10005],l[10005];
void solve()
{
int n,m,k;
cin>>n>>m>>k;
vector <vector <int> > a(n,vector <int> (m));
priority_queue <array<int,3> > pq;
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
cin>>a[i][j];
pq.push({a[i][j],i,j});
}
}
while(k--)
{
auto x=pq.top();
while(h[x[1]]||l[x[2]])
{
pq.pop();
x=pq.top();
}
h[x[1]]=l[x[2]]=1;
}
for(int i=0;i<n;i++)
{
if(h[i])
continue;
int fir=0;
for(int j=0;j<m;j++)
{
if(l[j])
continue;
if(fir)
cout<<' ';
else
fir=1;
cout<<a[i][j];
}
cout<<'\n';
}
}
signed main()
{
ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);
int T=1;
if(tin)
cin>>T;
while(T--)
{
solve();
}
return 0;
}L2
L2-1 算式拆解
呃，也算是个小模拟吧，题目说了题目保证给出的算式非空，且是正确可计算的。其实就是让找括号优先级，那就是找右括号吗，找到右括号就往左找他的左括号这样就保证优先级了（一定是右括号在前面的先运算）
#include<bits/stdc++.h>
#define int long long
using namespace std;
bool tin = 0 ;
void solve()
{
string s;
cin>>s;
for(int i=0;i<s.size();i++)
{
if(s[i]==')')
{
int j;
for( j=i;s[j]!='(';j--)
{}
for(int k=j+1;k<i;k++)
cout<<s[k];
cout<<'\n';
s.erase(j,(i-j+1));
i=j-1;
}
}
}
signed main()
{
ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);
int T=1;
if(tin)
cin>>T;
while(T--)
{
solve();
}
return 0;
}L2-2 三点共线
出题人太友善了，限制了y坐标只能是0，1，2，也不要求输出水平的，那就很简单了，就是符合规则的肯定y坐标是0，1，2这样，然后斜率一样，可以算出个三点共线的等式
（x,0）,(y,1),(z,2)
k=(y-x)/1=(z-y)/1;
2*y-x==z
所以我们把x值为1，0的存数组里，然后2的存哈希，暴力枚举1和0的情况看是否有2能搭配上即可
#include<bits/stdc++.h>
#define int long long
#define endl "\n"
using namespace std;
bool tin = 0;
const int N=1000000;
int f[N*2+10];
void solve()
{
int n,x,y;
cin>>n;
vector <vector <int> > ve(2);
for(int i=0;i<n;i++)
{
cin>>x>>y;
if(y==2)
{
f[x+N]++;
}
else
{
ve[y].push_back(x);
}
}
for(int i=0;i<2;i++)
{
sort(ve[i].begin(),ve[i].end());
ve[i].erase(unique(ve[i].begin(),ve[i].end()),ve[i].end());
}
bool ye=1;
for(auto y:ve[1])
{
for(auto x:ve[0])
{
int z=2*y-x;
if(abs(z)<=N&&f[z+N])
{
ye=0;
cout<<'['<<x<<", 0] ["<<y<<", 1] ["<<z<<", 2]"<<endl;
}
}
}
if(ye)
{
cout<<"-1"<<endl;
}
}
signed main()
{
ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);
int T=1;
if(tin)
cin>>T;
while(T--)
{
solve();
}
return 0;
}L2-3 胖达的山头
因为时间不大，所以可以直接用秒做单位化成线型的，做差分即可，一个熊猫记作在时间段+1个单位吗，最后前缀和处理，求出来数组（也就是每一秒）有的熊猫数量，取出最大值输出即可
#include<bits/stdc++.h>
//#define int long long
using namespace std;
bool tin = 0 ;
int he[100005];
void solve()
{
int n,a,b,c,d,e,f;
cin>>n;
int m=0;
while(n--)
{
scanf("%2d:%2d:%2d %2d:%2d:%2d",&a,&b,&c,&d,&e,&f);
int ui=a*60*60+b*60+c;
int uu=d*60*60+e*60+f;
m=max(uu,m);
he[ui]++,he[uu+1]--;
}
int ans=he[0];
for(int i=1;i<=m;i++)
{
he[i]+=he[i-1];
ans=max(ans,he[i]);
}
cout<<ans;
}
signed main()
{
//ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);
int T=1;
if(tin)
cin>>T;
while(T--)
{
solve();
}
return 0;
}L2-4 被n整除的n位数
L2-056 被n整除的n位数 - 团体程序设计天梯赛-练习集
暴力从左到右会超时，数据大小太大，但是位数不大，也就考虑依次填位值，考虑dfs第一位填1-9，之后填0-9即可，位数够的时候判断是否合法即可，合法放进答案数组，最后一排序顺序输出即可
#include<bits/stdc++.h>
#define int long long
#define endl "\n"
using namespace std;
bool tin = 0;
int n,a,b;
vector <int> ans;
void dfs(string s)
{
// cout<<s<<endl;
if(s.size()==n)
{
int u=stoll(s);
if(u>=a&&u<=b)
{
ans.push_back(u);
}
return ;
}
for(char i='0';i<='9';i++)
{
int u=stoll(s+i);
if(u%(s.size()+1)==0)
dfs(s+i);
}
}
void solve()
{
cin>>n>>a>>b;
for(char i='1';i<='9';i++)
{
string s="";
s+=i;
dfs(s);
}
if(ans.size())
{
sort(ans.begin(),ans.end());
for(auto x:ans)
cout<<x<<endl;
}
else
cout<<"No Solution";
}
signed main()
{
ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);
int T=1;
if(tin)
cin>>T;
while(T--)
{
solve();
}
return 0;
}L3
L3-1 人生就像一场旅行
L3-040 人生就像一场旅行 - 团体程序设计天梯赛-练习集
迪杰斯特拉满分？我不知道我这个代码谁写的，我补题的时候上号一看有个满分代码，之前和朋友聊的好像就是迪杰斯特拉就行
L3还是太权威了
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 505;
int b, n, m, k;
vector<array<int,3>> h[MAXN]; // {to, cost, mood}
struct Node {
int u, cost, mood;
bool operator>(const Node& other) const {
if (cost == other.cost) return mood < other.mood;
return cost > other.cost;
}
};
void solve() {
cin >> b >> n >> m >> k;
for (int i = 0; i < m; ++i) {
int u, v, c, w;
cin >> u >> v >> c >> w;
h[u].push_back({v, c, w});
h[v].push_back({u, c, w});
}
while (k--) {
int start;
cin >> start;
vector<int> cost(n+1, INT_MAX);
vector<int> mood(n+1, 0);
vector<bool> vis(n+1, false);
priority_queue<Node, vector<Node>, greater<Node>> pq;
cost[start] = 0;
pq.push({start, 0, 0});
while (!pq.empty()) {
auto [u, c, m] = pq.top();
pq.pop();
if (vis[u]) continue;
vis[u] = true;
for (auto& edge : h[u]) {
int v = edge[0], c_new = edge[1], m_new = edge[2];
if (c + c_new > b) continue;
if (cost[v] > c + c_new) {
cost[v] = c + c_new;
mood[v] = m + m_new;
pq.push({v, cost[v], mood[v]});
} else if (cost[v] == c + c_new && mood[v] < m + m_new) {
mood[v] = m + m_new;
pq.push({v, cost[v], mood[v]});
}
}
}
vector<int> reachable;
vector<pair<int, int>> mood_list;
for (int i = 1; i <= n; ++i) {
if (i != start && cost[i] <= b) {
reachable.push_back(i);
mood_list.emplace_back(-mood[i], i);
}
}
if (reachable.empty()) {
cout << "T_T\n";
continue;
}
sort(reachable.begin(), reachable.end());
for (int i = 0; i < reachable.size(); ++i) {
if (i) cout << " ";
cout << reachable[i];
}
cout << "\n";
sort(mood_list.begin(), mood_list.end());
vector<int> best;
int best_mood = -mood_list[0].first;
for (auto& p : mood_list) {
if (-p.first == best_mood) {
best.push_back(p.second);
} else {
break;
}
}
sort(best.begin(), best.end());
for (int i = 0; i < best.size(); ++i) {
if (i) cout << " ";
cout << best[i];
}
cout << "\n";
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
solve();
return 0;
}
腾讯云面向开发者汇聚海量精品云计算使用和开发经验，营造开放的云计算技术生态圈。
更多推荐
14
0- 0
已为社区贡献1条内容
所有评论(0)