2025年PTA天梯赛正式赛 | 算法竞赛，题目详解

L1

L1-01：珍惜声明

在这里插入图片描述
第一题就不说了，直接打印即可

#include<iostream>
using namespace std;
int main(){cout<<"Always code as if the guy who ends up maintaining your code will be a violent psychopath who knows where you live."<<endl;return 0;
}

L1-2偷感好重

在这里插入图片描述
也是，直接相加即可

#include<iostream>
using namespace std;
int main(){int a,b,c;cin>>a>>b>>c;cout<<a+b+c<<endl;return 0;
}

L1-3：高温补贴

在这里插入图片描述

#include<iostream>
using namespace std;
int main(){//35露天工作，并且不能将工作场所气温降到33以下的，int T,S,t;cin>>T>>S>>t;if(T>35){if(S==1){//露天if(t>=33){cout<<"Bu Tie"<<endl;cout<<T;}else{cout<<"Bu Re"<<endl;cout<<t;}}else{//室内if(t>=33){cout<<"Shi Nei"<<endl;cout<<T;}else{cout<<"Shu Shi"<<endl;cout<<t;}}}else{if(S==1){//露天if(S>=33){cout<<"Bu Tie"<<endl;cout<<T;}else{cout<<"Bu Re"<<endl;cout<<t;}}else{//室内if(S>=33){cout<<"Bu Tie"<<endl;cout<<T;}else{cout<<"Shu Shi"<<endl;cout<<t;}}}return 0;
}

if else判断即可，样例比较多，一个一个试一下应该还是比较简单的，题目可能有点绕

L1-4:零头就抹了吧

在这里插入图片描述
这个比较容易理解，直接二进制往前进就行，也就是2的n次幂，直到加到里源数据最近的那个数输出即可

#include<iostream>
using namespace std;
int main(){int n;cin>>n;int sum=1;while(sum<=n){sum*=2;}cout<<sum/2<<endl;return 0;
}

L1-5:这是字符串题

在这里插入图片描述
用一个数组储存字符串美丽度，用一个数组储存字符串每个字符数字数量

#include<iostream>
#include<map>
using namespace std;
int arr[200]={0};
int cnt[200]={0};
int res=0;
int main(){string a;cin>>a;for(int i=97;i<=122;i++){int n;cin>>n;arr[i]=n;}//然后统计每个字符出现个数for(int i=0;i<a.length();i++){cnt[int(a[i])]++;}for(int i=97;i<=122;i++){if(i==97){}else cout<<" ";cout<<cnt[i];}cout<<endl;for(int i=0;i<a.length();i++){res+=arr[int(a[i])];}cout<<res;return 0;
}

L1-6 这不是字符串题

在这里插入图片描述
因为数字范围是1-26，所以可以直接转化为字符求解

#include<iostream>
using namespace std;
//因为这里有个位数或者十位数，替换的时候不好替换，可以先转化为
//字母
string s;
int main(){int n,T;cin>>n>>T;for(int i=0;i<n;i++){int tmp;cin>>tmp;s+=char(tmp+'a'-1);//将每个数字都转化为字母的码值}while(T--){int m;cin>>m;if(m==1){//替换string re1,re2;int len1;cin>>len1;for(int i=0;i<len1;i++){//输入int tmp;cin>>tmp;re1+=char(tmp+'a'-1);}int len2;cin>>len2;for(int i=0;i<len2;i++){//输入int tmp;cin>>tmp;re2+=char(tmp+'a'-1);}if(s.find(re1)!=-1){//如果能找到，开始替换s.replace(s.find(re1),re1.length(),re2);}}else if(m==2){//插入string shix;//这里需要处理一下越界问题for(int i=0;i<s.length();i++){shix+=s[i];if(i<s.length()-1){//偶数则插入//这里直接插入不会影响原数列吗，当然会，所以要//先创建一个新的字符串进行存储int tmp1=s[i]-'a'+1;int tmp2=s[i+1]-'a'+1;int sum=tmp1+tmp2;if(sum%2==0){shix+=char(sum/2+'a'-1);}}}s=shix;}else{//反转int l,r;cin>>l>>r;reverse(s.begin()+l-1,s.begin()+r);}}for(int i=0;i<s.length();i++){if(i!=0)cout<<" ";cout<<int(s[i]-'a'+1);}return 0;
}

L1-7 大幂数

在这里插入图片描述
因为是找最大值，直接倒着求就行

#include<iostream>
#include<cmath>
#include<string>
using namespace std;long long int_pow(int base, int exp) {long long result = 1;for (int i = 0; i < exp; ++i) {result *= base;}return result;
}string get_expression(int k, int m) {string expr;for (int i = 1; i <= m; ++i) {if (i != 1) expr += "+";expr += to_string(i) + "^" + to_string(k);}return expr;
}int main() {int n;cin >> n;int max_k = 0;int best_m = 0;bool found = false;for (int k = 30; k >= 1; --k) {long long sum = 0;int m = 1;while (true) {long long term = int_pow(m, k);if (sum + term > n) break;sum += term;if (sum == n) {if (k > max_k) {max_k = k;best_m = m;found = true;}break;}m++;}}if (found) {cout << get_expression(max_k, best_m) << endl;} else {cout << "Impossible for " << n << "." << endl;}return 0;
}

L1-8 现代战争

在这里插入图片描述
开了好几个数组，一个记录是否被炸，一个记录价值，一个记录价值与坐标联系

//首先，如何每次找到最高价值建筑
//直接用一个数组处理整行整列是否存在
//那么就是，可以对建筑价值排序，降序排序，每次取到最高价值
//题目保证每个价值互不相等
#include<iostream>
using namespace std;
#define int long long
struct shix{int a;int b;int value;
};
bool cmp(shix a,shix b){return a.value>b.value;
}
int arr[1010][1010];
shix tmp[1000010];
bool row[1010];
bool line[1010];
signed main(){int n,m,s;cin>>n>>m>>s;int cnt=0;for(int i=0;i<n;i++){for(int j=0;j<m;j++){cin>>arr[i][j];tmp[cnt].a=i;tmp[cnt].b=j;tmp[cnt++].value=arr[i][j];}}//然后对所有价值进行排序sort(tmp,tmp+cnt,cmp);//对所有价值进行处理for(int i=0;i<cnt;i++){//如果这个坐标的行，列都已经处理过，那么就continue//没有处理过，那么就进行处理//每一次炸的时候肯定是两个不同的坐标if(!row[tmp[i].a]&&!line[tmp[i].b]){//cout<<"拆掉"<<tmp[i].a<<" "<<line[tmp[i].b]<<endl;//这个判断就是这个位置没有row[tmp[i].a]=true;line[tmp[i].b]=true;s--;}//else cout<<"不拆"<<tmp[i].a<<" "<<line[tmp[i].b]<<endl;if(s<=0)break;}//然后输出结果for(int i=0;i<n;i++){//处理该列的空格int lin_cnt=0;for(int j=0;j<m;j++){if(!row[i]&&!line[j]){//该行该列没有杯轰炸，那么就直接输出if(lin_cnt++!=0)cout<<" ";cout<<arr[i][j];}}//对于换行符来说，如果整个行被轰炸，那么该行就不输出换行if(!row[i])cout<<endl;}return 0;
}

L2

L2-1:算式拆解

在这里插入图片描述
这是一道经典的栈的数据结构例题，将字符串从左往右依次遍历，如果找到)就要开始输出，注意这个continue很关键，避免将)压入栈

#include<iostream>
#include<stack>
using namespace std;
stack<char>st;
stack<char>ans;
int main(){string str;cin>>str;for(int i=0;i<str.length();i++){if(!st.empty()&&str[i]==')'){//找到右括号，就可以进行一次输出//输出前删除右括号while(!st.empty()){//如果输出到右括号，直接删除即可if(st.top()=='('){st.pop();break;}//如果还不到右括号，那就是答案//把答案存进来ans.push(st.top());st.pop();}//如果空了，证明储存完毕，就可以进行输出了while(!ans.empty()){cout<<ans.top();ans.pop();}cout<<endl;continue;}//如果栈空，就先入栈st.push(str[i]);//这个去处理最后一个括号// if(!st.empty()&&i==str.length()-1){//     st.pop();//     cout<<st.top()<<endl;// }}return 0;
}

L2-2 三点共线

在这里插入图片描述
我的思路就是，两层循环，第一层是y=2的点，第二层是y=0的点，然后处理一下斜率，看看它们两个点连接的直线是否能过一个y=1的点，如果能过那么这就是一个结果，但是会超时，懂的朋友可以看一下

//三个点位于一条，
//如果想三点共线，那么必然是一个在y2，一个在y0，中间那个在y1
//计算全部斜率，然后去判断中间值
#include<iostream>
#include<map>
using namespace std;
int loc0[50001];
int loc2[50001];
//step记录这个值是否有数据
//mid也有可能等于负数，所以这个应该拿map存储
map<int,int> step;
map<int,int> quchong;
struct lin{int a,b,c;
};
lin res[100010];
bool cmp(lin n,lin m){if(n.b!=m.b){return n.b<m.b;}else{return n.a<m.a;}
}
int main(){int n;cin>>n;//不能输出重复的解//单斜率不够，因为两点已经确定一个直线//对y1坐标点求一个int cnt0=0,cnt2=0;while(n--){int a,b;cin>>a>>b;if(b==0){loc0[cnt0++]=a;}else if(b==2){loc2[cnt2++]=a;}else{step[a]=1;}}int shix=0;for(int i=0;i<cnt0;i++){//外层循环cnt0for(int j=0;j<cnt2;j++){//内层循环cnt2if((loc0[i]+loc2[j])%2==0){int mid=(loc0[i]+loc2[j])>>1;if(step[mid]==1&&quchong[loc0[i]]!=loc2[j]){//如果y1坐标下该值存在//并且要对这个结果进行一个去重操作quchong[loc0[i]]=loc2[j];//证明这两个点已经被使用//储存答案//printf("[%d, 0] [%d, 1] [%d, 2]\n",loc0[i],mid,loc2[j]);res[++shix].a=loc0[i];res[shix].b=mid;res[shix].c=loc2[j];}}}}//然后按照顺序输出结果sort(res+1,res+shix+1,cmp);if(shix==0){cout<<"-1"<<endl;}else{for(int i=1;i<=shix;i++){printf("[%d, 0] [%d, 1] [%d, 2]\n",res[i].a,res[i].b,res[i].c);}}return 0;
}

L2-3:胖达的山头

在这里插入图片描述
这一题一天的时间在24*3600秒，所以暴力时间+差分也不会超时

#include<iostream>
using namespace std;
const int N=3600*24;
int arr[N+3]={0};
int main(){int n;cin>>n;for(int i=0;i<n;i++){int h,m,s;scanf("%d:%d:%d",&h,&m,&s);int eh,em,es;scanf("%d:%d:%d",&eh,&em,&es);int st=h*3600+m*60+s;int ed=eh*3600+em*60+es;arr[st]+=1;arr[ed+1]-=1;}int mx=0;for(int i=0;i<=N;i++){arr[i]+=arr[i-1];mx=max(mx,arr[i]);}cout<<mx<<endl;
}

L2-4 被n整除的n位数

在这里插入图片描述
直接dfs即可，从最大的一个数位开始，考虑所有等可能的情况，每次对于len取余判断，然后结束条件是len=所求数位，并且在区间内

//整除数据
//给一个数n，求区间内被n整除的n位数
//暴力遍历超时是必然的
#include<iostream>
using namespace std;
#define int long long
int shix=0;
int res[10000100];
int n,a,b;
void dfs(int x,int len){if(x%len!=0)return ;if(len==n){if(x<=b && x>=a){//储存答案res[shix++]=x;}}for(int i=0;i<=9;i++){dfs(x*10+i,len+1);}
}
signed main(){cin>>n>>a>>b;for(int i=1;i<=9;i++){dfs(i,1);//i是数字，1是位数}if(shix==0){cout<<"No Solution"<<endl;}else{for(int i=0;i<shix;i++){cout<<res[i]<<endl;}}return 0;
}