洛谷P7886 「MCOI-06」Gerrymandering 题解

这是本蒟蒻的第一篇题解

读题点这里：P7886 「MCOI-06」Gerrymandering

题意

题目要求将一个 n×mn\times m 表格染色，使得每一个颜色形成恰好一个连通块，并且每一个连通块大小为 kk

特判

我们共有4种特判情况

  1. 当 n×m<kn\times m<k 或 n×mmod  k≠0n\times m\mod k\neq 0 时，没有答案，输出
    NO

    1
    if(n*m<k||n*m%k!=0) cout<<"NO"<<endl;

  2. 当 k=1k=1 时，存在答案，且每一格的数字都不一样 (Subtask 1)

    1
    2
    3
    4
    5
    6
    7
    8
    9
    cout<<"YES"<<endl;
    int cnt=1;
    for(int i=1;i<=m;i++){
    	for(int j=1;j<=n;j++){
    			cout<<cnt<<" ";
    			cnt++;
    	}
    	cout<<endl;
    }

  3. 当 n=1n=1 时，存在答案，且答案只有一行。直接输出 n×m÷kn\times m\div k 个数即可 (Subtask 2) (这一步骤与普通情况可以共用一个代码，故可以省略，但在这里为了便于理解，还是列出)

    1
    2
    3
    4
    cout<<"YES"<<endl;
    for(int i=1;i<=m/k;i++)
    	for(int j=1;j<=k;j++) cout<<i<<" ";
    cout<<endl;

  4. 当 n×m=kn\times m=k 时，存在答案，且每一格都是1

    1
    2
    3
    4
    5
    cout<<"YES"<<endl;
    for(int i=1;i<=m;i++){
    	for(int j=1;j<=n;j++) cout<<1<<" ";
    	cout<<endl;
    }

普通情况

先将所有的数字存入一个一维数组，再蛇形展开即可

如测试样例中的 6 6 4 就可以先存入一维数组，变成 1 1 1 1 2 2 3 3 3 3 2 2 4 4 4 4 5 5 6 6 6 6 5 5 7 7 7 7 8 8 9 9 9 9 8 8

再蛇形展开为

1
2
3
4
5
6
1 1 1 1 2 2 
3 3 3 3 2 2 
4 4 4 4 5 5 
6 6 6 6 5 5 
7 7 7 7 8 8 
9 9 9 9 8 8

普通情况的代码如下：

1
2
3
4
5
6
7
cout<<"YES"<<endl;
for(int i=1;i<=n*m;i++) a[i]=(i-1)/k+1;
for(int i=1;i<=n;i++){
    if(i%2==1) for(int j=1;j<=m;j++) cout<<a[(i-1)*m+j]<<' ';
    else for(int j=m;j;j--) cout<<a[(i-1)*m+j]<<' ';
	cout<<endl;
}

完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include<bits/stdc++.h>
using namespace std;
#define N 1000005

int T,n,m,k,a[N];
bool u[N]={0};

int main(){
	cin>>T;
	while(T--){
		cin>>n>>m>>k;
		if(n*m<k||n*m%k!=0) cout<<"NO"<<endl;//不成立的情况
		else if(n*m==k){//特判n*m=k
			cout<<"YES"<<endl;
			for(int i=1;i<=m;i++){
				for(int j=1;j<=n;j++) cout<<1<<" ";
				cout<<endl;
			}
		}else if(k==1){//特判k=1
			cout<<"YES"<<endl;
			int cnt=1;
			for(int i=1;i<=m;i++){
				for(int j=1;j<=n;j++){
					cout<<cnt<<" ";
					cnt++;
				}
				cout<<endl;
			}
		}else{//普通情况
			cout<<"YES"<<endl;
            //生成一维数组
			for(int i=1;i<=n*m;i++) a[i]=(i-1)/k+1;
            //蛇形输出
            for(int i=1;i<=n;i++){
                if(i%2==1)
                    for(int j=1;j<=m;j++) cout<<a[(i-1)*m+j]<<' ';
                else for(int j=m;j;j--) cout<<a[(i-1)*m+j]<<' ';
                cout<<endl;
            }
		}
	}
	system("pause");
	return 0;
}