自动搬运

查看原文

来自洛谷，原作者为

	Eznibuil whk 失败者 | 谁念征人苦，孤军夜夜归 | /article/rrrtvz2o

搬运于2025-08-24 22:52:25，当前版本为作者最后更新于2024-03-16 17:26:05，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

首先考虑解出每个火把需要被点奇数次还是偶数次。这个是简单的，如果 $n$ 不是 $3$ 的倍数则强行解，如果 $n$ 是 $3$ 的倍数则钦定一个然后强行解即可。

现在每个火把有两个属性：亮还是灭，还要点奇数次还是偶数次。如果场上有本来就还需要点奇数次的火把是灭的，点。该操作是一步干掉一个奇数。

这时候场上没有还需要点奇数次的灭的火把了。如果此时所有火把都亮了自然很好。假设有一个火把没有亮，叫它中间火把，那么必然它还需要被点偶数次，所以左右两侧一定要给它贡献奇数次，所以左右必然有一个还需要点奇数次，假设是右侧，那么肯定是亮的。而由于右侧火把是亮的，需要被贡献偶数次，而中间火把又只能贡献偶数次，所以右侧的右侧必然需要贡献奇数次，因此必然也是亮的。于是四个火把（左、中、右、右的右）依次是未知、灭、亮、亮，且还需点的次数分别是偶、偶、奇、奇。

人类智慧一波，构造一个依次点亮中、右、中、右的右，那么状态会转化为未知（不变）、亮、亮、亮，且还需点的次数为偶、偶、偶、偶。发现使用四步干掉了两个奇数，结合前面的一步干掉一个奇数，总共次数不会超过 $2n$。

显然每次操作都是 $O(1)$ 的，维护起来相当简单，因此本题时间复杂度 $O(n)$。

#include<iostream>
char s[1000001];
int a[1000001],b[1000001],e[1000001];
int main()
{
	std::cin.tie(0)->sync_with_stdio(0);
	int t;
	std::cin>>t;
	while(t--)
	{
		int n;
		std::cin>>n>>s;
		for(int i=0;i<n;i++)
			a[i]=s[i]^'0';
		if(n%3)
		{
			b[0]=0;
			for(int i=3;i<3*n;i+=3)
				b[i%n]=b[(i-3)%n]^a[(i-2)%n]^a[(i-1)%n];
			if(a[0]!=b[n-1]^b[0]^b[1]^1)
				for(int i=0;i<n;i++)
					b[i]^=1;
		}
		else
		{
			b[0]=b[1]=b[2]=0;
			for(int i=3;i<n;i++)
				b[i]=b[i-3]^a[i-2]^a[i-1];
			if(a[0]!=b[n-1]^b[0]^b[1]^1)
				for(int i=0;i<n;i+=3)
					b[i]^=1;
			bool f=1;
			for(int i=0;f&&i<n;i++)
				if(a[i]^b[i]^b[(i+n-1)%n]^b[(i+1)%n]!=1)
					f=0;
			if(!f)
			{
				std::cout<<"0\n";
				continue;
			}
		}
		for(int i=0;i<n;i++)
			if(a[i]^b[i]^b[(i+n-1)%n]^b[(i+1)%n]!=1)
				return 1;
		int le=0;
		const auto p=[&](int x){a[x?x-1:n-1]^=1,a[x]^=1,a[x<n-1?x+1:0]^=1,b[x]^=1,e[le++]=x;};
		if(!a[0]&&b[0])
			p(0);
		if(!a[1]&&b[1])
			p(1);
		for(int _=0;_<3;_++)
			for(int i=0;i<n;i++)
				if(!a[(i+2)%n]&&b[(i+2)%n])
					p((i+2)%n);
				else if(!a[i]&&!b[i]&&a[(i+1)%n]&&b[(i+1)%n]&&a[(i+2)%n]&&b[(i+2)%n])
				{
					p(i),p((i+1)%n),p(i),p((i+2)%n);
					for(int j=(i+3)%n;!a[j]&&b[j];j=j<n-1?j+1:0)
						p(j);
				}
		std::cout<<le;
		for(int i=0;i<le;i++)
			std::cout<<" \n"[!i]<<e[i]+1;
		std::cout<<'\n';
	}
	return 0;
}