巅峰赛#28 题解
2025-12-08 18:50:09
发布于：江苏
11阅读
0回复
0点赞
个人难度T3<T5<T1<T4<T2<T6
T1
由题意+简单思考得：
最左边只能用，最右边只能用，剩下的两种都可以，有一个可以不选。
#include<bits/stdc++.h>
using namespace std;
long long n,a[200005],b[200005],maxn,num;
int main(){
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=1;i<=n;i++){
cin>>b[i];
if(i==n)b[i]=a[i];
else if(i!=1)b[i]=min(a[i],b[i]);
num+=b[i];
maxn=max(maxn,b[i]);
}
cout<<num-maxn;
}
T2
二分+01bfs
#include<bits/stdc++.h>
using namespace std;
long long n,m,k,sx,sy,tx,ty,a[1005][1005],vis[1005][1005],l,r=1e9,mid,dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
char c[1005][1005];
struct kk{
int x,y,v,w;
};
deque<kk>q;
bool bfs(int x){
q.clear();
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
vis[i][j]=0;
q.push_back({sx,sy,k,0});
while(q.size()){
kk f=q.front();
q.pop_front();
if(f.x==tx&&f.y==ty){
return true;
}
for(int i=0;i<4;i++){
int nx=f.x+dx[i],ny=f.y+dy[i];
int nw=abs(a[f.x][f.y]-a[nx][ny]);
if(nx<1||ny<1||nx>n||ny>m||c[nx][ny]=='#')continue;
if(f.v&&nw>x&&!vis[nx][ny]){
vis[nx][ny]=1;
q.push_back({nx,ny,f.v-1,f.w});
}
if(nw<=x&&vis[nx][ny]<=1){
vis[nx][ny]=2;
q.push_front({nx,ny,f.v,max(f.w,nw)});
}
}
}
return false;
}
int main(){
cin>>n>>m>>k;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
cin>>c[i][j];
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
cin>>a[i][j];
cin>>sx>>sy>>tx>>ty;
if(!bfs(1e9)){
cout<<-1;
return 0;
}
while(l<r){
mid=(l+r)/2;
if(bfs(mid))r=mid;
else l=mid+1;
}
cout<<l;
}
T3
根据层序把中序遍历分成左右子树
#include<bits/stdc++.h>
using namespace std;
long long n,a[200005],b[200005],s[200005][2],m[200005],cnt;
map<long long,long long>mp;
struct k{
int l,r,fa;
};
queue<k>q;
void dfs(int n){
cout<<b[n]<<" ";
if(s[n][0])dfs(s[n][0]);
if(s[n][1])dfs(s[n][1]);
}
int main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
mp[a[i]]=i;
}
for(int i=1;i<=n;i++)cin>>b[i];
q.push({1,n,0});
while(q.size()){
cnt++;
k f=q.front();
q.pop();
int id=mp[b[cnt]];
s[f.fa][m[f.fa]++]=cnt;
if(id>f.l)q.push({f.l,id-1,cnt});
if(id<f.r)q.push({id+1,f.r,cnt});
}
dfs(1);
}
T4
深搜
#include<bits/stdc++.h>
using namespace std;
int n,m,sx,sy,vis[25][25],dx[4]={-1,0,1,0},dy[4]={0,-1,0,1};
char c[25][25];
bool dfs(int lx,int ly,int l){
bool ans=false;
if(l==1)ans=true;
vis[lx][ly]=1;
for(int i=0;i<4;i++){
int nx=lx+dx[i],ny=ly+dy[i];
if(nx<1||nx>n||ny<1||ny>m||vis[nx][ny]||c[nx][ny]=='#')continue;
if(l==1)ans=(ans&dfs(nx,ny,0));
else ans=(ans|dfs(nx,ny,1));
}
vis[lx][ly]=0;
return ans;
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>c[i][j];
if(c[i][j]=='S')sx=i,sy=j;
}
}
vis[sx][sy]=1;
if(sy>1&&c[sx][sy-1]!='#'&&dfs(sx,sy-1,1))cout<<"WIN\n"<<sx<<" "<<sy<<" "<<sx<<" "<<sy-1;
else if(sx>1&&c[sx-1][sy]!='#'&&dfs(sx-1,sy,1))cout<<"WIN\n"<<sx<<" "<<sy<<" "<<sx-1<<" "<<sy;
else if(sy<m&&c[sx][sy+1]!='#'&&dfs(sx,sy+1,1))cout<<"WIN\n"<<sx<<" "<<sy<<" "<<sx<<" "<<sy+1;
else if(sx<n&&c[sx+1][sy]!='#'&&dfs(sx+1,sy,1))cout<<"WIN\n"<<sx<<" "<<sy<<" "<<sx+1<<" "<<sy;
else cout<<"LOSE";
}
T5
区间DP
#include<bits/stdc++.h>
using namespace std;
int n,dp[605][605];
string s;
int main(){
cin>>s;
n=s.size();
s=' '+s;
for(int i=1;i<=n;i++)dp[i][i]=1;
for(int i=2;i<=n;i++){
for(int l=1;l<=n-i+1;l++){
int r=l+i-1;
dp[l][r]=0x3f3f3f;
if(s[l]==s[r]){
if(dp[l+1][r-1]<=1)dp[l][r]=1;
else dp[l][r]=dp[l+1][r-1];
}
for(int j=l;j<r;j++)dp[l][r]=min(dp[l][r],dp[l][j]+dp[j+1][r]);
}
}
cout<<dp[1][n];
}
有帮助，赞一个