这道题乍看不难,但是构造过程中发现非常毒瘤,因为有一种情况极难构造。
题意
构造一张完全有向图(即任意两点之间都有一条单向边),使任意两有序点之间的距离不大于 $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;
}
将上述三段代码组合起来就是最终情况了,这里不再赘述。
博主你的代码高亮工具用的是什么插件?
主题 Argon 自带的代码高亮