P7886 「MCOI-06」Gerrymandering 题解

C_S_L · 2021-10-05 11:38:59 · 题解

考虑如何染色。

我们先把每种颜色依次一行一行染下去，如下图（以样例 1 的第 3 个数据为例）：

此时，2,5,8 三个数字是不联通的。

我们要在保证其他数字仍然联通的情况下使得这三个数字联通。

我们可以使用另一种染色方式：奇数行从前往后染，偶数行从后往前染。这样，若某个数字在同一行里，那么一定联通，若不在一行里，也一定联通，因为相邻两行中的这个数字联通。

如图：

注意特判不可行的情况，即 k\nmid nm 。

于是，我们以 \Theta(\sum nm) 的时间复杂度解决了此题。

代码：

#include<bits/stdc++.h>
using namespace std;
int T,n,m,k,a[10000][10000];
int main(){
    scanf("%d",&T);
    while(T--){
        scanf("%d%d%d",&n,&m,&k);
        if(n*m%k!=0){
            printf("NO\n");
            continue;
        }
        printf("YES\n");
        int cnt=k-1;
        for(int i=1;i<=n;++i){
            if(i%2==1){
                for(int j=1;j<=m;++j){
                    a[i][j]=(++cnt)/k;
                }
            }
            else{
                for(int j=m;j>=1;--j){
                    a[i][j]=(++cnt)/k;
                }
            }
        }
        for(int i=1;i<=n;++i){
            for(int j=1;j<=m;++j){
                printf("%d ",a[i][j]);
            }
            printf("\n");
        }
    }
    return 0;
}