P9899 sol

· · 题解

题意

消除星星，但是版面只有两行。求最少操作次数。

分析

考虑简单贪心。

容易发现，所有位于第二行的萝卜位置相当于已经固定，因此选定一种颜色的萝卜，将第二行所有该种颜色的萝卜消除。

之后处理一次萝卜下落事件，再将第一行剩余的刚才选定颜色的萝卜消除。

然后场上只剩下另一种颜色的萝卜了，直接消完就做完了。

正确性证明

考虑消除一个连通块的萝卜的贡献有两种：

一个 trival 的观察：若要产生第二种贡献，必须保证该连通块中至少一个萝卜在第二行。

所以从第二行选定颜色起消是正确的，并可能使得另一种颜色的萝卜下落造成原本不相连的连通块变为同一个连通块，从而减少消萝卜次数。

下面证明不产生第二种贡献的情况是不优的。

对于任意处于第一行的萝卜，下落后场上该种颜色萝卜的连通块一定是不增的。

因为由于只有两种颜色，其左右两边与其同种颜色的萝卜必然会与其一同下落（因为第二行对应位置必然同时在一次操作中被消除）。

于是证毕。

Code

深搜会爆空间。

代码使用广搜，选定先消除的颜色为 1。

#include<bits/stdc++.h>
using namespace std;
int n,a[5000001][4],ans,p; // p 代表当前颜色
int dx[5]={0,0,1,-1};
int dy[5]={1,-1,0,0};
struct F{
    int x,y;
};
queue<F> qu;
void bfs(int sx,int sy){
    F q;
    q.x=sx,q.y=sy;
    qu.push(q);
    while(!qu.empty()){
        q=qu.front();
        qu.pop();
        int x=q.x,y=q.y;
        for(int i=0;i<4;++i){
            int nx=x+dx[i],ny=y+dy[i];
            if(nx<1||nx>n||ny<1||ny>2||a[nx][ny]!=p)continue;
            a[nx][ny]=2;
            q.x=nx,q.y=ny;
            qu.push(q);
        }
    }
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;++i){
        cin>>a[i][1];
    }
    for(int i=1;i<=n;++i){
        cin>>a[i][2];
    }
    for(int i=1;i<=n;++i){
        if(a[i][2]==1){
            a[i][2]=2;
            p=1;
            bfs(i,2);
            ans++;
        }
    }
    for(int i=1;i<=n;++i){
        if(a[i][2]==2){
            swap(a[i][1],a[i][2]);
        }
    }
    for(int i=1;i<=n;++i){
        if(a[i][1]==1){
            a[i][1]=2;
            p=1;
            bfs(i,1);
            ans++;
        }
    }
    for(int i=1;i<=n;++i){
        if(a[i][2]==0){
            a[i][2]=2;
            p=0;
            bfs(i,2);
            ans++;
        }
    }
    cout<<ans<<"\n";
    return 0;
}