题解：P9646 [SNCPC2019] Paper-cutting

· · 题解

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

分析

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

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

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

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

解答

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

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

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

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

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

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

实现细节

代码实现

上述就是我做这道题时的一些思考，供大家参考。其他就没什么大问题了的，最后的总复杂度就是 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;
}

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