「消格子游戏」题解（基于代码分析）

题意简化

$n \times m$ 网格，好格子为 *，坏格子为 #。
操作：选择底层相邻两列，消掉最底部最多3个格子（L型），每列至少消1个。消后上方格子下落，顶部补坏格子。
目标：消掉所有好格子。
求最少操作次数。

$n,m \le 2000$。

核心观察

1. 问题转化

由于消掉的格子会被坏格子填充，实际上我们只关心每列最上方的好格子位置。

定义 $L[i]$ = 第 $i$ 列从底部开始，第一个好格子的高度（底部为1）。
如果没有好格子，$L[i] = 0$。

2. 操作分析

每次操作涉及相邻两列 $i$ 和 $i+1$：

• 可以消掉两列底部各1个（共2个）
• 或消掉一列2个 + 另一列1个（共3个，L型）

每次操作后，这些列的高度 $L[i]$ 和 $L[i+1]$ 会减少相应数量。

3. 目标

将所有 $L[i]$ 变为 0。

代码算法解析

1. 预处理 $L[i]$

for(int i=1;i<=M;i++)
    for(int j=1;j<=N;j++)
        if(c[j][i]=='*'){
            L[i] = N-j+1;  // 从底部算的高度
            S += L[i];      // 统计总好格子数
            break;
        }

• $L[i]$：第 $i$ 列第一个好格子的高度
• $S$：所有好格子的总数

2. 贪心处理

核心循环：

int mx=0, mn=0;
for(int i=1;i<=M+1;i++){
    swap(mn, mx);
    mn = L[i] - mn;
    mx = L[i] - mx;
    
    if(mx < 0){
        S += -mx;
        mx = mn = 0;
    }
    else if(mn < 0)
        mn = mx % 3;
    
    mx *= 2;
    mn = mn/2 + (mn&1)*2;
}

变量含义：

• mx：当前列消完后可能的最大剩余高度
• mn：当前列消完后可能的最小剩余高度

算法思想：
从左到右处理，尝试通过操作将相邻两列的 $L$ 值消减。
优先使用3格操作（效率最高），必要时使用2格操作。

3. 最后答案

cout << S/3;

因为：

• 最优情况下，每次操作平均消掉接近3个好格子
• 最差情况，每次只能消2个
• 答案下界是 $\lceil S/3 \rceil$，但代码直接整除，实际需要证明

关键结论

1. 下界

最少操作次数 $\ge \lceil \frac{S}{3} \rceil$，因为每次最多消3个。

2. 贪心最优性

从左到右处理，总能用接近最优的方式消掉格子。

3. 复杂度

$O(nm)$ 预处理 + $O(m)$ 贪心，可过 $n,m \le 2000$。

样例解释

输入：

3 2
#*
*#
##

网格：

• 第1列：位置(2,1)有好格子，$L[1]=2$（从底部算）
• 第2列：位置(1,2)有好格子，$L[2]=3$

好格子总数 $S=5$。

贪心处理：

• 可以一次操作消掉 (1,1)和(1,2)的3个格子
• 再消掉剩余的2个

最少操作：$\lceil 5/3 \rceil = 2$。

输出：2

算法要点

1. 只关心每列第一个好格子的高度
2. 从左到右贪心消减
3. 优先使用3格操作
4. 答案接近 $\lceil 总格子数/3 \rceil$

代码特点

• 简洁的贪心实现
• 巧妙的 mx、mn 维护
• 直接整除得到答案
• $O(nm)$ 复杂度