CSP-S模拟赛 T4详解（私有勿看）
2025-08-19 13:51:21
发布于：浙江
坐看云卷云舒，千纸鹤的折痕在阳光下叠成阴影。
我到底希望着什么？我的目标是什么？
我问我自己。
——————————————————————————————————————————————
链接描述
先分析题目意思：
有个高度互不相同的猫爬架，其高度。
有对猫爬架相邻。
初始时，猫猫可以从任意一个猫爬架经过若干次飞跃到达另一个猫爬架。
现在要在猫爬架上放障碍：
如果猫猫不在被选中的猫爬架上，无事发生。
否则：
猫猫会移动到除去当前猫爬架外，高度最大的且可达的猫爬架上，并选择最短路进行飞跃。
“x猫爬架与y猫爬架可达“的定义：若从x开始，不经过任何障碍物，通过若干次飞跃移动到猫爬架y，则称x与y猫爬架可达。
猫猫初始在高度为的猫爬架上。
求猫在整个训练过程中，飞跃次数之和的最大值。
题目解释：
“选择最短路进行飞跃”不是说FLOYD,SPFA,DIJ.
这是树相关的专业用语，即不会在两个点之间来回走，只走一次。
有对猫爬架相邻，可以联想到有条边。
每次从x飞跃到y，都需要保证猫爬架y的高度小于猫爬架x的高度。
子任务分析：
首先能看到，子任务1-12，是一条链。
那么对于一条链，猫要么往左边走，要么往右边走，大概这样：
如果你希望猫往左边走，而此时目标点却在右边，你可以选择在目标点上放置一个障碍物。
然后猫就会往左边走。
也就是说，你可以选择猫往左边走还是往右边边走。
每次你都会有两种选择。
这种感觉有点像归并排序。
归并排序的思想是分治。
那我们就可以考虑，使用分治来解决这个问题。
然后你就可以开始写代码。
代码大概是这样的：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int p[5005];
int pos[5005];
vector<int>v[5005];
int fd(int l,int r){
int mx=-1;
for(int i=l;i<=r;i++){
mx=max(mx,p[i]);
}
return mx;
}
long long ans;
int dfs(int l,int r,int now){
if(l>r)return 0;
int l_max=fd(l,now-1);
int r_max=fd(now+1,r);
ll l_ans=0,r_ans=0;
if(l_max!=-1)l_ans=now-pos[l_max]+dfs(l,now-1,pos[l_max]);
if(r_max!=-1)r_ans=pos[r_max]-now+dfs(now+1,r,pos[r_max]);
return max(l_ans,r_ans);
}
int main(){
freopen("cat.in","r",stdin);
freopen("cat.out","w",stdout);
int n;
cin>>n;
for(int i=1;i<=n;i++)cin>>p[i],pos[p[i]]=i;
for(int i=1;i<n;i++){
int x,y;
cin>>x>>y;
v[x].push_back(y);
v[y].push_back(x);
}
cout<<dfs(1,n,pos[n]);
fclose(stdin);
fclose(stdout);
return 0;
}
然后发现会有一些超时。
主要超时的原因是找最大值的时候，时间复杂度是。
那么就要考虑如何在短时间内找区间最大值。
先复习一下ST表：
#include<bits/stdc++.h>
using namespace std;
const int N=2e6+5;
int a[N];
int dp[N][21];
int main(){
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=1;i<=n;i++)dp[i][0]=a[i];
for(int k=1;k<=log2(n);k++){
for(int i=1;i<=n;i++){
if(i+(1<<(k-1))>n)continue;
dp[i][k]=min(dp[i][k-1],dp[i+(1<<(k-1))][k-1]);
}
}
for(int i=1;i<=m;i++){
int x,y;
cin>>x>>y;
int k=log2(y-x+1);
cout<<min(dp[x][k],dp[y-(1<<k)+1][k])<<" ";
}
return 0;
}
然后将它们合成一下：（注意数据范围变大后要开longlong）
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int p[200005];
int pos[200005];
int f[200005][21];
vector<int>v[200005];
int fd(int l,int r){
if(l>r)return -1;
/*int mx=-1;
for(int i=l;i<=r;i++){
mx=max(mx,p[i]);
}
return mx;*/
int k=log2(r-l+1);
return max(f[l][k],f[r-(1<<k)+1][k]);
}
ll ans;
ll dfs(int l,int r,int now){
if(l>r)return 0;
int l_max=fd(l,now-1);
int r_max=fd(now+1,r);
ll l_ans=0,r_ans=0;
if(l_max!=-1)l_ans=now-pos[l_max]+dfs(l,now-1,pos[l_max]);
if(r_max!=-1)r_ans=pos[r_max]-now+dfs(now+1,r,pos[r_max]);
return max(l_ans,r_ans);
}
int main(){
freopen("cat.in","r",stdin);
freopen("cat.out","w",stdout);
int n;
cin>>n;
for(int i=1;i<=n;i++)cin>>p[i],pos[p[i]]=i;
for(int i=1;i<=n;i++)f[i][0]=p[i];
for(int k=1;k<=log2(n);k++){
for(int i=1;i<=n;i++){
if(i+(1<<(k-1))>n)continue;
f[i][k]=max(f[i][k-1],f[i+(1<<(k-1))][k-1]);
}
}
for(int i=1;i<n;i++){
int x,y;
cin>>x>>y;
v[x].push_back(y);
v[y].push_back(x);
}
cout<<dfs(1,n,pos[n]);
fclose(stdin);
fclose(stdout);
return 0;
}
这里空空如也
有帮助，赞一个