2025年GPLT团体程序设计天梯赛L1-L2

目录

1.珍惜生命

2.偷感好重

 3.高温补贴

 4.零头就抹了吧

5.这是字符串题

 6.这不是字符串题

 7.大幂数​编辑

 8.现代战争​编辑

9.算式拆解

10.三点共线 

11.胖达的山头

12.被n整除的n位数

---

1.珍惜生命

【解析】直接输出即可

#include<bits/stdc++.h>
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.";
} 

2.偷感好重

【解析】直接将三个数相加即可

#include<bits/stdc++.h>
using namespace std;
int main(){
int a,b,c;
cin>>a>>b>>c;
int sum=a+b+c;
cout<<sum;	
}

 3.高温补贴

【解析】这题才开始正向根据题意即先考虑是否补贴的话题意可能有些不清楚，那我们逆着想不补贴的情况写了，剩下的就是补贴的了。

#include<bits/stdc++.h>
using namespace std;
int main(){int T,s,t;cin>>T>>s>>t;int f=0;if((T>35&&t>=33)&&!s){
cout<<"Shi Nei"<<endl;
cout<<T;	}else if(s&&(T<=35||t<33)){cout<<"Bu Re"<<endl;cout<<t;}else if((T<=35||t<33)&&!s){cout<<"Shu Shi"<<endl;cout<<t;}else{cout<<"Bu Tie"<<endl;cout<<T;}}

 4.零头就抹了吧

【解析】 二进制取整

 #include<bits/stdc++.h>
using namespace std;
int n;
vector<int> a;
int main(){cin>>n;while(n){a.push_back(n>>1);n>>=1;
}
int k=1;
for(int i=0;i<a.size()-1;i++){k<<=1;
}
cout<<k;
}

5.这是字符串题

【解析】数组模拟

#include<bits/stdc++.h>
using namespace std;
string s;
int a[27],b[27];
long long sum=0;
int main(){
cin>>s;
memset(b,0,sizeof(b));
for(int i=0;i<26;i++){cin>>a[i];
}
for(int i=0;i<s.size();i++){sum+=a[s[i]-'a'];b[s[i]-'a']++;
}
for(int i=0;i<26;i++){cout<<b[i];if(i!=25)cout<<" ";
}
cout<<endl;
cout<<sum;	
} 

 6.这不是字符串题

【解析】哇，这个不是字符串题比不是字符串题要难得多啊，我的思路是数组纯模拟 

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int  a[N];
int m,n;
string s;
void slove1(){ 	
int b[N],c[N];int x,y;;cin>>x;for(int i=0;i<x;i++)cin>>b[i];cin>>y;for(int i=0;i<y;i++)cin>>c[i];int i=1,j=0;while(i<=n){if(a[i]==b[j])j++;else j=0;if(j==x)break;i++;	}  if(j==x){int d[N],cnt=0;for(int p=i+1;p<=n;p++)d[cnt++]=a[p]; int  p,q;for(p=i-x+1,q=0;q<y;q++,p++)a[p]=c[q]; for(q=p,i=0;i<cnt;i++)a[q++]=d[i];n=q-1;}	
}
void slove2(){for(int i=1;i<n;i++){if((a[i]+a[i+1])%2==0){int b[N];int k=(a[i]+a[i+1])/2;int cnt=0;for(int j=0,p=i+1;p<=n;p++,j++){b[j]=a[p];cnt++;}a[i+1]=k;   for(int j=i+2,p=0;p<cnt;j++,p++){a[j]=b[p];} n++;i++;}	}
}
void slove3(){int i,j;cin>>i>>j;int k[j-i+10];for(int p=0,q=i;q<=j;q++,p++){k[p]=a[q];}for(int p=j-i,q=i;q<=j;q++,p--){a[q]=k[p];}
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i];
}
for(int i=0;i<m;i++){int x;cin>>x;if(x==1){slove1();}else if(x==2){slove2();	}else if(x==3){slove3();	}
}  
cout<<a[1];for(int i=2;i<=n;i++)
cout<<" "<<a[i];
}

 7.大幂数

【解析】数据范围不是很大，可以暴力枚举

#include<bits/stdc++.h>
using namespace std;
int main(){int n;cin>>n;int f=0;int res,c;//降幂寻找// 2<n<2^31 意味着幂次最大为31  for(int i=31;i>=1;i--){//必须开long long 否则会爆！！！ long long sum=1,j=2;while(sum<n){sum+=pow(j,i);if(sum==n){f=1;res=j;c=i;break;}j++;}//最大幂找到后退出 if(f)break;	}if(f){printf("1^%d",c);for(int l=2;l<=res;l++)printf("+%d^%d",l,c);}else printf("Impossible for %d.",n); 
}

 8.现代战争

【解析】模拟

#include<bits/stdc++.h>
using namespace std;
long long g[1010][1010];
long long max_x=-0x3f3f3f3f3f;
int main(){int n,m,k;cin>>n>>m>>k;int x,y; for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){cin>>g[i][j];if(g[i][j]>=max_x){x=i,y=j;max_x=g[i][j];}}}while(k--){for(int p=1;p<=n;p++){g[p][y]=-0x3f3f3f3f3f;}for(int p=1;p<=m;p++){g[x][p]=-0x3f3f3f3f3f;}max_x=-0x3f3f3f3f;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){if(g[i][j]>=max_x){x=i,y=j;max_x=g[i][j];}}	}
}
int c1=1;for(int i=1;i<=n;i++){int c=1,f=0;for(int j=1;j<=m;j++){if(!f&&g[i][j]!=-0x3f3f3f3f3f){f=1;cout<<g[i][j];}else if(g[i][j]!=-0x3f3f3f3f3f&&f){cout<<" "<<g[i][j];}}if(c1<=n-k&&f)cout<<endl;if(f)c1++;
}
}

9.算式拆解

 【解析】这个题就是模拟栈的过程

#include<bits/stdc++.h>
using namespace std;
char s[150];
vector<char> h,k; 
int main(){scanf("%s",s);for(int i=0;i<strlen(s);i++){ 
//当遇到")"弹出if(s[i]==')') {while(h.size()&&h.back()!='('){char x=h.back();h.pop_back();k.push_back(x);}h.pop_back();while(k.size()){char x=k.back();k.pop_back();cout<<x;	}cout<<endl;}else h.push_back(s[i]);
}
}

10.三点共线 

【解析】这个地方我直接用的暴力枚举和离散化处理。这题也有一个前置条件，即满足共线的条件x2=2*x1-x0。

#include<bits/stdc++.h>
using namespace std;
int n;
//便于离散化处理
const int N=4e6;
vector<int>a,b; 
bool c[2*N+10];
int main(){cin>>n;//输入for(int i=0;i<n;i++){int x,y;cin>>x>>y;if(y==0)a.push_back(x);else if (y==1)b.push_back(x);else c[x+N]=true; }//进行去重，防止重复遍历sort(a.begin(),a.end());sort(b.begin(),b.end());a.erase(unique(a.begin(),a.end()),a.end());b.erase(unique(b.begin(),b.end()),b.end());//暴力枚举int k=0;for(int j=0;j<b.size();j++){for(int i=0;i<a.size();i++){
//满足共线条件int x3=2*b[j]-a[i];//离散化操作if(c[x3+N]){k=1;printf("[%d, 0] [%d, 1] [%d, 2]\n",a[i],b[j],x3);
}}
}
if(k==0)
cout<<-1;
}

11.胖达的山头

【解析】1.区间分组问题

#include<bits/stdc++.h>
using namespace std;
const int N=100010;
struct Range{int l,r;
}range[N];
bool cmp(Range x,Range y)
{return x.l<y.l;
}
int main()
{int n;cin>>n;for(int i=0;i<n;i++){
string a,b;
cin>>a>>b;
int p=0,q=0;for(int i=0;i<a.size();i++){if(a[i]!=':')p*=10,p+=a[i]-'0';
}
for(int i=0;i<b.size();i++){if(b[i]!=':')q*=10,q+=b[i]-'0';
}
range[i].l=p;
range[i].r=q;	
}sort(range,range+n,cmp);priority_queue<int,vector<int>,greater<int>> heap;for(int i=0;i<n;i++){if(heap.empty()||heap.top()>=range[i].l) heap.push(range[i].r);else {heap.pop();heap.push(range[i].r);}}cout<<heap.size();return 0;
}

 2.将题目转化为在同一时刻最多有多少只胖达同时处于活跃状态，这个最大并发活跃数就是我们最少需要的山头数量，利用差分来写。具体的可以看PAT 2025天梯赛L2-3. 胖达的山头 - AcWing

#include<bits/stdc++.h>
using namespace std;
const int N=250000;
int sum[N];
int n;
int main(){cin>>n;
getchar();
memset(sum,0,sizeof(sum)); 
for(int i=0;i<n;i++){
string a,b;
cin>>a>>b;
int p=0,q=0;for(int i=0;i<a.size();i++){if(a[i]!=':')p*=10,p+=a[i]-'0';
}
for(int i=0;i<b.size();i++){if(b[i]!=':')q*=10,q+=b[i]-'0';
}
sum[p+1]++;
sum[q+2]--;	
}
int ans=0;
for(int i=1;i<N;i++){sum[i]+=sum[i-1];ans=max(ans,sum[i]);
}
cout<<ans;
}

12.被n整除的n位数

【解析】 dfs直接进行暴力搜索。

#include<bits/stdc++.h>
using namespace std;
long long a,b;
int n;
int k[20];
int f=0;
void dfs(int x,long long s){if(x==n){if(s>=a&&s<=b){cout<<s<<endl;f=1;}return ;}for(int i=0;i<=9;i++){long long k=s*10+i;
//回溯前进行判断是否能够被当前位置整除，剪枝if(k%(x+1)==0)dfs(x+1,s*10+i);}}
int main(){cin>>n;cin>>a>>b;
//这里没有保证a,b也是n位数，所以我们要用to_string函数，不能用a-pow(10,n-1)int l=to_string(a)[0]-'0';int r=to_string(b)[0]-'0';for(int i=l;i<=r;i++)dfs(1,i); if(!f)cout<<"No Solution";
}