Question

2024牛客寒假算法基础集训营6 K 错综的统一

一个矩阵仅由 "r"，“e”，“d” 组成

一个矩阵区域是美丽的，当且仅当：在矩形区域内，任意横向或纵向取一个长度大于 \(1\) 的连续字串是，该字符串都不是回文的

现在有 \(Q\) 次询问，每次给定一个矩阵，问最少修改多少字符（字符只能修改 "r"，“e”，“d”）可以使得该区域为 “美丽的”

Solution

枚举的力量

单独考虑回文很难，但是我们发现实际上非回文串很少

就拿一行来说，回文串就只有：

• "redredred......"
• "edredredr......"
• "dredredre......"
• "derderder......"
• "erderderd......"
• "rderderde......"

第二行可以是第一行向左或者向右移动一个单位来构造

也就是说，合法的非回文矩阵就 12 种，枚举每一种矩阵，找到最小的修改次数

如何快速求出一个矩阵内的修改次数，只需要利用二维前缀和即可

注意：\(2\times 2\) 的矩阵需要特判

Code

#include<bits/stdc++.h>
#define endl '\n'

const int INF = 0x3f3f3f3f;
using namespace std;

vector<string> list_s = {"red", "edr", "dre", "der" , "erd", "rde"};

int main() {
    int n, m , q;
    cin >> n >> m >> q;
    vector<vector<char>> a(n + 1, vector<char>(m + 1));
    
    for (int i = 1; i <= n; i++) 
        for (int j = 1; j <= m; j++)
            cin >> a[i][j];
    
    vector<vector<vector<char> > > p;
    for (auto &s : list_s) {
        vector<vector<char> > t(n + 1, vector<char>(m + 1));
        for (int i = 1; i <= n; i += 1)
            for (int j = 1; j <= m; j += 1)
                t[i][j] = s[((i - 1) + (j - 1)) % 3];
        p.push_back(t);

        for (int i = 1; i <= n; i += 1)
            for (int j = 1; j <= m; j += 1)
                t[i][j] = s[(((i - 1) - (j - 1)) % 3 + 3) % 3];
        p.push_back(t);
    }

    vector<vector<vector<int> > > sum;
    for (auto &t : p) {
        vector<vector<int> > s(n + 1, vector<int>(m + 1, 0));
        for (int i = 1; i <= n; i += 1)
            for (int j = 1; j <= m; j += 1)
                s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + (t[i][j] != a[i][j]);
        sum.push_back(s);
    }

    while (q --) {
        int x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2;
        int ans = INF;
        if (x2 - x1 + 1 == 2 && y2 - y1 + 1 == 2) {
            for (auto &s : list_s) {
                char c1 = s[0], c2 = s[1];
                int now = 0;
                now += (a[x1][y1] != c1);
                now += (a[x1][y2] != c2);
                now += (a[x2][y1] != c2);
                now += (a[x2][y2] != c1);
                ans = min(ans, now);
            }
        }
        if(true) {
            for (auto &s : sum) {
                int now = s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1];
                ans = min(ans, now);
            }
        }
        cout << ans << endl;
    }

    return 0;
}