简要题意
一张有 $n$ 个点的图, 对于所有的 $i < j$ , 都有一条 $i$ 到 $j$ 的有向边. 要求给这 $\frac{n(n-1)}{2}$ 条边染色, 使得任意长度大于 $k$ 的路径都有至少两种颜色.
$n,k \leqslant 10^3$ .
题解
首先可以转化题意, 变成对于任意长度为 $k$ 的路径至少有两种颜色.
我们先将 $1,2,3,\dots ,k$ 这些点之间的边都染成颜色 $1$ , 这些边的长度都小于 $k$ .
同理, 将 $k+1,k+2,\dots ,2\times k$ 之间的边, $2\times k+1,2\times k+2,\dots ,3\times k$ 最后到 $k^2-k+1,k^2-k+2,\dots ,k^2$ 之间的边都染成颜色 $1$ , 也就是将 $n$ 个元素$k$ 个一组分组.
接下来将 $n$ 个数按 $k^2$ 个一组分组, 同组内没有然颜色的边染成颜色 $2$ , 这样就能保证这 $k^2$ 个点之间所有长度为 $k$ 的路径上的颜色种类至少有两个.
简单证明:
反证法, 定义 $k^2$ 个一组的为组, $k$ 个一组的为块.
- 如果都是颜色 $1$ , 那么一定在同一个块内, 长度不足 $k$ .
- 如果都是颜色 $2$ , 那么贪心的走, 从第一个块的任意一个点出发, 走颜色 $2$ 的边, 一定会走到第二个块, 最后走到第 $k$ 个块, 路径长度为 $k-1$ .
综上, 原命题成立.
接下来以此类推, $k^3$ 个元素一组染成颜色 $3$ , $k^4$ 个元素一组染成颜色 $4$ , $\dots$
所以最终最少使用 $\lceil \log_{k}{n} \rceil$ 种颜色.
代码
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
|
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
typedef long long ll;
typedef pair <int,int> pii;
#define DEBUG(x) cout << #x << " = " << x << endl
template <typename T>
inline bool read(T &x) {
int f = 1,c = getchar();x = 0;
while (!isdigit(c)) {if (c == 45)f = -1;c = getchar();}
while (isdigit(c))x = (x<<3)+(x<<1)+(c^48),c = getchar();
return x *= f,true;
}
template <typename T,typename... Args>
inline bool read(T &x,Args &...args) {
return read(x) && read(args...);
}
namespace run {
int n,k,ans,sum;
inline int main() {
read(n,k);
ans = 1;sum = k;
while (sum < n)ans++,sum *= k;
printf("%d\n",ans);
for (register int i = 0;i < n;++i)
for (register int j = i+1;j < n;++j) {
int x = i,y = j,d = 0;
while (x ^ y)x /= k,y /= k,++d;
printf("%d ",d);
}
cerr<<1.0*clock()/CLOCKS_PER_SEC<<endl;
return 0;
}
}
#define demonlover
int main() {
#ifdef demonlover
freopen("CF1583F.in","r",stdin);
freopen("CF1583F.out","w",stdout);
#endif
return run :: main();
}
|