codeforces1328D

文章目录[x]
  1. 1:题目链接
  2. 2:题意
  3. 3:思路
  4. 4:参考代码

csdn博客链接:https://nuoyanli.blog.csdn.net/article/details/105142596


题目链接

http://codeforces.com/contest/1328/problem/D

题意

给你一个数组,让你给他染色,如果,则不能染同一种颜色,若,你可以染成一种颜色,也可以染成不同颜色的。求染色用的颜色最少是多少及每个元素的颜色是什么(,输出任意满足条件的解即可)。

思路

  • 沒有相同类型只需要一种颜色即可
  • 如果第一个和最后一个种类相同并且颜色相同,中间也有不同,就两种颜色即可
  • 如果第一个和最后一个种类相同并且颜色相同,其他的全部不相同,就三种颜色
  • 如果第一个和最后一个种类不相同或者颜色吧相同,直接两种颜色

详细见代码。

参考代码

#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false), cin.tie(0)
#define endl '\n'
#define PB push_back
#define FI first
#define SE second
#define m_p(a, b) make_pair(a, b)
const double pi = acos(-1.0);
const double eps = 1e-9;
typedef long long LL;
const int N = 1e6 + 10;
const int M = 1e5 + 10;
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
const double f = 2.32349;
int a[N], colr[N], n;
void solve() {
  IOS;
  int t;
  cin >> t;
  while (t--) {
    cin >> n;
    for (int i = 1; i <= n; i++) {
      cin >> a[i];
      colr[i] = 0;
    }
    bool f = 0;
    for (int i = 1; i <= n; i++) {
      if (i == 1) {
        if (a[i] != a[n] || a[i] != a[i + 1]) {
          f = 1;
          break;
        }
      } else if (i == n) {
        if (a[i] != a[i - 1] || a[i] != a[1]) {
          f = 1;
          break;
        }
      } else {
        if (a[i] != a[i - 1] || a[i] != a[i + 1]) {
          f = 1;
          break;
        }
      }
    }
    if (!f) {//沒有相同类型只需要一种颜色即可
      cout << 1 << endl;
      for (int i = 1; i <= n; i++) {
        cout << "1 ";
      }
      cout << endl;
    } else {
      colr[1] = 1;
      int id = -1;
      for (int i = 2; i <= n; i++) {//找到最后一个不相同类型的位置为id,颜色初始化为1,不相同就为2
        if (a[i] == a[i - 1]) {
          colr[i] = colr[i - 1];
          id = i;
        } else {
          colr[i] = 3 - colr[i - 1];
        }
      }
      if (a[1] != a[n] && colr[1] == colr[n]) {//如果第一个和最后一个种类相同并且颜色相同
        if (id != -1) {//中间有不同,就两种颜色即可
          colr[id] = 3 - colr[id];
          for (int i = id + 1; i <= n; i++) {
            colr[i] = 3 - colr[i - 1];
          }
          cout << 2 << endl;
          for (int i = 1; i <= n; i++) {
            cout << colr[i] << " ";
          }
          cout << endl;
        } else {//其他全部相同,就三种颜色
          colr[n] = 3;
          cout << 3 << endl;
          for (int i = 1; i <= n; i++) {
            cout << colr[i] << " ";
          }
          cout << endl;
        }
      } else {//如果第一个和最后一个种类不相同或者颜色吧相同,直接两种颜色
        cout << 2 << endl;
        for (int i = 1; i <= n; i++) {
          cout << colr[i] << " ";
        }
        cout << endl;
      }
    }
  }
}
signed main() {
  solve();
  return 0;
}
/*
5
1 2 1 2 2
6
1 2 2 1 2 2
5
1 2 1 2 3
3
10 10 10

2
1 2 1 1 2
2
1 1 2 1 1 2
3
1 2 1 2 3
1
1 1 1
*/

 


点赞

发表评论

昵称和uid可以选填一个,填邮箱必填(留言回复后将会发邮件给你)
tips:输入uid可以快速获得你的昵称和头像