CF323B Tournament-graph 题解

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

题意

题目链接

构造一张完全有向图(即任意两点之间都有一条单向边),使任意两有序点之间的距离不大于 $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;
    }

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

本文作者:water_tomato

评论

  1. jcomey
    3年前
    2020-11-05 21:45:21

    博主你的代码高亮工具用的是什么插件?

    • 博主
      jcomey
      3年前
      2020-11-28 19:03:45

      主题 Argon 自带的代码高亮

发送评论 编辑评论

|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇