自动搬运

查看原文

来自洛谷，原作者为

	VinstaG173 Si Dieu n'existait pas, il faudrait l'inventer.

搬运于2025-08-24 22:34:18，当前版本为作者最后更新于2021-11-04 01:30:28，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

简单结论+构造题。

显然若 $x+1<l$，$l \le x<r$ 或 $x \ge r$，则有 $x,x+1$ 位置上的字母相同性在对 $[l,r]$ 任意操作后不变，即原来相同操作后也相同，原来不同操作后也不同。故一次操作 $[l,r]$ 最多只可能让相邻不同对数增加 $2$。故设最初相邻相同对数为 $x$，至少要 $\left\lceil\dfrac{x}{2}\right\rceil$ 次操作才能使得相邻均不相同。

以下给出构造。由以上分析得每次操作 $[l,r]$ 必然在 $l-1,l$ 与 $r,r+1$ 两个相邻位置均由相同变为不同。特别的，若 $x$ 是奇数，则有一次操作只需要对 $[l,n]$ 将 $l-1,l$ 变为不同。这样我们只要找出相邻相同组再任意分组即可。事实上直接取头尾很容易实现。时间复杂度 $O(n)$。

感觉开这个数据范围是 checker 的缘故。

Code:

#include<cstdio>
int n,x,y,t;
char s[5003];
int l[5003],r[5003];
int main()
{
	scanf(" %d %s",&n,s+1);x=1,y=n;
	while(x<y)
	{
		while(x<y&&s[x]!=s[x+1])++x;
		while(y>x&&s[y]!=s[y-1])--y;
		if(x==y)break;
		l[++t]=++x,r[t]=--y;
	}
	printf("%d\n",t);
	if(l[t]>r[t])r[t]=n;
	for(int i=1;i<=t;++i)printf("%d %d BCA\n",l[i],r[i]);
	return 0;
}