題目鏈接：點擊查看

題目大意：給出一個旋轉木馬外觀的排列，要求給每個木馬刷上一種顏色，使得相鄰的外觀不同的木馬顏色不同，問最少需要幾種顏色，并提供構造方案

題目分析：沒做出來的同學大概是沒讀懂題吧，一開始我也因為題意琢磨了半天，感覺像是離散化，莽了一發果然錯了，后來官方給出了提示是 “ 外觀相同的木馬顏色也可以不同 ” 后就豁然開朗了，其實就是構造一種方案使得相鄰的木馬顏色都不同，分類討論一下就好了：

n 個木馬的外觀相同(類比于最后一個樣例)：使用一種顏色，每個木馬染上顏色 1 即可

偶數個木馬：使用兩種顏色，1 2 1 2 1 2.....1 2染上顏色就好了，這樣第一個木馬的顏色是 1 ，最后一個木馬的顏色是 2 ，即使首尾相接仍然沒問題

奇數個木馬：

如果存在相鄰的兩個木馬外觀相同，則可以將這兩個木馬視為同一個木馬（合并），然后就可以按照偶數個木馬討論了

如果不滿足上面的情況，那么只能用三個顏色進行染色了，如果用兩種顏色染色的話，1 2 1 2 .... 1 2 1 最后會出現第一個木馬和最后一個木馬顏色相同的情況，所以我們只需要將最后一個木馬的顏色換為 3 就可以避免了

需要注意的是，在尋找是否存在相鄰木馬的外觀相同時，別忘了特判一下第一個木馬和最后一個木馬，因為在題目的意思里，給出的排列實際上是一個環狀的排列

代碼：
?

#include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> using namespace std;typedef long long LL;typedef unsigned long long ull;const int inf=0x3f3f3f3f;const int N=2e5+100;int a[N],n,pos;bool check_one() {for(int i=1;i<=n;i++)if(a[i]!=a[1])return false;return true; }bool check() {for(int i=1;i<n;i++)if(a[i]==a[i+1]){pos=i;return true;}if(a[1]==a[n]){pos=n;return true;}return false; }int main() { #ifndef ONLINE_JUDGE // freopen("input.txt","r",stdin); // freopen("output.txt","w",stdout); #endif // ios::sync_with_stdio(false);int w;cin>>w;while(w--){scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%d",a+i);if(check_one()){puts("1");for(int i=1;i<=n;i++)printf("1 ");puts("");}else{if(n&1){if(!check()){puts("3");for(int i=1;i<=n/2;i++)printf("1 2 ");puts("3");}else{puts("2");for(int i=1;i<=pos;i++)if(i&1)printf("1 ");elseprintf("2 ");for(int i=pos+1;i<=n;i++)if(i&1)printf("2 ");elseprintf("1 ");puts("");}}else{puts("2");for(int i=1;i<=n/2;i++)printf("1 2 ");puts("");}}}return 0; }

?

總結

以上是生活随笔為你收集整理的CodeForces - 1328D Carousel(构造+贪心)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。