自动搬运

查看原文

来自洛谷，原作者为

	ppllxx_9G One plus one does not equal two

搬运于2025-08-24 23:01:53，当前版本为作者最后更新于2024-08-11 17:33:03，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

题目大意

对于一个长度为 $n$ 的 $01$ 串 $s$，你可以对其进行最多 $r$ 次操作，对于每次操作，你可以选择一个下标 $p$ 满足 $p=1$，$p=n$，$s_{p-1}\not=s_{p+1}$ 中的至少一个，将 $s_p$ 反转。输出操作方案。

解题思路

最大限制次数 $r=10^6$，恰好是 $\frac{n^2}{4}$ 次，所以考虑能否使每一个位置的操作次数近似 $\frac{n}{4}$。所以想到从中点向两侧遍历。每侧 $\frac{n}{2}$ 个点，每个点可以进行 $\frac{n}{4}$ 次操作。

显然，如果一个点当前不能被改变，那我们能通过改变它一侧的点，使它变成可以被改变状态。其实这就是一个递归求解的过程。

• 对于中点左侧的点，如果不能被改变，选择向左递归。
• 对于中点右侧的点，如果不能被改变，选择向右递归。

这样我们先钦定中间两个点，使其变成一样的（最多需要 $\frac{n}{2}$ 次）。然后向左右分别求解（还剩 $\frac{n}{2}-1$ 个点），最坏情况是 $\frac{\frac{n}{2}(\frac{n}{2}-1)}{2} \times 2$ 次，加上最开始钦定时的 $\frac{n}{2}$ 次，刚刚好（应该卡不到吧）。

AC 代码

#include<bits/stdc++.h>
using namespace std;
const int N = 2e3+5;
int n,a[N],r,ans,op[2000005],limit;
inline void change(int x,int o)
{
	if(x==1||x==n||a[x-1]!=a[x+1]) return a[x]^=1,op[++ans]=x,void(0);
	if(o) change(x-1,o),a[x]^=1,op[++ans]=x;
	else change(x+1,o),a[x]^=1,op[++ans]=x;
}
int main()
{
	scanf("%d%d",&n,&limit);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	int l=n>>1,r=l+1;
	if(a[l]!=a[r]) change(l,1);
	l--,r++;
	while(l>=1) a[l]!=a[l+1]?change(l,1),l--:l--;
	while(r<=n) a[r]!=a[r-1]?change(r,0),r++:r++;
	printf("%d\n",ans);
	for(int i=1;i<=ans;i++) printf("%d ",op[i]);
	return 0;
}