[NOI Online #2 提高组] 涂色游戏

题意

有无限多个格子。

$p1$ 的倍数必须染红
$p2$ 的倍数必须染蓝
同时是两者倍数的位置可以任选红或蓝

忽略未染色格子后，如果出现 $k$ 个连续格子颜色相同，就算“无聊”。

题目要求判断：是否存在一种染色方案，使它不是无聊的。

思路

先看一个可以直接验证想法的小数据暴力：

cpp

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
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226#include <bits/stdc++.h>
using namespace std;

// brute.cpp：小数据暴力解。
// 对一个周期内的“必染色类型”建状态图，
// 判断是否存在无限染色方案，使得同色连续段长度始终小于 k。

int T;
long long p1, p2, k;

struct State {
    int pos;
    int last_color; // 0 红, 1 蓝, 2 表示还没有上一段颜色
    int run_len;
};

vector<int> type_list;
vector<State> states;
vector<vector<int> > graph, rev_graph, comps;
vector<int> vis, order, comp, has_cycle, reached;

long long gcd_value(long long a, long long b) {
    while (b != 0) {
        long long r = a % b;
        a = b;
        b = r;
    }
    return a;
}

long long lcm_value(long long a, long long b) {
    return a / gcd_value(a, b) * b;
}

int get_idx(const vector<vector<int> > &id, int pos, int last_color, int run_len) {
    return id[pos][last_color * (int)k + run_len];
}

void dfs1(int u) {
    vis[u] = 1;
    for (int v : graph[u]) {
        if (!vis[v]) {
            dfs1(v);
        }
    }
    order.push_back(u);
}

void dfs2(int u, int cid) {
    comp[u] = cid;
    comps[cid].push_back(u);
    for (int v : rev_graph[u]) {
        if (comp[v] == -1) {
            dfs2(v, cid);
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> T;

    while (T--) {
        cin >> p1 >> p2 >> k;

        if (k == 1) {
            cout << "No\n";
            continue;
        }

        type_list.clear();
        states.clear();
        graph.clear();
        rev_graph.clear();
        comps.clear();
        vis.clear();
        order.clear();
        comp.clear();
        has_cycle.clear();
        reached.clear();

        long long g = gcd_value(p1, p2);
        long long a = p1 / g;
        long long b = p2 / g;

        long long L = lcm_value(a, b);

        for (long long x = 0; x < L; x++) {
            bool red = (x % a == 0);
            bool blue = (x % b == 0);

            if (!red && !blue) {
                continue;
            }

            if (red && blue) {
                type_list.push_back(2); // 公共点，可以染红或染蓝
            } else if (red) {
                type_list.push_back(0);
            } else {
                type_list.push_back(1);
            }
        }

        int m = type_list.size();
        vector<vector<int> > id(m, vector<int>(3 * (int)k, -1));

        for (int pos = 0; pos < m; pos++) {
            for (int last_color = 0; last_color < 3; last_color++) {
                for (int run_len = 0; run_len < k; run_len++) {
                    int cur_id = states.size();
                    id[pos][last_color * (int)k + run_len] = cur_id;
                    states.push_back({pos, last_color, run_len});
                }
            }
        }

        graph.assign(states.size(), vector<int>());
        rev_graph.assign(states.size(), vector<int>());

        for (int i = 0; i < (int)states.size(); i++) {
            int pos = states[i].pos;
            int last_color = states[i].last_color;
            int run_len = states[i].run_len;

            vector<int> colors;
            if (type_list[pos] == 2) {
                colors.push_back(0);
                colors.push_back(1);
            } else {
                colors.push_back(type_list[pos]);
            }

            for (int color : colors) {
                int next_run = (last_color == color ? run_len + 1 : 1);
                if (next_run >= k) {
                    continue;
                }

                int next_pos = (pos + 1) % m;
                int to = get_idx(id, next_pos, color, next_run);
                graph[i].push_back(to);
                rev_graph[to].push_back(i);
            }
        }

        vis.assign(states.size(), 0);
        for (int i = 0; i < (int)states.size(); i++) {
            if (!vis[i]) {
                dfs1(i);
            }
        }

        comp.assign(states.size(), -1);
        int comp_cnt = 0;
        for (int i = (int)order.size() - 1; i >= 0; i--) {
            int u = order[i];
            if (comp[u] == -1) {
                comps.push_back(vector<int>());
                dfs2(u, comp_cnt);
                comp_cnt++;
            }
        }

        has_cycle.assign(comp_cnt, 0);
        for (int i = 0; i < comp_cnt; i++) {
            if ((int)comps[i].size() > 1) {
                has_cycle[i] = 1;
                continue;
            }
            int u = comps[i][0];
            for (int v : graph[u]) {
                if (v == u) {
                    has_cycle[i] = 1;
                }
            }
        }

        queue<int> q;
        reached.assign(states.size(), 0);

        vector<int> first_colors;
        if (type_list[0] == 2) {
            first_colors.push_back(0);
            first_colors.push_back(1);
        } else {
            first_colors.push_back(type_list[0]);
        }

        bool ok = false;
        for (int color : first_colors) {
            int start = get_idx(id, 1 % m, color, 1);
            if (!reached[start]) {
                reached[start] = 1;
                q.push(start);
            }
        }

        while (!q.empty()) {
            int u = q.front();
            q.pop();

            if (has_cycle[comp[u]]) {
                ok = true;
                break;
            }

            for (int v : graph[u]) {
                if (!reached[v]) {
                    reached[v] = 1;
                    q.push(v);
                }
            }
        }

        if (ok) {
            cout << "Yes\n";
        } else {
            cout << "No\n";
        }
    }

    return 0;
}

brute.cpp 会把一个周期内的必染色类型抽出来，然后在状态图上判断是否存在无限延续的合法染色方案。

这个做法适合小数据理解，但显然不可能应对 $10^6$ 组、 $10^9$ 量级的数据。

第一步：先除掉 gcd

设：

$g = gcd(p1, p2)$

把所有下标都除以 $g$ ，不会改变“染色顺序里相邻关系”的结构，所以只需要研究：

$a = p1 / g$
$b = p2 / g$

并设 $a <= b$ 。

这样就有：

$gcd(a, b) = 1$

第二步：谁更容易形成长连续段？

因为 $a <= b$ ，所以：

$a$ 的倍数更密
$b$ 的倍数更稀

直觉上，真正危险的是“很多个 $a$ 的倍数连续出现”，因为稀疏的那一色根本来不及把它们打断。

如果我们把所有公共点都染成较稀疏的那一色，那么蓝色连续段最多只会很短，问题就转化成：

在相邻两个 $b$ 的倍数之间，最多会出现多少个只能染成红色的点？

第三步：强制红段长度是多少？

看相邻两个 $b$ 的倍数：

$jb$
$(j+1)b$

在这两个点之间，所有被染色的内部点都只能是 $a$ 的倍数。
因为 $gcd(a,b)=1$ ，内部不会再出现公共点来帮你切开这段红色。

所以这中间会形成一整段连续红色。

这段长度的最大值是：

$ceil((b - 1) / a)$

用整数写法就是：

$(a + b - 2) / a$

第四步：判定条件

如果：

$k$ 大于这个最大强制同色段长度

那么就可以通过把公共点尽量染成较稀疏的颜色，成功避免出现长度为 $k$ 的同色连续段。

否则，无论怎么染，都会被某一段强制红色卡住。

所以答案就是：

若 $k > ceil((b - 1) / a)$ ，输出 Yes
否则输出 No

特殊情况

如果 $p1 = p2$ ，那么所有必须染色的位置其实都是公共点，可以随意交替染色。

这时只要 $k > 1$ ，就一定有解。

代码

cpp

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#include <bits/stdc++.h>
using namespace std;

long long T;
long long p1, p2, k;

long long gcd_value(long long a, long long b) {
    while (b != 0) {
        long long r = a % b;
        a = b;
        b = r;
    }
    return a;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> T;

    while (T--) {
        cin >> p1 >> p2 >> k;

        // 任意一种染色方案都至少会出现长度为 1 的同色段，
        // 所以 k=1 时一定无解。
        if (k == 1) {
            cout << "No\n";
            continue;
        }

        long long g = gcd_value(p1, p2);
        long long a = p1 / g;
        long long b = p2 / g;
        if (a > b) {
            swap(a, b);
        }

        // p1 == p2 时，所有必须染色的格子都是公共点，
        // 可以任意交替染色，因此只要 k>1 就一定有解。
        if (a == 1 && b == 1) {
            cout << "Yes\n";
            continue;
        }

        // 归一化后看成：
        // - a 的倍数偏“稠密”，把它当成红色
        // - b 的倍数偏“稀疏”，把它当成蓝色
        //
        // 在两次相邻的 b 倍数之间，里面所有必须染色的点都只能是 a 的倍数，
        // 它们会形成一整段连续红色。这个连续段长度的最大值是 ceil((b-1)/a)。
        long long max_run = (a + b - 2) / a;

        if (k > max_run) {
            cout << "Yes\n";
        } else {
            cout << "No\n";
        }
    }

    return 0;
}

复杂度

时间复杂度：每组 $O(log min(p1,p2))$
空间复杂度： $O(1)$

总结

这题的关键不是模拟染色，而是先做两个转化：

用 gcd 把问题归一化
把“是否无聊”转成“强制同色段的最大长度是多少”

一旦发现真正的瓶颈是相邻两个稀疏倍数之间的那段连续稠密颜色，题目就只剩一个简单公式判定。

测试点编号	$p_1$ , $p_2 \leq$	$k \leq$	$T \leq$
1 $\sim$ 3	$15$	$15$	$3375$
4 $\sim$ 6	$10^3$	$10^3$	$10^4$
7 $\sim$ 8	$10^3$	$10^3$	$10$
9 $\sim$ 10	$10^5$	$10^3$	$10^3$
11 $\sim$ 12	$10^5$	$5 \times 10^5$	$10$
13 $\sim$ 14	$10^5$	$5 \times 10^5$	$10^5$
15	$10^9$	$10^9$	$10$
16 $\sim$ 20	$10^9$	$10^9$	$10^6$