自动搬运

查看原文

来自洛谷，原作者为

	342zhuyongqi **

搬运于2025-08-24 21:51:31，当前版本为作者最后更新于2018-08-07 10:54:21，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

利用构造法贪心求解。

因为可以操作n次，一共3n个，所以可以把每3个分成一组

一共有8种可能

000

111

011

100

110

001

010

101

对于010 101不用改变

对于011 100换前2个

对于110 001换后2个

对于111 000看前面就行了

#include<stdio.h>
#include<string.h>
int n;
char a[300010];
int ans[100010],ans2;
int idx,sum,t;
#define a1 (i-1)*3+1
#define a2 (i-1)*3+2
#define a3 (i-1)*3+3
int main()
{
	scanf("%s",a+1);
	int l=strlen(a+1);
	for(int i=1;i<=l;i++)
		a[i]=a[i]-'0';
	for(int i=1;i<=l;i++)
		if(a[i]!=a[i+1])
			ans2++;
	if(ans2>=l/3*2+1)
	{
		printf("0");
		return 0;
	}
	for(int i=1;i<=l/3;i++)
	{
		if((a[a1]==a[a2])&&(a[a2]!=a[a3]))
		{
			sum++;
			if(a[a2]==1)
				a[a2]=0;
			else
				a[a2]=1;
			if(a[a3]==1)
				a[a3]=0;
			else
				a[a3]=1;			
			ans[++idx]=a2;
		}
		else if((a[a1]!=a[a2])&&(a[a2]!=a[a3]))
			continue;
		else if((a[a1]!=a[a2])&&(a[a2]==a[a3]))
		{
			sum++;
			if(a[a2]==1)
				a[a2]=0;
			else
				a[a2]=1;
			if(a[a1]==1)
				a[a1]=0;
			else
				a[a1]=1;			
			ans[++idx]=a1;			
		}
		else
		{
			if(a[a1]==a[(i-1)*3])
			{
				sum++;
				if(a[a1]==1)
					a[a1]=0;
				else
					a[a1]=1;
				if(a[a2]==1)
					a[a2]=0;
				else
					a[a2]=1;			
				ans[++idx]=a1;				
			}
			else
			{
				sum++;
				if(a[a3]==1)
					a[a3]=0;
				else
					a[a3]=1;
				if(a[a2]==1)
					a[a2]=0;
				else
					a[a2]=1;			
				ans[++idx]=a2;				
			}
		}
	}
	printf("%d\n",sum);
	for(int i=1;i<=sum;i++)
	{
		if(i!=sum)
			printf("%d ",ans[i]);
		else 
			printf("%d",ans[i]);		
	}
}