「俄罗斯方块覆盖」题解

问题分析

我们需要在 $n \times m$ 的棋盘上放置特定类型的俄罗斯方块，避开特殊方格，最大化放置的方块数量。根据俄罗斯方块类型的不同，需要采用完全不同的算法。

核心思路

根据三种不同的俄罗斯方块类型，分别设计算法：

类型 A：骨牌覆盖（二分图匹配）

类型 B：大数计算（公式推导）

类型 C：状态压缩 DP（复杂形状覆盖）

算法详解

1. 类型 A 解法（骨牌覆盖）

namespace solveA {
// 使用网络流（Dinic算法）求解二分图最大匹配
int dinic() {
    int res = 0;
    while (bfs())
        res += dfs(s, inf);
    return res;
}

void work() {
    // 构建二分图：棋盘黑白染色
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            if (!vis[i][j]) {
                if ((i + j) & 1) {  // 黑格
                    // 与相邻白格连边
                    if (i < n && !vis[i + 1][j])
                        addedge(getid(i, j), getid(i + 1, j), 1);
                    if (j < m && !vis[i][j + 1])
                        addedge(getid(i, j), getid(i, j + 1), 1);
                } else {  // 白格
                    // 反向边
                    if (i < n && !vis[i + 1][j])
                        addedge(getid(i + 1, j), getid(i, j), 1);
                    // ...
                }
            }
    
    // 源点连黑格，白格连汇点
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            if ((i + j) & 1)
                addedge(s, getid(i, j), 1);
            else
                addedge(getid(i, j), t, 1);
    
    cout << dinic();
}
}

算法原理：

• 将棋盘按 $(i+j) \bmod 2$ 黑白染色
• 黑格作为左部，白格作为右部
• 相邻非特殊格子间建立边
• 最大匹配数即为最多骨牌数

2. 类型 B 解法（大数计算）

namespace solveB {
void work() {
    // n, m 是2的幂，K=1
    // 答案 = floor(n/2) * floor(m/2) - 1
    
    // 使用FFT进行大数乘法计算 n*m
    // 然后除以4再减1
    HPN ans;
    // ... 大数计算过程
    ans = ans - 1;
    ans /= 3;  // 实际应该是除以4，这里代码可能有误
    ans.print();
}
}

算法原理：

• $2 \times 2$ 方块覆盖，每个方块占4格
• 总方块数 = $\lfloor \frac{n}{2} \rfloor \times \lfloor \frac{m}{2} \rfloor$
• 有一个特殊方格破坏一个方块，所以减1

3. 类型 C 解法（状态压缩DP）

namespace solveC {
void work() {
    // 使用滚动数组状态压缩DP
    memset(f, -0x3f, sizeof(f));
    f[0][(1 << m) - 1][(1 << m) - 1] = 0;
    
    for (int i = 0; i < n; i++) {
        // 状态转移
        for (int _i = 0; _i < (1 << m); _i++)
            for (int l = 0; l < (1 << m); l++)
                if (!(l & (_i | vis[i] | vis[i + 1])))
                    for (int j = _i; ; j = (j - 1) & _i) {
                        if (!(j & (l | vis[i])))
                            cmax(f[(i & 1) ^ 1][j | vis[i] | l][vis[i + 1] | l], 
                                 f[i & 1][_i][j | vis[i]] + count(l));
                        if (!j) break;
                    }
        
        // 处理各种俄罗斯方块形状
        for (int _i = 0; _i < (1 << m); _i++)
            for (int j = 0; j < (1 << m); j++) {
                // L形、T形、直线形等俄罗斯方块的放置
                for (int _j = 0; _j < m; _j++) {
                    // 各种形状的检测和状态更新
                }
            }
    }
}
}

算法原理：

• 使用两行状态压缩表示当前行和下一行的覆盖情况
• 枚举所有可能的俄罗斯方块放置方式
• 通过状态转移更新最优解

复杂度分析

类型 A

• 网络流：$O((nm)^{1.5})$，对于 $n,m \leq 100$ 可接受

类型 B

• 大数乘法：$O(L \log L)$，其中 $L$ 是数字位数

类型 C

• 状态压缩DP：$O(n \cdot 4^m)$，对于 $m \leq 11$ 可接受

关键技巧

类型 A

1. 棋盘染色：利用二分图性质
2. 网络流建模：将匹配问题转化为最大流
3. Dinic算法：高效求解二分图匹配

类型 B

1. 公式推导：直接计算理论最大值
2. 大数处理：使用FFT加速大数乘法
3. 边界处理：考虑特殊方格的影响

类型 C

1. 状态设计：使用位运算表示覆盖状态
2. 形状枚举：处理多种俄罗斯方块形状
3. 滚动数组：优化空间复杂度

总结

本题的巧妙之处在于：

1. 多算法融合：根据不同类型采用完全不同的算法
2. 问题转化：将几何覆盖问题转化为图论或DP问题
3. 高效实现：针对数据范围选择合适算法
4. 状态压缩：利用位运算处理复杂状态

这种"分类讨论 + 算法选择"的策略在解决复杂问题时非常有效。