巅峰赛#28 题解

CuSn

2025-12-08 18:50:09

发布于：江苏

15阅读

0回复

0点赞

个人难度T3<T5<T1<T4<T2<T6

T1

由题意+简单思考得：
最左边只能用 $b_i$ ，最右边只能用 $a_i$ ，剩下的两种都可以，有一个可以不选。

#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];
}