这是本蒟蒻的第一篇题解


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


题意

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


特判

我们共有4种特判情况

  1. n×m<kn\times m<kn×mmodk0n\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;
}