题解：P13524 [KOI 2025 #2] 跳跃

HNO_3 · 2025-11-04 16:00:37 · 题解

P13524 跳跃 题解

分析

• 首先，对于子任务 1，暴力枚举即可，复杂度为 O(n^2 \times (n-2)!)。
• 假设原始排列为 1,2,3,\ldots,n，每一个点的原始贡献为 1，将一个点向前移贡献会加上 2，如 1,2,4,3,5 中 4 的贡献由 1 变成了 3，对应 c 序列由 1,1,1,1 变成了 1,1,3,1，而对应的 3 也后移（所以子任务 2 其实是由 1,3 组成的序列，遇到 a_i=3 时交换一下 i 与 i+1 的位置即可），所以对于 c_i-c_{i-1}=2 的时候可以存起来，遇到 c_i-c_{i-1}=-2 的时候把栈顶拿出来，使用 nxt_i 记录 i 的映射值，输出时遇到映射值先输出即可。

1. 子任务 2

   for(int i=1;i<=n;++i) p[i]=i;
   for(int i=1;i<n;++i)
       if(a[i]==3) swap(p[i],p[i+1]);
   for(int i=1;i<=n;++i) cout<<p[i]<<' ';

2. 映射实现

   int main()
   {
   ios::sync_with_stdio(false);
   cin.tie(nullptr);cout.tie(nullptr);
   //  freopen("paper.in","r",stdin);
   //  freopen("paper.out","w",stdout);
   cin>>n;
   bool flag=true;
   for(int i=1;i<n;++i){
       cin>>a[i];
       if(a[i]!=1) flag=false;
   }
   if(flag){
       for(int i=1;i<=n;++i) cout<<i<<' ';
       return 0;
   }
   int cnt=0;
   for(int i=2;i<n;++i){
       if(a[i]-a[i-1]==2){
           p[++cnt]=i;
       }
       if(a[i]-a[i-1]==-2){
           nxt[p[cnt]]=i;
           nxt[i]=p[cnt];
           --cnt;
       }
   }
   cout<<"1 ";
   for(int i=1;i<n;++i){
       if(a[i]-a[i-1]==2) cout<<nxt[i]<<' '<<i<<' ';
       if(a[i]-a[i-1]==0) cout<<i<<' ';
   }
   cout<<n<<' ';
   return 0;
   }

   ::::info[注意事项] 注意首尾固定，可以单独输出，c_i-c_{i-1}=2 与 c_i-c_{i-1}=-2 的情况选择一种输出即可（c_i-c_{i-1}=-2 时先输出 i 再输出 nxt_i）。 ::::

时间复杂度 O(n)。