专栏文章

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

ffengyuchen666
P13524题解参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@mindtzbu
此快照首次捕获于
2025/12/02 00:47
3 个月前
此快照最后确认于
2025/12/02 00:47
3 个月前
查看原文

P13524 跳跃 题解

分析

  • 首先，对于子任务 11，暴力枚举即可，复杂度为 O(n2×(n−2)!)O(n^2 \times (n-2)!)。
  • 假设原始排列为 1,2,3,…,n1,2,3,\ldots,n，每一个点的原始贡献为 11，将一个点向前移贡献会加上 22，如 1,2,4,3,51,2,4,3,5 中 44 的贡献由 11 变成了 33，对应 cc 序列由 1,1,1,11,1,1,1 变成了 1,1,3,11,1,3,1，而对应的 33 也后移（所以子任务 22 其实是由 1,31,3 组成的序列，遇到 ai=3a_i=3 时交换一下 ii 与 i+1i+1 的位置即可），所以对于 ci−ci−1=2c_i-c_{i-1}=2 的时候可以存起来，遇到 ci−ci−1=−2c_i-c_{i-1}=-2 的时候把栈顶拿出来，使用 nxtinxt_i 记录 ii 的映射值，输出时遇到映射值先输出即可。
  1. 子任务 22
CPP
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]<<' ';
  1. 映射实现
CPP
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;
}
注意事项
注意首尾固定，可以单独输出，ci−ci−1=2c_i-c_{i-1}=2 与 ci−ci−1=−2c_i-c_{i-1}=-2 的情况选择一种输出即可（ci−ci−1=−2c_i-c_{i-1}=-2 时先输出 ii 再输出 nxtinxt_i）。
时间复杂度 O(n)O(n)。

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...