题目地址：洛谷：【P2601】[ZJOI2009]对称的正方形 – 洛谷、BZOJ：Problem 1414. — [ZJOI2009]对称的正方形

题目描述

Orez很喜欢搜集一些神秘的数据，并经常把它们排成一个矩阵进行研究。最近，Orez又得到了一些数据，并已经把它们排成了一个n行m列的矩阵。通过观察，Orez发现这些数据蕴涵了一个奇特的数，就是矩阵中上下对称且左右对称的正方形子矩阵的个数。 Orez自然很想知道这个数是多少，可是矩阵太大，无法去数。只能请你编个程序来计算出这个数。

题意简述

求上下左右对称的正方形子矩阵个数。

输入输出格式

输入格式：
文件的第一行为两个整数n和m。接下来n行每行包含m个正整数，表示Orez得到的矩阵。

输出格式：
文件中仅包含一个整数answer，表示矩阵中有answer个上下左右对称的正方形子矩阵。

输入输出样例

输入样例#1：

5 5
4 2 4 4 4 
3 1 4 4 3 
3 5 3 3 3 
3 1 5 3 3 
4 2 1 2 4 

输出样例#1：

27

说明

数据范围
对于30%的数据 n，m≤100
对于100%的数据 n，m≤1000 ，矩阵中的数的大小≤10^9

题解

参考资料：题解 P2601 【[ZJOI2009]对称的正方形】 – Miaomiao’s Home – 洛谷博客
本题可以先对矩阵元素间插入数字0以便处理奇偶回文的情况，对每行每列跑一遍Manacher，统计出回文半径。
对于每个格子，上下左右找一遍以该格子为顶点的区间回文半径不大于区间长度的最大区间，这些区间长度的最小值就是这个格子为中心的最大对称正方形，而消除插入0的影响后的值就是这个格子对答案的贡献。
思路很简单也很暴力，算法$O(n^2 \log n)$，但是写出来常数挺大的，而且其实不太好写。

代码

// Code by KSkun, 2018/6
#include <cstdio>
#include <cctype>
#include <cstring>

#include <algorithm>

typedef long long LL;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2)
        ? EOF : *p1++;
}

inline LL readint() {
    register LL res = 0, neg = 1; register char c = fgc();
    for(; !isdigit(c); c = fgc()) if(c == '-') neg = -1;
    for(; isdigit(c); c = fgc()) res = (res << 1) + (res << 3) + c - '0';
    return res * neg;
}

inline int min(int a, int b) {
    return a < b ? a : b;
}

const int MAXN = 2005;

int n, m, a[MAXN][MAXN], lh[MAXN][MAXN], lv[MAXN][MAXN], t[MAXN];

inline void manacher(int n, int *arr, int *len) {
    int id = 0, mx = 0;
    for(register int i = 1; i <= n; i++) {
        if(i < mx) len[i] = min(len[(id << 1) - i], mx - i);
        else len[i] = 1;
        while(arr[i - len[i]] == arr[i + len[i]] 
            && i - len[i] >= 1 && i + len[i] <= n) len[i]++;
        if(mx < i + len[i]) {
            id = i; mx = i + len[i];
        }
    }
}

int Log[MAXN], mn[MAXN][12], ans[MAXN][MAXN];

inline void initst(int n, int x, int arr[][MAXN]) {
    for(register int i = 1; i <= n; i++) {
        mn[i][0] = arr[i][x] - 1;
    }
    for(register int j = 1; j < 12; j++) {
        for(register int i = 1; i <= n; i++) {
            if(i + (1 << j) - 1 > n) break;
            mn[i][j] = min(mn[i][j - 1], mn[i + (1 << (j - 1))][j - 1]);
        }
    }
}

inline int query(int x, int y) {
    int lg = Log[y - x + 1];
    return min(mn[x][lg], mn[y - (1 << lg) + 1][lg]);
}

int main() {
    for(register int i = 2; i < MAXN; i++) {
        Log[i] = Log[i >> 1] + 1;
    }
    n = readint(); m = readint();
    for(register int i = 1; i <= n; i++) {
        for(register int j = 1; j <= m; j++) {
            a[(i << 1) - 1][(j << 1) - 1] = readint();
        }
    }
    n = (n << 1) - 1; m = (m << 1) - 1;
    for(register int i = 1; i <= n; i++) {
        for(register int j = 1; j <= m; j++) {
            t[j] = a[i][j];
        }
        manacher(m, t, lh[i]);
    }
    for(register int i = 1; i <= m; i++) {
        for(register int j = 1; j <= n; j++) {
            t[j] = a[j][i];
        }
        manacher(n, t, lv[i]);
    }
    memset(ans, 0x3f, sizeof(ans));
    for(register int i = 1; i <= n; i++) {
        initst(m, i, lv);
        int t = 1;
        for(register int j = 1; j <= m; j++) {
            while(t < j && query(t, j) < j - t) t++;
            ans[i][j] = min(ans[i][j], j - t);
        }
        t = m;
        for(register int j = m; j >= 1; j--) {
            while(t > j && query(j, t) < t - j) t--;
            ans[i][j] = min(ans[i][j], t - j);
        }
    }
    for(register int i = 1; i <= m; i++) {
        initst(n, i, lh);
        int t = 1;
        for(register int j = 1; j <= n; j++) {
            while(t < j && query(t, j) < j - t) t++;
            ans[j][i] = min(ans[j][i], j - t);
        }
        t = n;
        for(register int j = n; j >= 1; j--) {
            while(t > j && query(j, t) < t - j) t--;
            ans[j][i] = min(ans[j][i], t - j);
        }
    }
    int res = 0;
    for(register int i = 1; i <= n; i++) {
        for(register int j = 1; j <= m; j++) {
            if((i & 1) && (j & 1)) res += (ans[i][j] >> 1) + 1;
            else if(!(i & 1) && !(j & 1)) res += (ans[i][j] + 1) >> 1;
        }
    }
    printf("%d", res);
    return 0;
}