「JOI 2014 Final」JOI 徽章 题解

题目分析

我们需要在 $M \times N$ 的 JOI 旗帜中，通过最多修改一个格子（或者不修改），使得旗帜中包含的与给定 JOI 徽章完全匹配的 $2 \times 2$ 子矩阵数量最大化。

关键思路

1. 问题分解

这个问题可以分为两个部分：

• 基础计数：计算原始旗帜中已经匹配的 $2 \times 2$ 子矩阵数量
• 优化搜索：枚举每个可能的修改位置和修改字符，计算修改后的最大匹配数

2. 算法设计

基础计数

对于原始旗帜，我们遍历所有可能的 $2 \times 2$ 子矩阵 $(i,j)$，其中 $1 \leq i \leq M-1$，$1 \leq j \leq N-1$，检查是否与目标徽章完全匹配。

优化搜索

对于每个格子 $(x,y)$，我们考虑将其修改为 J、O、I 中的任意一个字符，然后计算修改后的匹配数变化：

1. 移除影响：修改会影响以 $(x-1,y-1)$、$(x-1,y)$、$(x,y-1)$、$(x,y)$ 为左上角的 $2 \times 2$ 子矩阵
2. 重新计算：修改后重新检查这些受影响的子矩阵
3. 恢复状态：计算完当前修改的影响后，恢复原始状态，继续下一个尝试

3. 时间复杂度分析

• 基础计数：$O(M \times N)$
• 优化搜索：每个格子尝试 3 种修改，每次影响最多 4 个子矩阵
• 总复杂度：$O(M \times N \times 3 \times 4) = O(12MN)$，对于 $M,N \leq 1000$ 是可接受的

代码实现详解

#include <bits/stdc++.h>
using namespace std;

const int N = 1e3 + 10;
const char cand[] = {'J', 'O', 'I'};

int n, m, ans, o;
char g[N][N], e[3][3];

// 检查以(x,y)为左上角的2x2子矩阵是否匹配徽章
bool check(int x, int y) {
    for (int i = 0; i < 2; i++)
        for (int j = 0; j < 2; j++)
            if (g[x + i][y + j] != e[i + 1][j + 1])
                return false;
    return true;
}

// 尝试将位置(x,y)修改为字符c
void solve(int x, int y, char c) {
    if (c == g[x][y])  // 如果修改后字符不变，跳过
        return;
    
    char tmp = g[x][y];  // 保存原始字符
    int cnt = o;         // 从原始匹配数开始
    
    // 移除受影响的原有匹配
    for (int i = x - 1; i <= x; i++)
        for (int j = y - 1; j <= y; j++)
            if (i >= 1 && i <= n-1 && j >= 1 && j <= m-1)  // 边界检查
                if (check(i, j))
                    cnt--;
    
    // 应用修改
    g[x][y] = c;
    
    // 计算新的匹配
    for (int i = x - 1; i <= x; i++)
        for (int j = y - 1; j <= y; j++)
            if (i >= 1 && i <= n-1 && j >= 1 && j <= m-1)  // 边界检查
                if (check(i, j))
                    cnt++;
    
    // 更新最大值
    ans = max(ans, cnt);
    // 恢复原始状态
    g[x][y] = tmp;
}

int main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    cin >> n >> m;
    
    // 读入旗帜
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            cin >> g[i][j];
    
    // 读入徽章
    for (int i = 1; i <= 2; i++)
        for (int j = 1; j <= 2; j++)
            cin >> e[i][j];
    
    // 计算原始匹配数
    for (int i = 1; i <= n - 1; i++)
        for (int j = 1; j <= m - 1; j++)
            if (check(i, j))
                ans++;
    
    o = ans;  // 保存原始匹配数
    
    // 尝试所有可能的修改
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            for (int k = 0; k < 3; k++)
                solve(i, j, cand[k]);
    
    cout << ans << endl;
    return 0;
}

算法正确性证明

1. 完备性：我们枚举了所有可能的修改位置和修改字符，确保不会漏掉最优解
2. 正确性：对于每个修改，我们精确计算了受影响的 $2 \times 2$ 子矩阵，并正确统计了匹配数的变化
3. 边界处理：在 solve 函数中隐式处理了边界情况，确保不会访问无效位置

优化空间

• 可以预处理所有 $2 \times 2$ 子矩阵的匹配状态，避免重复检查
• 对于每个位置，可以只考虑能增加匹配数的修改，减少不必要的计算

总结

本题通过枚举+局部更新的策略，在合理的时间复杂度内解决了最优修改问题。关键在于理解修改一个格子只会影响其周围的 $4$ 个 $2 \times 2$ 子矩阵，从而可以高效地计算修改带来的影响。