Codeforces Round #630 (Div. 2)B: Composite Coloring

题目链接: http://codeforces.com/contest/1332/problem/B

在这里插入图片描述

思路

这题题目还是容易看明白(依靠翻译,emmmmm
就是最多只有11中颜色,让你进行涂色,对于两个数a,b 必须满足gcd(a,b) > 1 才能图相同的颜色,
想到了对于相同的因子应该归为一类,但是,还不够 !
来源: https://www.cnblogs.com/fisherss/p/12610766.html
在这里插入图片描述

代码

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
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1005;
typedef long long ll;
int ans[MAXN];
int dir[15]={ 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31};
int vis[35];
int main()
{
ios::sync_with_stdio(false);
int t;
while(cin >> t) {
while(t--) {
set<int> se;
int n;
cin >> n;
for(int i = 1; i <= n; i++) {
int k;
cin >> k;
int tmp = -1;
for(int j = 0; j < 11; j++) {
if(k % dir[j] == 0) {
tmp = dir[j];
if(vis[dir[j]] != 0) {
se.insert(dir[j]);
ans[i] = dir[j];
tmp = -1;
break;
}
}
}
if(tmp != -1) {
ans[i] = tmp;
se.insert(tmp);
}
}
unordered_map<int, int> mp;
int now = 1;
for(auto i : se) {
mp[i] = now++;
}
cout << se.size() << endl;
for(int i = 1; i <= n; i++) {
if(i != 1) cout << " ";
cout << mp[ans[i]];
}
cout << endl;
}
}
return 0;
}

本文标题:Codeforces Round #630 (Div. 2)B: Composite Coloring

文章作者:HKer_YM

发布时间:2020年04月01日 - 16:12:26

最后更新:2020年04月01日 - 16:23:22

原始链接:https://blog.dreams-wj.top/2020/04/01/Codeforces-Round-630-Div-2-B-Composite-Coloring/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。