题解 CF1583F 【Defender of Childhood Dreams】

· · 题解

一篇来自蒟蒻的题解，不喜误喷，有误请私信。

考场上都没来得及看题，wtcl。

题目简述

有 n 个点，对于每两个点 i,j 满足 i< j，在 i 与 j 之间都会有一条连边。现在要对这 \frac{n\times (n-1)}{2} 条边进行染色。要求对于每一条长度大于等于 k 的路径，所有边的颜色种类至少要有两种。问至少要用几种颜色，并输出一种染色方案。

题目分析

是一道构造题，代码很好写，只要想清楚构造的方法。

首先，我们很容易发现（甚至可以不发现），只要保证每条长度为 k 的路径满足条件，那么长度大于 k 的所有路径都一定满足条件。证明随便想想，略。

我们先将 1,2,3,\dots ,k 这些点之间的所有边都染上颜色 1 ，因为这 k 个点之间的最长边的长度也没到 k 。

同理，将 k+1,k+2,k+3,\dots ,2k 之间的所有边都染上颜色 1 ，将 2k+1,2k+2,2k+3,\dots ,3k 之间的所有边都染上颜色 1 ，以此类推，最后到 k^2-k+1,k^2-k+2,k^2-k+3,\dots ,k^2 这些点之间的所有边都染上颜色 1，简单来说，就是现将 n 以 k 个元素为一组分组，组内全部边都染 1 。

接下来，考虑将这 n 个数按照 k^2 个元素为一组再进行分组，属于同一组内的两个点间还没有染色的边都染上颜色 2，仔细想想，这要就能保证这 k^2 个元素之间的所有长度等于 k 的路径上的颜色种类数至少有两个了。如果想不明白，可以看下蒟蒻证明：

用反证法：假设有一条长度为 k 的路径上的颜色种类只有 1 种。

定义：一个 k^2 个元素的分组叫做组，组内的每 k 个元素组成的分组叫块。

总上，假设不成立，故原名题得证。

证明了这点，接下来又是“以此类推”了。以 k^3 个元素划分组，组内还未染色的边全部染成 3；再以 k^4 个元素划分组，组内还未染色的边全部染成 4 ……

所以最后最少的颜色数量是 \lceil \log_k n\rceil。所有边的颜色上面都处理好了，直接输出即可。

Talk is cheap, show me the code!

Codeforces Status

int n=read(),k=read();
int ans=1,sum=k;
while(sum<n) ans++,sum*=k;//计算⌈logkN⌉
printf("%d\n",ans);
For(i,0,n-1){
    For(j,i+1,n-1){
        int x=i,y=j,d=0;
        while(x!=y) x/=k,y/=k,d++;//算每条边属于哪种跨度的
        printf("%d ",d);
    }
}