P8422 题解

yanhao40340 · 2023-05-03 18:24:33 · 题解

第一道紫题题解！虽然是道模拟。

题意

大体题意就是一个消消乐的游戏过程，多看几遍题面即可。

分析

消消乐的游戏步骤：交换棋子 \to 判断是否可消 \to 统计组合奖分 \to 特殊效果 \to 统计消除奖分 \to 消除棋子 \to 重力下落 \to 判断是否可消 \to ...。

其中有效操作每满 5 次就要进行一次统计牌型奖分。

最后要统计终局奖分。

因为这是一道模拟题，且 1 \le n,m \le 50，所以只要不是死循环的代码就基本不会 \texttt{TLE}。接下来我们就一个一个步骤实现。

交换棋子

交换棋子是这些步骤里最简单的一个。

首先需要判断这两个交换的位置是否相邻。

其次判断这两个位置是否存在棋子。

最后判断交换后盘面能否实现消除。

时间复杂度 \Theta\left(nm(n+m)\right)。代码如下：

bool change(int xa,int ya,int xb,int yb){ //交换棋子，返回值表示是否交换成功
    if (abs(xa-xb)+abs(ya-yb)==1) //判断是否相邻
        if (a[xa][ya].first&&a[xb][yb].first){ //判断位置是否有棋子
            swap(a[xa][ya],a[xb][yb]);
            bool res=check(1); //判断能否消除
            if (!res){swap(a[xa][ya],a[xb][yb]);return false;} //不能消除则重置盘面
            return true;
        }
    return false;
}

判断是否可消

主要思路是对于每一个棋子向右和向下扫描，判断是否有 3 个及 3 个以上的同色棋子连成一线。函数将可以消除的棋子坐标加入 dels 中。

时间复杂度 \Theta\left(nm(n+m)\right)。代码如下：

bool check(bool flg){ //判断是否可消，flg 参数表示是否是第一轮消除，返回值表示是否可以消除
    dels.clear();
    bool can=false; //记录是否消除
    for (int i=1;i<=n;++i)
        for (int j=1;j<=m;++j){
            if (a[i][j].first){ //如果有棋子
                int tot=0,tot2=0;
                for (int k=0;i+k<=n;++k){ //向下扫描
                    if (a[i+k][j].first==a[i][j].first) ++tot;
                    else break;
                }
                if (tot>=3){ //如果有 3 个及以上的同色棋子
                    can=true;
                    if (flg) col[now%5].insert(a[i][j].first); //如果是第一轮消除，那么将消除的颜色加入到这一次的主颜色中
                    for (int k=0;k<tot;++k)
                        dels.insert(make_pair(i+k,j)); //把要消除的棋子加入 dels
                }
                for (int k=0;j+k<=m;++k){ //向右扫描
                    if (a[i][j+k].first==a[i][j].first) ++tot2;
                    else break;
                }
                if (tot2>=3){
                    can=true;
                    if (flg) col[now%5].insert(a[i][j].first);
                    for (int k=0;k<tot2;++k)
                        dels.insert(make_pair(i,j+k));
                }
            }
        }
    return can;
}

统计组合奖分

把所有要消除的点打上标记（代码中的 mp 数组），然后求出所有四连通块即可。

依次对还没有访问过的点进行宽搜，宽搜时访问的点打上已访问标记（代码中的 vis 数组）。

时间复杂度 \Theta\left(nm\right)。代码如下：

bitset<maxn> vis[maxn],mp[maxn];
int dir[][2]={{0,1},{0,-1},{1,0},{-1,0}};
void calcsquares(){ //统计组合奖分
    queue<pii> q;delsquares.clear();
    for (int i=1;i<=n;++i) vis[i].reset(),mp[i].reset();
    for (pii it:dels) mp[it.first].set(it.second); //标记所有要消除的点
    for (pii it:dels){
        if (!vis[it.first][it.second]){ //如果该点还没有访问过，即不在已经搜索的任一四连通块内
            q.push(it);int tot=0; //tot 记录连通块大小
            vis[it.first].set(it.second);
            while (!q.empty()){ //宽搜板子
                pii fr=q.front();q.pop();++tot;
                int x=fr.first,y=fr.second;
                for (int i=0;i<4;++i){
                    int dx=dir[i][0]+x,dy=dir[i][1]+y;
                    if (1<=dx&&dx<=n&&1<=dy&&dy<=m){
                        if (mp[dx].test(dy)&&a[dx][dy].first==a[x][y].first&&!vis[dx].test(dy)){
                            vis[dx].set(dy);
                            q.push(make_pair(dx,dy));
                        }
                    } 
                }
            }
            delsquares.push_back(tot); //记录该四连通块的大小
        }
    }
    for (int it:delsquares)
        ans+=(it-3)*(it-3)*50; //计算分数
    return;
}

特殊效果

对于每一个功能都按题意模拟实现即可。把所有功能加入到队列中，如果触发了新的功能则将新功能也加入到队列中。

也是使用宽搜（也许叫手写栈的深搜？）实现。

时间复杂度约为 \Theta\left(n^2m\right)。代码如下：

void feature(){ //特殊效果
    queue<tuple<int,int,int> > q;
    for (pii it:dels)
        if (a[it.first][it.second].second){ //如果有特殊效果
            q.push(make_tuple(it.first,it.second,a[it.first][it.second].second)); //加入队列
            a[it.first][it.second].second=0; //取消效果，否则会被多次加入
        }
    while (!q.empty()){ //宽搜板子
        auto fr=q.front();q.pop();
        int x=get<0>(fr),y=get<1>(fr),op=get<2>(fr); //x 和 y 表示坐标，op 表示功能的类型
        switch (op){
            case 1: //消一行
                for (int i=1;i<=m;++i)
                    if (a[x][i].first){
                        if (a[x][i].second)
                            q.push(make_tuple(x,i,a[x][i].second)),a[x][i].second=0;
                        dels.insert(make_pair(x,i));
                    }
                break;
            case 2: //消一列
                for (int i=1;i<=n;++i)
                    if (a[i][y].first){
                        if (a[i][y].second)
                            q.push(make_tuple(i,y,a[i][y].second)),a[i][y].second=0;
                        dels.insert(make_pair(i,y));
                    }
                break;
            case 3: //消一行 + 一列
                for (int i=1;i<=m;++i)
                    if (a[x][i].first){
                        if (a[x][i].second)
                            q.push(make_tuple(x,i,a[x][i].second)),a[x][i].second=0;
                        dels.insert(make_pair(x,i));
                    }
                for (int i=1;i<=n;++i)
                    if (a[i][y].first){
                        if (a[i][y].second)
                            q.push(make_tuple(i,y,a[i][y].second)),a[i][y].second=0;
                        dels.insert(make_pair(i,y));
                    }
                break;
            case 4: //消 3*3 区域
                for (int i=max(1ll,x-1);i<=min(n,x+1);++i)
                    for (int j=max(1ll,y-1);j<=min(m,y+1);++j)
                        if (a[i][j].first){
                            if (a[i][j].second)
                                q.push(make_tuple(i,j,a[i][j].second)),a[i][j].second=0;
                            dels.insert(make_pair(i,j));
                        }
                break;
            case 5: //消 5*5 区域
                for (int i=max(1ll,x-2);i<=min(n,x+2);++i)
                    for (int j=max(1ll,y-2);j<=min(m,y+2);++j)
                        if (a[i][j].first){
                            if (a[i][j].second)
                                q.push(make_tuple(i,j,a[i][j].second)),a[i][j].second=0;
                            dels.insert(make_pair(i,j));
                        }
                break;
            case 6: //消同色棋子
                for (int i=1;i<=n;++i)
                    for (int j=1;j<=m;++j)
                        if (a[i][j].first==a[x][y].first){
                            if (a[i][j].second)
                                q.push(make_tuple(i,j,a[i][j].second)),a[i][j].second=0;
                            dels.insert(make_pair(i,j));
                        }
                break;
            default:
                break;
        }
    }
}

统计消除奖分

按题中所给公式模拟即可，没什么好说的。

时间复杂度 \Theta\left(nm\right)。代码如下：

void calcchesses(int turns){ //统计消除奖分
    for (pii it:dels){
        int x=it.first,y=it.second;
        ans+=a[x][y].first*turns; //公式
    }
    return;
}

消除棋子

现在所有要消除的棋子都在 dels 里面，所以直接遍历 dels 逐个进行消除即可。

时间复杂度 \Theta\left(nm\right)。代码如下：

void remove(){ //消除棋子
    for (pii it:dels){
        int x=it.first,y=it.second;
        a[x][y].first=0;
    }
    return;
}

重力下落

对于每一列分开考虑，如果这一个位置有棋子，那么它下落的格数就等于这一列它下面被消除的棋子个数。

所以对每一列做后缀和，统计被消除棋子的个数，即可从 \Theta\left(n^2m\right) 优化到 \Theta\left(nm\right)。

时间复杂度 \Theta\left(nm\right)。代码如下：

int zeros[maxn]; //后缀和，表示被消除棋子的个数
void down(){ //重力下落
    for (int i=1;i<=m;++i){
        for (int j=n;j;--j){ //后缀和
            if (!a[j][i].first) zeros[j]=zeros[j+1]+1;
            else zeros[j]=zeros[j+1];
        }
        for (int j=n;j;--j)
            if (a[j][i].first) //如果有棋子
                if (j+zeros[j]<=n){
                    pii tmp=a[j][i];
                    a[j][i]=make_pair(0,0);
                    a[j+zeros[j]][i]=tmp; //交换
                }
    }
    return;
}

枚举主颜色

显然，对于每一次操作，最少有一个主颜色，最多有两个主颜色。

那么我们就对有两个主颜色的操作进行枚举，因为最多只有 5 次操作需要枚举，所以枚举的次数不超过 2^5=32 次。

枚举可以使用 \texttt{dfs}，也可以直接用二进制数枚举。

时间复杂度 \Theta\left(2^{len}k\le 32k\right)，其中 len 表示有 2 个主颜色的操作总数。代码如下：

int dfscolors(){ //枚举主颜色，返回值表示这五次操作的最大牌型奖分
    vector<int> dbcols; //有 2 个主颜色的操作编号
    for (int i=0;i<5;++i)
        if (col[i].size()==2) dbcols.push_back(i);
    int len=dbcols.size(),range=1<<len,num=0;
    vector<int> nowcol;
    int maxx=0;
    for (int i=0;i<range;++i){ //二进制数枚举
        num=0;
        for (int j=0;(1<<j)<=i;++j)
            if (i&(1<<j)) num|=(1<<dbcols[j]); //计算当前状态对应的数
        nowcol.clear();
        for (int j=0,k=1;j<5;++j,k<<=1){ //依次取主颜色
            if (num&k) nowcol.push_back(*col[j].rbegin());
            else nowcol.push_back(*col[j].begin());
        }
        int res=calccolors(nowcol); //计算
        maxx=max(res,maxx);
    }
    return maxx;
}

统计当前牌型奖分

主要思想就是两次使用映射计算出每种牌型有几种。

cnt 表示一个数出现的次数；

ccnt 表示一种牌型（1 个相同颜色，1 对相同颜色等）出现的次数。

时间复杂度 \Theta\left(k\right)，不过可以通过一连串判断实现到 \Theta\left(1\right)。代码如下：

int calccolors(vector<int> cols){ //统计当前牌型奖分，返回值表示当前牌型得分
    int cnt[maxk]={0},ccnt[6]={0};
    for (int it:cols) ++cnt[it];
    for (int i=1;i<=kinds;++i) ++ccnt[cnt[i]];
    if (ccnt[1]==5){ //高牌：5 种不同颜色
        int maxx=*max_element(cols.begin(),cols.end()); //取最大颜色编号
        return 50+maxx;
    }
    if (ccnt[1]==3&&ccnt[2]==1){ //一对：1 对+ 3 种不同颜色
        for (int i=kinds;i;--i)
            if (cnt[i]==2) return 100+(i<<1);
    } 
    if (ccnt[1]==1&&ccnt[2]==2){ //两对：2 对+ 1 种不同颜色
        int res=200,flg=1;
        for (int i=kinds;i;--i)
            if (cnt[i]==2) res+=(i<<flg),flg=0;
        return res;
    }
    if (ccnt[3]==1&&ccnt[1]==2){ //三条：3 种相同颜色+ 2 种不同颜色
        for (int i=kinds;i;--i)
            if (cnt[i]==3) return 300+i*3;
    }
    if (ccnt[3]==1&&ccnt[2]==1){ //葫芦：3 个相同颜色 + 另外 2 个相同颜色
        int res=500;
        for (int i=kinds;i;--i)
            if (cnt[i]==3) res+=i*3;
            else if (cnt[i]==2) res+=i;
        return res;
    }
    if (ccnt[4]==1&&ccnt[1]==1){ //四条：4 个相同颜色 + 1 个其他颜色
        for (int i=kinds;i;--i)
            if (cnt[i]==4) return 750+i*5;
    }
    if (ccnt[5]==1){ //五条：5 个颜色全部相同
        for (int i=kinds;i;--i)
            if (cnt[i]==5) return 1000+i*10;
    }
    return 0;
}

主函数和剩下的几种得分

这些得分比较简单，我就都放在了主函数里计算。

bool alluse=true; //标记操作是否全部有效
while (q--){
    int xa=read(),ya=read(),xb=read(),yb=read();
    bool flg=change(xa,ya,xb,yb);
    if (flg){ //如果操作有效
        calcsquares();
        feature();
        calcchesses(1);
        remove();down();
        int turns=1;
        while (check(0)){
            ++turns;
            calcsquares();
            feature();
            calcchesses(turns);
            remove();down();
        }
        ans+=(turns-1)*(turns-1)*80; //统计连锁奖分
        ++now; //计入一次有效操作
        }
    else alluse=false; //否则无法得到全部操作有效的终局得分
    if (now==5){ //如果有效操作满 5 个
        ans+=dfscolors();
        for (int i=0;i<5;++i) col[i].clear();
        now=0;
    }
}
//以下是终局奖分
if (alluse) ans+=1000;
if (delall()) ans+=10000; //delall 函数表示是否全部删除，该函数实现简单，就不放代码了

后记

AC 记录。

这道大模拟属于比较好做的，没有什么坑点，主要在于码量。

另外熟练运用 STL 在一些不卡时间的模拟题中可以减少很多不必要的错误和码量。（仅个人观点）

完结散花！！！