CF1579G Minimal Coverage

发表于 更新于 分类于

题意

给定一张\(n\) 个点的有向图，若 \(i\)<\(j\)则 \(i\) 到\(j\)有边。现要求用最小的颜色数量给边染色，使任意一条长度为 \(k\) 的路径不同色。输出方案。

思路

将\(1,2,3...k\)的边全部设置为1，将\(k+1,k+2,k+3...2k\)的边设为1，一直至\(k^2\)，然后在每个\(k\)的块内的边设为2，在\(k^2\)的块内的边设为3，以此类推，则最终答案数为\(\lceil log_kn\rceil\)。

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
// Problem: Defender of Childhood Dreams
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/CF1583F
// Memory Limit: 500 MB
// Time Limit: 3000 ms
// Auther : MaxDYF
// 
// Powered by CP Editor (https://cpeditor.org)

//#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
const int inf = 1 << 30;
const long long llinf = 1ll << 60;
const double PI = acos(-1);
typedef pair<int, int> pii;
typedef long long ll;
int n, m, k, q;

void work()
{
	cin >> n >> k;
	cout << (int)(ceil(log(n) / log(k))) << endl;
	for (int i = 0; i < n; i++)
		for (int j = i + 1; j < n; j++)
		{
			int x = i, y = j;
			int col = 0;
			while (x != y)
			{
				x /= k;
				y /= k;
				col++;
			}
			cout << col << ' ';
		}
	cout << endl;
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	work();
}