CF323B Tournament-graph 题解

发布于 2020-09-23  817 次阅读


这道题乍看不难,但是构造过程中发现非常毒瘤,因为有一种情况极难构造。

题意

题目链接

构造一张完全有向图(即任意两点之间都有一条单向边),使任意两有序点之间的距离不大于 $2$。题意应该还算是比较容易理解的。

解析

$n$ 为奇数

题目已知 $n \ge 3$ 且 $n=4$ 时不可行。我们首先考虑 $n$ 是奇数的情况,我认为这种情况还是比较好想的,我们只要对于每一点,其接下来的奇数次序的点都可以直连,偶数次序的点都可以通过走到奇数次序的点,再走一条边到达(因此这些点让他们往回连)。对每一个点都以这种方式连边,我们会轻易发现这张图一定是可行的。

这种情况比较容易,不多做阐述,可以结合代码理解一下。

for(int i=1;i<n;i++){
    bool k=1;
    for(int j=i+1;j<=n;j++){
        if(k)
            a[i][j]=1;
        else a[j][i]=1;
        k^=1;
    }
}
for(int i=1;i<=n;i++){
    for(int j=1;j<=n;j++){
        printf("%d ",a[i][j]);
    }
    printf("\n");
}

$n$ 为偶数

我们首先考虑,如果前 $n-2$ 个点已经可以构造成一张竞赛图的话,我们只需要让前 $n-2$ 个点都连向第 $n-1$ 个点,让第 $n$ 个点连向前 $n-2$ 个点,再让第 $n-1$ 个点连向第 $n-2$ 个点即可,自己画一下图即可确认这一点。

然而我们刚开始并不知道偶数个点能不能构造出一张竞赛图,但我们可以在一次 WA 后得到这一结论。

我们已知 $4$ 个点不能构造出一张竞赛图,而如果题目要我们手构出 $8$ 个点的图就太毒瘤了,因此本着这种自信,我们决定想办法构造出一张 $6$ 个点的竞赛图——而这我认为是这道题最为困难的一点,且我自己也没找到什么好办法。在以奇数点的构造思路进行尝试失败后,我们考虑到如果让一个点连向多个点,这样别的点只要连向这个点就可以同时完成两步内到达多个点,然后我们凭借这个可能并不明朗的思路,再经过无数次尝试之后,终于构造出了一张完美(毒瘤)的竞赛图。

于是代码就很显然了。

a[1][2]=a[1][3]=a[1][4]=a[2][3]=a[2][4]=a[2][5]=
a[3][4]=a[3][6]=a[4][5]=a[4][6]=a[5][1]=a[5][3]=
a[6][1]=a[6][2]=1;
for(int i=n;i>6;i-=2){
    for(int j=1;j<=i-2;j++){
        a[j][i-1]=1;
        a[i][j]=1;
    }
    a[i-1][i]=1;
}
for(int i=1;i<=n;i++){
    for(int j=1;j<=n;j++){
        printf("%d ",a[i][j]);
    }
    printf("\n");
}

我们最后再补充上唯一一种无法构造的情况—— $n=4$。

if(n==4){
        printf("-1\n");
        return 0;
    }

将上述三段代码组合起来就是最终情况了,这里不再赘述。


月流华 岁遗沙 万古吴钩出玉匣