CF 1328 D. Carousel(环构造)

Problem - D - Codeforces

大意：给出一个 n 个数组成的环 ， 要对环上的点染色 ， 要求任意一个相邻数不同的点对染色不同 ，求使用最少的颜色数 ， 并用颜色数排列构造一种染色方案。

思路：手模一下发现颜色数并不会超过 3 .

下面分情况进行讨论：

1 : 当所有数相同时 ans = 1

2 : 当环为偶数长度时 ， 显然可以构造 1 , 2 交替的环 ans = 2

3 : 当环长为奇数时 ， 构造 1 , 2 交替的环会强制让断点处的数相等 ， 这时候如果环中有相邻相等的数对 ， 就可以作为断点 ， ans = 2 ， 否则 ans = 3 ， 先构造 1 2 交替 ， 让最后一个数作为 3 即可。

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define int long long
const int N = 2e6 + 10;
const int mod = 1e9 + 7;
typedef pair<int,int>PII;/*
3
1 2 3 4 5
1 2 1 2 1
*/
int n , t;
int a[N] , ans[N];signed main(){IOScin >> t;while(t --){cin >> n;bool tag = 0;int now = 0;map<int , int>mp;for(int i = 0 ; i < n ; i ++){cin >> a[i];mp[a[i]] = 1;}for(int i = 0 ; i < n ; i ++){if(a[i] == a[(i + 1) % n]) tag = 1 , now = (i + 1) % n;}if(mp.size() == 1){cout << "1\n";for(int i = 0 ; i < n ; i ++) ans[i] = 1;}else{if(n % 2 == 0){cout << "2\n";for(int i = 0 ; i < n ; i ++){if(i & 1) ans[i] = 1;else ans[i] = 2;}}else if(tag){cout << "2\n";for(int i = 1 , j = now ; i <= n ; i ++ , j = (j + 1) % n){if(i & 1) ans[j] = 1;else ans[j] = 2;}}else{cout << "3\n";for(int i = 0 ; i < n - 1 ; i ++){if(i & 1) ans[i] = 1;else ans[i] = 2;}ans[n - 1] = 3;}}for(int i = 0 ; i < n ; i ++) cout << ans[i] << " ";cout << "\n";}return 0;
}
//freopen("文件名.in","r",stdin);
//freopen("文件名.out","w",stdout);