D. Carousel(分类+构造)

\(题目的要求似乎很低:只需要不同类的相邻元素不同色就行了。\)

下面的讨论的话，实际上最后一个点是关键，要想到怎么让最后一个点不开新的颜色就简单了。

\(分情况讨论:\)

\(\color{Red}{Ⅰ.只有一个种类或n=1,那么全涂一种颜色就行了。}\)

\(\color{Purple}Ⅱ、偶数个元素,全涂1和2相间染色，到一定满足要求且最优\)

\(\color{Orange}{Ⅲ.奇数个元素}\)

\(这个时候因为末尾元素可能会和n-1或1号元素颜色相同，所以我们再继续分类\)

\(Ⅲ.1.\ n和n-1的种类相同，和1随意\)

那么前面还是1和2相间染色，最后一个元素和n-1同色，这样保证了和1不同色。

\(Ⅲ.2.\ n和1种类相同,那么直接1和2相间染色\)

\(Ⅲ.3.\ 值得注意的是和两边种类不同时，为了使答案是2，我们要尽可能让1和n-1号元素的颜色相同\)

如果前面有重复元素连在一起，那么我改变一个重复元素不相间染色，后面相间染色，那就和偶数的情况一样

例子:种类:1 1 2 3 4

相间染色:1 2 1 2 1(此时不满足条件)

改变重复元素:1 1 2 1 2(满足条件)

如果没有上面这种情况，只能新开颜色3，给末尾元素涂上3.

#include <bits/stdc++.h>

using namespace std;

const int maxn=2*1e5+9;

int t[maxn],q,n,a[maxn],k;

void print(int k,int w){

	cout<<k<<endl;

	for(int i=1;i<=w;i++)	cout<<a[i]<<" ";

}

int main()

{

	cin>>q;

	while(q--)

	{

		k=1;

		cin>>n;

		int flag=0;

		for(int i=1;i<=n;i++)

		{

			cin>>t[i];

			if(t[i]!=t[i-1]&&i!=1)	flag=1;

		}

		if(flag==0||n==1)//只有一种颜色

		{

			cout<<1<<endl;

			for(int i=1;i<=n;i++)	cout<<1<<" ";

		}

		else

		{

			for(int i=1;i<=n;i++)

			if(i%2==1)	a[i]=1;

			else	a[i]=2;

			if(n%2==0)	print(2,n);

			else

			{

				if(t[n]!=t[n-1]&&t[n]!=t[1])

				{

					int P=0;

					for(int i=2;i<=n-1;i++)

					if(t[i]==t[i-1])	P++;

					if(P>=1)

					{

						a[1]=1;int num;

						for(int i=2;i<=n-1;i++)

						{

							if(t[i]==t[i-1])

							{

								a[i]=a[i-1],num=i+1;

								break;

							}

						}

						for(int i=num;i<=n;i++)

						if(a[i-1]==1)	a[i]=2;

						else	a[i]=1;

						print(2,n);

					}

					else

					{

						a[n]=3;

						print(3,n);

					}

				}

				else if(t[n]!=t[n-1])	print(2,n);//和n-1个不相等

				else if(t[n]!=t[1])//和第一个不相等

				{

					a[n]=2;

					print(2,n);

				}

				else	print(2,n);//都不想等，怎么都可以

			}

		}

		cout<<endl;

	}

}

巴特西

D. Carousel(分类+构造)

最新文章

热门文章