条形座位的定义：在 $n$ 个座位中有 $2$ 个座位只有一个相邻的座位(为端点) 其余 $n - 2$ 个座位均有两个相邻的座位。($n = 1$ 时也算)
$\texttt{subtask 1-3}$
即为$n = 1$ 的情况，说明只有一行，因此一定是条形座位。那么我们只需要根据乘法原理将每组条形座位的方案相乘即可。
那么每组条形座位的方案如何计算呢？还是乘法原理！我们先回顾一下选座位的要求：任意考生不可能和来自同学校的考生座位相邻。
那么对于 $k$ 个学校的学生与一个长度为 $m$ 的条形座位。[$k \ge 2$] 第一个位置肯定有 $k$ 种情况；第二个座位的学生与第一个的来自不同的学校，所以只有 $k - 1$ 种情况；第三个座位的学生与第二个的来自不同的学校，但可以与第一个的来自相同的学校，所以仍然有 $k - 1$ 种情况。
综上所述，上面的一组条形座位的方案数为 $k \times (k - 1) ^ {n - 1}$ $[k \ge2]$。
根据这个，我们就可以得到 $40pts$ 的代码：
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
| #include <iostream>
#define MOD 998244353
using namespace std;
char a[1005][1005];
int an[1005];
int main()
{
int n,m,k,w = 0;long long ans = 1;
cin>>n>>m>>k;
for(int i = 1;i <= n;++i)
for(int j = 1;j <= m;++j) cin>>a[i][j];
for(int i = 1;i <= m;i++)
{
if(a[1][i] == 'O' && a[1][i - 1] != 'O') an[++w]++;
else if(a[1][i] == 'O') an[w]++;
}
for(int i = 1;i <= w;i++)
{
long long num = k;
for(int j = 2;j <= an[i];j++) num *= k - 1,num %= MOD;
ans *= num;ans %= MOD;
}
cout<<ans<<endl;
return 0;
}
|
$\texttt{subtask 4，5}$
我们将上面的思路由一维扩展到二维，发现我们只要进行一次搜索进行连通块数量的统计就行了。
需要多开一个 vis[1005][1005] 的数组，用于记录该点是否到达过。每一个连通块的大小都要单独计算，因此在搜索完毕后会得到若干个大小不同的条形座位，分别经过上述公式计算后相乘即可得出答案。$80pts$ 的代码如下：
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
| #include <iostream>
#define MOD 998244353
#define MAX 1005
#define ll long long
using namespace std;
char a[MAX][MAX];
ll an[MAX],ans = 1;
bool vis[MAX][MAX];
int dx[4] = {1,-1,0,0},dy[4] = {0,0,1,-1},n,m,k,w;
void search(int x,int y);
int main()
{
cin>>n>>m>>k;
for(int i = 1;i <= n;++i)
for(int j = 1;j <= m;++j) cin>>a[i][j];
for(int i = 1;i <= n;++i)
for(int j = 1;j <= m;++j)
if(!vis[i][j] && a[i][j] == 'O') w++,search(i,j);
for(int i = 1;i <= w;++i)
{
ll sum = k;
for(int j = 2;j <= an[i];++j) sum *= k - 1,sum %= MOD;
ans *= sum,ans %= MOD;
}
cout<<ans<<endl;
return 0;
}
void search(int x,int y)
{
vis[x][y] = 1;an[w]++;
for(int i = 0;i < 4;++i)
{
int xx = x + dx[i],yy = y + dy[i];
if(1 <= xx && 1 <= yy && xx <= n && y <= m && !vis[xx][yy] && a[xx][yy] == 'O') search(xx,yy);
}
}
|
$\texttt{subtask 6}$
可能出现不是条形座位的情况，因此我们需要判断每个连通块是否合法。若不合法，就要特判输出 $0$ 。那么我们如何去检查呢？
我们可以开一个队列：每次搜索计数一个连通块时，搜索到一个新的点时，把该点的坐标记录到队列中去。在搜索完毕后，进行统一的检查。不断取出队列中的元素，若不满足只有 $2$ 个相邻座位数为 $1$ 的点且其余座位的相邻座位数均为 $2$，就说明不满足条件，输出 $0$ 并停止程序。需要注意的是，只有一个座位的情况需要额外的特判。
综上所述，我们就得到了 $100pts$ 的代码：
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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
| #include <iostream>
#include <queue>
#define MOD 998244353
#define MAX 1005
#define ll long long
using namespace std;
struct node
{
int x,y;
};
queue <node> q;
char a[MAX][MAX];
ll an[MAX],ans = 1;
bool vis[MAX][MAX];
int dx[4] = {1,-1,0,0},dy[4] = {0,0,1,-1},num[MAX][MAX],n,m,k,w;
void search(int x,int y);
bool check();
int main()
{
cin>>n>>m>>k;
for(int i = 1;i <= n;++i)
for(int j = 1;j <= m;++j) cin>>a[i][j];
for(int i = 1;i <= n;++i)
for(int j = 1;j <= m;++j)
if(!vis[i][j] && a[i][j] == 'O')
{
w++;search(i,j);
if(!check())
{
cout<<0<<endl;
return 0;
}
}
for(int i = 1;i <= w;++i)
{
ll sum = k;
for(int j = 2;j <= an[i];++j) sum *= k - 1,sum %= MOD;
ans *= sum,ans %= MOD;
}
cout<<ans<<endl;
return 0;
}
void search(int x,int y)
{
q.push({x,y});
vis[x][y] = 1;an[w]++;
for(int i = 0;i < 4;++i)
{
int xx = x + dx[i],yy = y + dy[i];
if(1 <= xx && 1 <= yy && xx <= n && y <= m && !vis[xx][yy] && a[xx][yy] == 'O') search(xx,yy);
}
}
bool check()
{
int tt = 0;
if(q.size() == 1)
{
q.pop();
return 1;
}
while(!q.empty())
{
int t = 0;
node ch = q.front();q.pop();
if(a[ch.x][ch.y - 1] == 'O') t++;
if(a[ch.x][ch.y + 1] == 'O') t++;
if(a[ch.x - 1][ch.y] == 'O') t++;
if(a[ch.x + 1][ch.y] == 'O') t++;
if(t == 1) tt++;
if(t > 2) return 0;
}
if(tt == 2) return 1;
else return 0;
}
|
