天才和疯子互相为邻

「CF1328D」Carousel

发表于 分类于

$Link$

$n$ 个点围成一圈，每个点都有类型。

给每个点染色，要求相邻的不同类型的点不能染同种颜色。

求最少颜色数和染色方案。

共有 $t$ 组数据。

$1\le t\le 10^4,3\le n\le 2\times 10^5,\sum n\le 2\times 10^5$。

这道题看起来很简单。

实际上它就是很简单，只不过由于断环为链，特殊处理有点复杂。

首先我们可以把同种类型的合并，首尾类型当做不同。

显然合并后，若剩下点有偶数个，直接黑白染色即可。

如果剩下奇数个点，分情况讨论。

  • 如果首尾是同种类型，将其合并就可以黑白染色了。

  • 如果有一个点是合并得来的，将其拆开（同种类型无要求），同样可以黑白染色。

  • 如果上述两种情况都不行，将最后一个点染成第三种颜色即可。

记得特判剩下一个点的情况。

时间复杂度 $O(n)$。

$code$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
#include <iostream>
#include <cstdlib>
#include <cstdio>
using namespace std;
inline int read()
{
    int f = 1, x = 0;
    char ch;

    do{
        ch = getchar();
        if (ch == '-')
            f = -1;
    }while(ch < '0' || ch > '9');
    do{
        x = x * 10 + ch - '0';
        ch = getchar();
    }while(ch >= '0' && ch <= '9');
    return f * x;
}
const int N = 2e5;

int tt;
int n;
int tot;
int a[N + 1];

int main()
{
    tt = read();

    while (tt--) {
        n = read();
        int tot = 0;
        for (int i = 1; i <= n; i++) {
            a[i] = read();
            if (a[i] != a[i - 1])
                tot++;
        }
        if (tot == 1) {
            printf("1\n");
            for (int i = 1; i <= n; i++)
                printf("1 ");
            printf("\n");
            continue;
        }
        if (!(tot & 1)) {
            printf("2\n1 ");
            int now = 1;
            for (int i = 2; i <= n; i++) {
                if (a[i] != a[i - 1]) {
                    if (now == 1)
                        now = 2;
                    else
                        now = 1;
                }
                printf("%d ", now);
            }
            printf("\n");
        } else {
            if (a[1] == a[n]) {
                printf("2\n1 ");
                int now = 1;
                for (int i = 2; i <= n; i++) {
                    if (a[i] != a[i - 1]) {
                        if (now == 1)
                            now = 2;
                        else
                            now = 1;
                    }
                    printf("%d ", now);
                }
                printf("\n");
                continue;
            }
            int w = 0;
            for (int i = 2; i <= n; i++) {
                if (a[i] == a[i - 1]) {
                    w = i;
                    break;
                }
            }
            if (w) {
                printf("2\n1 ");
                int now = 1;
                for (int i = 2; i <= n; i++) {
                    if (a[i] != a[i - 1]) {
                        if (now == 1)
                            now = 2;
                        else
                            now = 1;
                    }
                    if (i == w) {
                        if (now == 1)
                            now = 2;
                        else
                            now = 1;
                    }
                    printf("%d ", now);
                }
                printf("\n");
            } else {
                printf("3\n3 1 ");
                int now = 1;
                for (int i = 3; i <= n; i++) {
                    if (a[i] != a[i - 1]) {
                        if (now == 1)
                            now = 2;
                        else
                            now = 1;
                    }
                    printf("%d ", now);
                }
                printf("\n");
            }
        }
    }

    return 0;
}