题目链接
题意：
输入木马种类 给他们上色
要求 相邻的不同种类的木马不能涂同一种颜色 （环 1与n也是相邻的）
输出最少要几种颜色 并涂色方式
最多三种就能满足题意。
#include <bits/stdc++.h>
using namespace std;
const int N=2e5+10;
void solve()
{
int n;cin>>n;
vector<int> t(n+1);
bool check=false;//是否有相邻且种类相同的
for(int i=1;i<=n;i++)
{
cin>>t[i];
if(t[i]==t[i-1])check=true;
}
if(t[1]==t[n])check=true;//循环
if(count(t.begin(),t.end(),t[1])==n)//所有数相同
{
cout<<"1"<<endl;
for(int i=1;i<=n;i++)cout<<"1 ";
}
else if(n%2==0)// 1 2 1 2...一定满足 不同type不同颜色
{
cout<<"2"<<endl;
for(int i=1;i<=n;i++)cout<<i%2+1<<" ";
}
else if(check)//可以将两个相同的数“合并” 使n变成偶数
{
cout<<"2"<<endl;
for(int i=1;i<=n;i++)
{
if(t[i]==t[i-1]) check=false;
if(check)cout<<i%2+1<<" ";
else cout<<(i+1)%2+1<<" ";
}
}
else //所有type都不同 且为奇数 所以最后一个颜色为3
{
cout<<"3"<<endl;
for(int i=1;i<=n-1;i++)cout<<i%2+1<<" ";
cout<<"3";
}
cout<<endl;
}
int main()
{
int T;cin>>T;
while(T--)
{
solve();
}
return 0;
}