题解 P2601 【[ZJOI2009]对称的正方形】

· · 题解

my_blog: http://blog.csdn.net/miaomiao\_ymxl/article/details/54667726

  1. 把矩阵变成(2n-1)*(2m-1)的，即在数字中间补上0

2.（Manacher算法）定义lx[][], ly[][]数组分别表示对于每个矩阵中的数，它的左右（上下）的最长延伸回文串的长度

3.定义left[][]数组表示对于每个矩阵中的数，以它为中心，最多可以向左边延伸的半个矩形（保证上下回文）的长度（长度应小于所有在范围内的ly[][]的最小值）

  1. 那么对于left[i]数组，它的左边界(j-left[i])是递增不减的，所以可以结合RMQ在O(n2)的时间内求出来

  2. 所以right[][], up[][], down[][]数组定义类似

  3. 那么最终的答案为min(left[][], right[][], up[][], down[][])的和再减去包含０的部分！

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;
#define LL long long
#define pb push_back
#define Set(a, v) memset(a, v, sizeof(a))
#define For(i, a, b) for(int i = (a); i <= (int)(b); i++)
#define Forr(i, a, b) for(int i = (a); i >= (int)(b); i--)
#define LOG (10+5)
#define MAXN (2000+5)
int f[MAXN][MAXN];
int map[MAXN][MAXN], lx[MAXN][MAXN], ly[MAXN][MAXN];
void read(int &x){
    char ch = getchar();
    while(ch < '0' || ch > '9') ch = getchar();
    x = 0;
    while(ch >= '0' && ch <= '9'){
        x = x*10+ch-'0';
        ch = getchar();
    }
}
int s[MAXN], Min[MAXN][LOG], Log[MAXN];
void Manacher(int *len, int n){
    int p0 = 0;
    For(i, 1, n){
        int pos = p0+len[p0];
        if(pos > i && len[2*p0-i]<(pos-i)) len[i] = len[2*p0-i];
        else{
            if(pos > i) len[i] = pos-i;
            while(i+len[i] < n && i-len[i] > 1 && s[i+len[i]+1]==s[i-len[i]-1]) ++len[i];
            p0 = i;
        }
    }
}
void makeRMQ(int x[MAXN][MAXN], int h, int n){
    Set(Min, 0x3f);
    For(i, 1, n) Min[i][0] = x[i][h];
    For(j, 1, 11) For(i, 1, n){
        if((i+(1<<j)-1) > n) break;
        Min[i][j] = min(Min[i][j-1], Min[i+(1<<(j-1))][j-1]);
    }
}
int query(int L, int R){
    int k = Log[R-L+1];
    return min(Min[L][k], Min[R-(1<<k)+1][k]);
}
int main(){
    int n, m;
    read(n); read(m);
    For(i, 2, n) Log[i] = Log[i>>1]+1;
    For(i, 1, n) For(j, 1, m) read(map[i*2-1][j*2-1]);
    n = n*2-1, m = m*2-1;
    For(i, 1, n){
        For(j, 1, m) s[j] = map[i][j];
        Manacher(lx[i], m);
    }
    For(i, 1, m){
        For(j, 1, n) s[j] = map[j][i];
        Manacher(ly[i], n);
    }
    Set(f, 0x3f);
    For(i, 1, n){
        makeRMQ(ly, i, m);
        int v = 1;
        For(j, 1, m){
            while(v<j && query(v, j) < (j-v)) v++;
            f[i][j] = min(f[i][j], j-v);
        }
        v = m;
        Forr(j, m, 1){
            while(v>j && query(j, v) < (v-j)) v--;
            f[i][j] = min(f[i][j], v-j);
        }
    }
    For(i, 1, m){
        makeRMQ(lx, i, n);
        int v = 1;
        For(j, 1, n){
            while(v<j && query(v, j) < (j-v)) v++;
            f[j][i] = min(f[j][i], j-v);
        }
        v = n;
        Forr(j, n, 1){
            while(v>j && query(j, v) < (v-j)) v--;
            f[j][i] = min(f[j][i], v-j);
        }
    }
    int ans = 0;
    For(i, 1, n) For(j, 1, m){
        if((i&1)&&(j&1)) ans += (f[i][j]>>1)+1;
        else if(!(i&1) && !(j&1)) ans += (f[i][j]+1)>>1;
    }
    printf("%d\n", ans);
    return 0;
}