自动搬运

查看原文

来自洛谷，原作者为

	jjsnam I'm no good at goodbyes.

搬运于2025-08-24 22:50:24，当前版本为作者最后更新于2025-02-04 15:00:09，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

蛮有意思的一道题，但是也不是很难想（因为我自己一次切掉了），很久没有写过题解了，于是这次想写一下。

分析

根据题目描述和样例解释，我们不难发现，答案的求解方式应该是把输入给出的 $01$ 矩阵经过若干次折叠（需要折叠部分相对折叠轴完全对称），然后统计出值为 $0$ 的连通块的个数。所有这样操作后的结果的最小值即为答案。

下图应该能帮助理解解题步骤：

那么按照上面的分析，这道题目的解法大致可以以下几个部分：

1. 找对称矩阵块和对称轴
2. 确定进行几次怎样的折叠
3. 统计折叠最后所剩图形中 $0$ 连通块的总数

解答

我们来看看上述三个部分应该怎样解决。

第三个部分是最容易的，连通块用一个 BFS 即可解决。

第一个部分呢？对称轴的横竖是类似的，我们现在来看竖对称轴的情况：

参照上文图片容易发现，对称矩阵块的每一行单独构成了一个回文串，因而我们可以知道，每个竖对称轴所管的对称矩阵块宽度就是每一行以该轴为中心的回文串的半径的最小值。对每一行（横对称轴则为列）跑 Manacher 算法即可解决。

第二个部分是本题比较难的一点。我们不知道应该怎么折叠，也不知道应该折叠多少，如果枚举的话方案数太多肯定不是我们想要的复杂度。因而我们需要深入思考折叠操作，也就是解决下面两个个问题：

• 能折叠的情况下，折叠一定比不折叠更优吗？

  对。最后答案的统计来自于剩余图形的 $0$ 连通块总数，因而我们只需要考虑折叠前后 $0$ 联通块的变化：

  • 对于被折叠轴穿过的连通块：折叠后连通块面积减半，但是不影响连通块总数。
  • 对于不被折叠轴穿过的连通块：如果它在折叠后被保留，那么连通块总数不变；如果他在折叠后被折到背面（也就是被舍弃）那么连通块总数会减少。

  综上，折叠一定不会让连通块总数增多。故而能折叠就折叠的策略，既方便我们代码实现，也不会影响我们找到最优解。

• 横折叠和竖折叠会相互影响吗？

  不会。还是只考虑竖折叠轴的情况，结合下图：

  

  从竖折叠轴考虑，蓝色的横折叠的折叠轴两侧的 $01$ 矩阵是相同的，也就是他们提供给竖折叠的回文串半径信息是相同的，蓝色折叠不折叠都会保留一份完整的回文串半径信息，不会影响竖折叠对于对称矩阵块的决策。

  因而我们在实现的时候就可以采用先把一个方向全部折叠，再折另一个方向的策略，这也是易于我们代码实现的。

这样三个部分就比较明了了，再来考虑一些代码实现的细节。

实现细节

• 在实现时，我们应该保留一个完整的矩形块，因而我们可以选择在折叠时都删除偏向外侧的那层矩阵块。如下图：

  因而我们可以设置四个指针代表被保留的矩阵块的横纵边界，折叠时只需要把相应指针移到对称轴的位置即可不断进行『折叠』操作。

• 根据题目描述，可以发现折叠的对称轴，也就是回文串的对称中心，都是数字之间而不是数字，也就是说我们实现 Manacher 算法时只需要求解偶回文串即可。

• 有了每个折叠轴对应的最大对称矩阵块，根据上面的实现准备，什么条件需要被满足来保证折叠的合法性和有效性？（以竖左边界为例）

  • 其中一个最大对称块需要包含从竖左边界到折叠轴的所有部分。
  • 折叠轴需要在竖左右边界的中间左侧（否则移动竖左边界的操作是不合法的，因为此时左侧的矩阵包含了除被折叠的对称块以外更多的矩阵部分）。

• 还是以竖左边界为例，我们在枚举对称轴的时候应该从左往右枚举还是从右往左枚举？

  从左往右，广泛来说就是由边界向中心移动的方向。这是因为大的折叠后保留的矩阵部分不会被之前进行的小折叠所影响，同时小折叠的进行也有可能导致新的大折叠出现。

  e.g. 011000010 现在从左看最大的折叠应该是 01|1000010->1000010（另一个更大的由于超出了折叠轴在左半部分的限制，是不能被考虑的），但是如果将小折叠折上，就会有 01|1000010->1000010->100|0010->0010。

• 由于没有明确的 $n, m$ 范围，因而本题用动态数组是一个合理的选择。

代码实现

上述就是我做这道题时的一些思考，供大家参考。其他就没什么大问题了的，最后的总复杂度就是 $O(\sum{n\times m})$，下面是代码：

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <queue>

using namespace std;
typedef pair<int, int> PII;
const int INF = 0x3f3f3f3f;
const int dx[] = {1, 0, -1, 0};
const int dy[] = {0, 1, 0, -1};

int n, m, T;

void manacher(string s, vector<int> &p){// 第一部分
    int len = s.size();
    int mid = 0, R = 0;
    for (int i = 0; i < len; i ++){
        int j = mid * 2 - i;
        if (i < R){
            p[i] = min(p[j], R - i);
        }
        else p[i] = 0;
        while (i - p[i] >= 0 && i + p[i] + 1 < len && s[i - p[i]] == s[i + p[i] + 1]) p[i] ++;
        if (i + p[i] > R){
            mid = i, R = i + p[i];
        }
    }
}

void BFS(int ux, int uy, int xl, int xr, int yl, int yr, vector< vector<bool> > &vis, string *s){// 第三部分
    queue<PII> q;
    q.push(make_pair(ux, uy));
    while (!q.empty()){
        auto [ux, uy] = q.front();
        q.pop();
        vis[ux][uy] = true;
        for (int i = 0; i < 4; i ++){
            int vx = ux + dx[i], vy = uy + dy[i];
            if (vx < xl || vx > xr || vy < yl || vy > yr || vis[vx][vy] || s[vx][vy] == '1') continue;
            q.push(make_pair(vx, vy));
        }
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> T;
    while (T --){
        cin >> n >> m;
        string s[n], t[m];
        for (int i = 0; i < n; i ++){
            cin >> s[i];
        }
        for (int i = 0; i < m; i ++){
            for (int j = 0; j < n; j ++){
                t[i].push_back(s[j][i]);
            }
        }
        vector< vector<int> > rowp(n, vector<int>(m)), colp(m, vector<int>(n)); // 行、列manacher的p数组
        for (int i = 0; i < n; i ++){
            manacher(s[i], rowp[i]);
        }
        for (int i = 0; i < m; i ++){
            manacher(t[i], colp[i]);
        }

        int xl = 0, xr = n - 1, yl = 0, yr = m - 1;// 横左、横右、竖左、竖右边界
        // 求横左
        for (int i = xl; i * 2 < xl + xr; i ++){
            int p = INF;
            for (int j = 0; j < m; j ++){
                p = min(p, colp[j][i]);
            }
            if (i - p + 1 > xl) continue;
            xl = i + 1;
        }
        // 求横右
        for (int i = xr; i * 2 >= xl + xr - 1; i --){
            int p = INF;
            for (int j = 0; j < m; j ++){
                p = min(p, colp[j][i]);
            }
            if (i + p < xr) continue;
            xr = i;
        }
        // 求竖左
        for (int i = yl; i * 2 < yl + yr; i ++){
            int p = INF;
            for (int j = 0; j < n; j ++){
                p = min(p, rowp[j][i]);
            }
            if (i - p + 1 > yl) continue;
            yl = i + 1;
        }
        // 求竖右
        for (int i = yr; i * 2 >= yl + yr - 1; i --){
            int p = INF;
            for (int j = 0; j < n; j ++){
                p = min(p, rowp[j][i]);
            }
            if (i + p < yr) continue;
            yr = i;
        }

        // 统计答案
        vector< vector<bool> > vis(n, vector<bool>(m));
        int ans = 0;
        for (int i = xl; i <= xr; i ++){
            for (int j = yl; j <= yr; j ++){
                if (s[i][j] == '1' || vis[i][j]) continue;
                ans ++, BFS(i, j, xl, xr, yl, yr, vis, s);
            }
        }

        cout << ans << endl;
    }

    return 0;
}

谢谢观看，有任何疑问也欢迎与我讨论！