专栏文章

题解：P14448 [ICPC 2025 Xi'an R] Beautiful Dangos

___pyx__
P14448题解参与者 3已保存评论 3

文章操作

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

当前评论
3 条
当前快照
1 份
快照标识符
@mina4jil
此快照首次捕获于
2025/12/01 23:03
3 个月前
此快照最后确认于
2025/12/01 23:03
3 个月前
查看原文
真没招了，重现赛最后二十分钟快写完了结果被同学关电脑了，痛失场切。所以这篇题解没有完整代码。
如果想看如何判断是否能使一个区间排序后满足要求，那还是去看官方题解吧。本人数学不行。

题意

给你一个序列，让你求差最小的 ll 和 rr，使对下标 ll 到 rr 重排后可以使这个序列相同的数不相邻。特别的，这个序列中只有至多三种数。

做法

考虑用双指针来扫。先求出左边往右边的第一个有相邻并相同的数的位置 LL，再求出从右往左第一个有相邻并相同的数的位置 RR。取指针 ll 为 11，rr 为 RR。此时 ll 到 rr 包含了所有相邻且相同的数。如果无法对此区间进行排序使这段区间与旁边两侧的数（各只用考虑一个，因为更远的已经满足要求）合并起来符合要求，那么把 rr 往右移直到满足要求。再在满足要求的情况下将 ll 右移直到不满足要求的前一个，更新答案。接着把 ll 右移一个。一直扫到 ll 扫到 LL 时或 rr 扫到 nn 并且不满足要求时结束。
计算是否符合要求可以用前缀和来维护，算出三种数各有多少个，再考虑左右两个数，就是组合问题了。另外开头需要先计算一下整个序列是否可以变成满足条件的序列，和是否原来就满足条件。
最后输出可以把 anslansl 往左和 ansransr 往右都按原序列打印出来，中间的用前缀和求一下每个数的数量，组合咋算的咋输出就可以了。
中间输出再说一句，要注意记录上一个颜色是什么，然后尽可能的先输出与其不相同的剩余更多的颜色。相同数量就看看 ansransr 右边那个是什么，优先输出。注意判 anslansl 为 11 的情况第一个颜色应该输出什么。
其实可以把前缀和省掉，边扫变更新，更省空间。
给出部分关键代码。
CPP
l=1,r=R-1;     //双指针
ansl=0,ansr=n+1;
while(l<=L+1){
	while(r<=n&&!query(l,r))r++;
	if(r>n)break;
	while((l<L+1)&&query(l+1,r))l++;
	if((ansr-ansl)>(r-l)){
		ansr=r,ansl=l;
	}
	if(l==L+1)break;
	l++;
}
还有丑陋的判断是否符合要求（不要嘲笑我可以吗）。
CPP
inline bool query(int l,int r){
	int x1=s1[r]-s1[l-1],x2=s2[r]-s2[l-1],x3=s3[r]-s3[l-1];
	int y=(r-l+1);
	int g;
	if(y%2==1){
		if(x1>(y/2+1)||x2>(y/2+1)||x3>(y/2+1)){
			return false;
		}
	}
	else {
		if(x1>y/2||x2>y/2||x3>y/2){
			return false;
		}
	}
	if(l==1&&r==n){
		return true;
	}
	if(l==1||r==n){
		int g;
		if(l==1)g=a[r+1];
		else g=a[l-1];
		if(y%2==0)return true;
		if(g==1){
			if(x1==(y/2+1))return false;
		}
		if(g==2){
			if(x2==(y/2+1))return false;
		}
		if(g==3){
			if(x3==(y/2+1))return false;
		}
		return true;
	}
	if(a[l-1]==a[r+1]){
		g=a[l-1];
		if(y%2==0){
			if(g==1){
				if(x1==(y/2))return false;
			}
			if(g==2){
				if(x2==(y/2))return false;
			}
			if(g==3){
				if(x3==(y/2))return false;
			}
			return true;
		}
		if(y%2==1){
			if(g==1){
				if(x1==(y/2+1))return false;
			}
			if(g==2){
				if(x2==(y/2)+1)return false;
			}
			if(g==3){
				if(x3==(y/2)+1)return false;
			}
			return true;
		}
	}
	int g1=a[l-1],g2=a[r+1];
	if(y%2==0)return true;
	if(g1==1||g2==1){
		if(x1==(y/2+1))return false;
	}
	if(g1==2||g2==2){
		if(x2==(y/2+1))return false;
	}
	if(g1==3||g2==3){
		if(x3==(y/2+1))return false;
	}
	return true;
}

评论

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

正在加载评论...