个人建网站有什么好处,wordpress 免费字体,国家骨干高职院校建设网站,做网站能赚吗CF 1328 D. Carousel(环构造)
Problem - D - Codeforces
大意#xff1a;给出一个 n 个数组成的环 #xff0c; 要对环上的点染色 #xff0c; 要求任意一个相邻数不同的点对染色不同 #xff0c;求使用最少的颜色数 #xff0c; 并用颜色数排列构造一种染色方案。
思路…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 即可。
#includebits/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 pairint,intPII;/*
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;mapint , intmp;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);
