D. Carousel

题意

给你一个长度为 n ( n > 3 ) n(n>3) n(n>3)的数组，首尾相连形成一个环。对每个位置进行涂色，要求相邻但不相同数字的填涂颜色不同，相邻且相同的位置颜色可以相同也可以不相同。要求所用颜色的最大数字最小，颜色由数字来表示。

思路

分类讨论 构造

  • 全部为同一种颜色，则全为1即可。
  • 至少有一个位置与其相邻的数字相同，则我们可以从这个相同的位置剖开这个环，形成一条线，再从头到尾1,2交替的填入即可。
  • n为偶数，交替填入1,2即可，首尾必不相同。
  • 全部不相同且为奇数，第一个填入3，后面交替填入1,2即可。

这道题需要仔细严谨的分情况去考虑，关键点在于抓住题干中的两相邻数字相同时可相同也可不同，从而想到两相邻数字相同时，可以从中剖开交替填入1,2。

解锁绑定cin/scanf cout/printf之后要注意不能用puts putchar getchar之类的
don’t mix cin/scanf, cout/printf!

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
const double eps = 1e-8;
const int NINF = 0xc0c0c0c0;
const int INF  = 0x3f3f3f3f;
const ll  mod  = 1e9 + 7;
const ll  maxn = 2e5 + 5;

int n,a[maxn];

bool jud1(){
	bool flag=0;
	for(int i=1;i<=n;i++) if(a[i]!=a[i%n+1]){flag=1;break;}
	if(flag) return 0;
	cout<<"1\n";
	for(int i=1;i<=n;i++) cout<<1<<" ";
	puts("");
    return 1;
}

bool jud2(){
	bool flag=0;int pos=0;
	for(int i=1;i<=n;i++) if(a[i]==a[i%n+1]){pos=i;flag=1;break;}
	if(!flag&&(n%2)) return 0;
	cout<<2<<"\n";
	for(int i=1;i<=n;i++){//这下面的代码很丑 某大佬WZYYN用的是 printf("%d ",1+(i-p+n)%n%2);一句话就搞定了从中剖开交替输出的含义。
		if(i<=pos){
			if((pos-i)&1){
				cout<<"1 ";
			}else cout<<"2 ";
		}else{
			if(pos&1){
				if((n-i)&1) cout<<"2 ";
				else cout<<"1 ";
			}else{
				if((n-i)&1) cout<<"1 ";
				else cout<<"2 ";
			}
		}
	}
	puts("");
    return 1;
}

void jud3(){
	cout<<"3\n3";
	for(int i=2;i<=n;i++) cout<<" "<<1+(i&1);
	puts("");
}

void solve(){
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	if(jud1()) return;
    if(jud2()) return;
    jud3();
}

int main(){
	int T;cin>>T;
	while(T--) solve();
	return 0;
}