2020牛客暑期多校训练营(第六场)G-Grid Coloring
Grid Coloring
https://ac.nowcoder.com/acm/contest/5671/G
题目大意
给定一个n×n的正方形(如下图),有k种不同颜色,给每条边染色,使其满足以下条件,输出一种方案:
(1) 所有颜色的边数应该相同;
(2) 不存在一个单色环;
(3) 一行或一列至少存在两种颜色。
解题思路
最开始,我们要排除出掉没有解决方案的三种情况: (边数mod颜色数)
接着,我们按这样的方式给每条边标号:
- 对于一个1×1的环(图中橙色框),它的两条纵边序号相邻,颜色应该不同;
- 对于一个A×B,A<B的环(图中绿色框),它必定有相邻的横边,因此染的颜色不同;同理可以证明所有横边均不同色。
- 对于一个A×B,A>B的环(图中紫色框),如果其横边长为1,那么它必定有相邻的纵边;
如果其横边长>1,那么它必定有相邻的横边。
这样能得出什么结论?
可以发现,因为任意一个环以及任意横边均不同色,因此我们只需要分析纵边是否同色。
从我们标完号的图中,我们可以发现,两条相邻(纵向)边的序号差是2n+1。如图中第一列n+1,3n+2,5n+3......
因为(2n+1不能是一个循环节(k)的倍数)且,
所以我们可以得出。继续推导:
所以相邻的纵边不同色。
那么涂色的方案已经呼之欲出了:
我们按照上图中边的标号(也就是从上到下),每n个为一组,每组按顺序涂颜色1到k。(即序号为1的颜色1,序号为2的颜色2……序号为k的颜色k,序号为k+1的颜色1,序号为k+2的颜色2……)
AC代码
#include<bits/stdc++.h> using namespace std; int a[210][210],b[210][210]; int main() { int T,n,k,t,i,j; scanf("%d",&T); while(T--) { scanf("%d%d",&n,&k); if(n==1 || k==1 || (2*n*(n+1))%k) { puts("-1"); continue; } t=0; for(i=0;i<n;i++) { for(j=0;j<n;j++) t=t%k+1,a[i][j]=t; for(j=0;j<=n;j++) t=t%k+1,b[j][i]=t; } for(i=0;i<n;i++) t=t%k+1,a[n][i]=t; for(i=0;i<=n;i++) { for(j=0;j<n;j++) printf("%d ",a[i][j]); puts(""); } for(i=0;i<=n;i++) { for(j=0;j<n;j++) printf("%d ",b[i][j]); puts(""); } } return 0; }
2020牛客暑期多校训练营 文章被收录于专栏
只是题解,可参考,可学习,可点赞:)