题解 P6582 【座位调查】

· · 题解

我又来啦QwQ!

一道很不错的联通块+推公式题。

STEP 1 解题大致思路

经过一段时间的思索，我们可以轻易地将这道题分成几个子任务：

  1. 输入整张地图；

  2. 遍历整张地图：

    • 找到座椅；

    • 进入 dfs 遍历，找到这个联通块的所有座椅，并且记录有几个座椅周围只有一个座椅以及该联通块的座椅个数，注意遍历完的座椅要标记；

    • 如果该联通块周围有一个座椅的座椅不是两个且联通块个数不为 1，说明该图不合法，输出0并结束程序；

    • 否则根据联通块个数套入公式计算即可。

  3. 将计算完的答案输出。

STEP 2 推导公式

当联通块合法的时候，我们可以对于这个联通块套用计算公式。

既然每一个合法的联通块都是“条形”座位，那么只要联通块合法，我们就完全可以将它掰成一个直的条形座位。

对于每一个条形的座位联通块，第一个座位一定可以放 k 个学校的学生，也就是有 k 种可能，而后面的座位因为前面的一个座位已经选过了一个学校，为了符合题意，只能放 k-1 个学校的学生，所以若设联通块的座位个数为 w，则通项公式为：

k\times(k-1)^{w-1}

然后我们把所有的联通块的可能性个数乘起来就好啦！（不要忘记驱魔哦QwQ）

STEP 3 AC\ code 及注释

#include<bits/stdc++.h>
using namespace std;
#define inf 998244353//模数
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};//每一项对应一个方向
int n,m,k,tot;//如题，如下
long long sum,ans=1;//如题，如下
char ma[1001][1001];//储存地图
long long ksm(long long s,long long mi){//快速幂加速
    long long ans=1,cnt=s;
    while (mi){
        if (mi&1) ans=ans*cnt%inf;
        cnt=cnt*cnt%inf;
        mi>>=1;
    }
    return ans;
} 
int find(int x,int y){//寻找周围的座椅数
    int js=0;
    for (int i=0;i<4;i++){
        int xx=x+dx[i],yy=y+dy[i];
        if (xx>=1&&xx<=n&&yy>=1&&yy<=m&&ma[xx][yy]!='X') js++;
    }
    return js;
}
void dfs(int x,int y){//简单dfs搜索
    if (find(x,y)==1) tot++;//记录周围只有一个座椅的座椅数
    ma[x][y]='W';//换一个标记以方便记录每个座椅周围的座椅数
    sum++;//座椅数++
    for (int i=0;i<4;i++){//四个方向遍历
        int xx=x+dx[i],yy=y+dy[i];
        if (xx>=1&&xx<=n&&yy>=1&&yy<=m&&ma[xx][yy]=='O'){
            dfs(xx,yy);
        }
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);//加速神器
    cin>>n>>m>>k;
    for (int i=1;i<=n;i++){
        for (int j=1;j<=m;j++){
            cin>>ma[i][j];
        }
    }//输入地图
    for (int i=1;i<=n;i++){
        for (int j=1;j<=m;j++){//遍历地图
            if (ma[i][j]=='O'){
                sum=tot=0;//初始化，sum记录座椅个数，tot记录周围只有一个座椅的座椅个数
                dfs(i,j);//dfs搜索
                if (tot<2&&sum>1){//不合法
                    cout<<0<<endl;
                    return 0;
                }
                ans=ans*k%inf*ksm(k-1,sum-1)%inf;//套公式
            }
        }
    }
    cout<<ans<<endl;//输出
    return 0;//完美撒花
}

STEP 4 完结撒花！

如果还有什么不懂的地方欢迎 \text{评论区/私信} 问我哦，我会第一时间回复哒！

如果都懂了的话，就点个赞纪念一下你的成长8QWQ!