题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=1414
题号“1414”,还真的是把我做得“要死要死的”!做了一整天QAQ
Hash version:
#include<iostream>
#include<cstdio>
#include<cstring>
#define LL long long
using namespace std;
const int MX = 0;
const int MAXN = 2000+9;
unsigned int SEEDX = 37;
unsigned int SEEDY = 137;
int n,m; LL vout;
unsigned int px[2000+9],py[2000+9],mat[MAXN][MAXN],f[5][MAXN][MAXN];
inline int read(){
char c=getchar(); int ret=0;
while (c<'0'||c>'9') c=getchar();
while (c<='9'&&c>='0'){ret=ret*10+c-'0';c=getchar();}
return ret;
}
inline void init(){
m = read(); n = read(); vout = (unsigned int)n*m;
for (int j=1;j<=m;j++) {
for (int i=1;i<=n*2+1;i++) mat[i][j*2-1] = MX;
for (int i=1;i<=n;i++) mat[i*2][j*2] = read(), mat[i*2-1][j*2] = MX;
mat[n*2+1][j*2] = MX;
} for (int i=1;i<=n*2+1;i++) mat[i][m*2+1] = MX;
n = n*2+1; m = m*2+1;
}
inline void Hash_init(){
px[0] = 1; for (int i=1;i<=2001;i++) px[i] = SEEDX*px[i-1];
py[0] = 1; for (int i=1;i<=2001;i++) py[i] = SEEDY*py[i-1];
for (int i=n,g=1;i;i--,g++) for (int j=1,h=1;j<=m;j++,h++) f[1][i][j] = px[g]*py[h]*mat[i][j] + f[1][i+1][j] + f[1][i][j-1] - f[1][i+1][j-1];
for (int i=1,g=1;i<=n;i++,g++) for (int j=1,h=1;j<=m;j++,h++) f[2][i][j] = px[g]*py[h]*mat[i][j] + f[2][i-1][j] + f[2][i][j-1] - f[2][i-1][j-1];
for (int i=1,g=1;i<=n;i++,g++) for (int j=m,h=1;j;j--,h++) f[3][i][j] = px[g]*py[h]*mat[i][j] + f[3][i-1][j] + f[3][i][j+1] - f[3][i-1][j+1];
for (int i=n,g=1;i;i--,g++) for (int j=m,h=1;j;j--,h++) f[4][i][j] = px[g]*py[h]*mat[i][j] + f[4][i+1][j] + f[4][i][j+1] - f[4][i+1][j+1];
}
inline unsigned int Get_Hash(int t, int x1, int y1, int x2, int y2){
if (t == 1) return (f[1][x1][y1] + f[1][x2+1][y2-1] - f[1][x2+1][y1] - f[1][x1][y2-1]) * px[2001-(n-x1+1)] * py[2001-y1];
else if (t == 2) return (f[2][x1][y1] + f[2][x2-1][y2-1] - f[2][x2-1][y1] - f[2][x1][y2-1])* px[2001-x1] * py[2001-y1];
else if (t == 3) return (f[3][x1][y1] + f[3][x2-1][y2+1] - f[3][x2-1][y1] - f[3][x1][y2+1]) * px[2001-x1] * py[2001-(m-y1+1)];
else return (f[4][x1][y1] + f[4][x2+1][y2+1] - f[4][x2+1][y1] - f[4][x1][y2+1]) * px[2001-(n-x1+1)] * py[2001-(m-y1+1)];
}
inline bool judge(int x, int y, int len){
unsigned int t1 = Get_Hash(1,x,y,x+len,y-len),t2 = Get_Hash(2,x,y,x-len,y-len);
if (t1 != t2) return false;
t1 = Get_Hash(3,x,y,x-len,y+len);
if (t1 != t2) return false;
t2 = Get_Hash(4,x,y,x+len,y+len);
if (t1 != t2) return false;
else return true;
}
inline void solve(){
for (int j=1;j<=m;j++) for (int i=1;i<=n;i++) if ((i&1) + (j&1) != 1) {
int l=2,r=min(min(i-1,j-1),min(n-i,m-j)),ans=0,mid;
while (l <= r) {
mid = l + r >> 1;
if (judge(i,j,mid)) l = mid+1, ans = mid;
else r = mid-1;
}vout += ans/2;
}
}
int main(){
init(); Hash_init(); solve();
printf("%lld\n",vout);
return 0;
}
Manacher version:
#include<iostream>
#include<cstdio>
#include<cstring>
#define LL long long
using namespace std;
const int MAXN = 2000+9;
int mat[MAXN][MAXN],n,m,tmp[MAXN],ans[MAXN],que[MAXN],tot,pos[MAXN];
int res_x[MAXN][MAXN],res_y[MAXN][MAXN],sa_y[MAXN][MAXN],sa_x[MAXN][MAXN];
inline int read(){
char c=getchar(); int ret=0;
while (c<'0'||c>'9') c=getchar();
while (c<='9'&&c>='0'){ret=ret*10+c-'0';c=getchar();}
return ret;
}
inline void manacher(int lim){
int MX=0; ans[0] = 0;
for (int i=1;i<=lim;i++) {
if (MX+ans[MX] > i) ans[i] = min(MX+ans[MX]-i, ans[MX*2-i]);
else ans[i] = 0;
while (tmp[i+ans[i]+1] == tmp[i-ans[i]-1]) ans[i]++;
if (ans[i]+i > MX+ans[MX]) MX = i;
}
}
inline void DP(int lim){
tot = 0; pos[0] = 0; int sta = 0;
for (int i=1;i<=lim;i++) {
while (tot && ans[i] <= que[tot]) tot--; sta = min(sta, tot);
que[++tot] = ans[i]; pos[tot] = i; int w = sta;
while (w < tot && min(que[w],(i-pos[w-1])*2-1) <= min(que[w+1],(i-pos[w])*2-1)) w++;
sta = w; tmp[i] = min(que[w],(i-pos[w-1])*2-1);
}
}
int main(){
m = read(); n = read();
for (int j=1;j<=m;j++) for (int i=1;i<=n;i++) mat[i*2][j*2] = read();
n = n * 2 + 1; m = m * 2 + 1;
for (int i=1;i<=n;i++) {
for (int j=1;j<=m;j++) tmp[j] = mat[i][j]; tmp[0] = -1; tmp[m+1] = -2;
manacher(m);
for (int j=1;j<=m;j++) sa_y[i][j] = ans[j];
}
for (int j=1;j<=m;j++) {
for (int i=1;i<=n;i++) ans[i] = sa_y[i][j]*2+1;
DP(n);
for (int i=1;i<=n;i++) res_x[i][j] = tmp[i];
for (int i=1;i*2<=n;i++) swap(ans[i],ans[n-i+1]);
DP(n);
for (int i=1;i<=n;i++) res_x[i][j] = min(res_x[i][j],tmp[n-i+1]);
}
for (int j=1;j<=m;j++) {
for (int i=1;i<=n;i++) tmp[i] = mat[i][j]; tmp[0] = -1; tmp[n+1] = -2;
manacher(n);
for (int i=1;i<=n;i++) sa_x[i][j] = ans[i];
}
for (int i=1;i<=n;i++){
for (int j=1;j<=m;j++) ans[j] = sa_x[i][j]*2+1;
DP(m);
for (int j=1;j<=m;j++) res_y[i][j] = tmp[j];
for (int j=1;j*2<=m;j++) swap(ans[j],ans[m-j+1]);
DP(m);
for (int j=1;j<=m;j++) res_y[i][j] = min(res_y[i][j], tmp[m-j+1]);
}
LL vout = (n/2)*(m/2);
for (int j=1;j<=m;j++) for (int i=1;i<=n;i++) if ((i+j) % 2 == 0)
vout += max(0,(min(res_x[i][j]-1,res_y[i][j]-1)/2)/2);
printf("%lld\n",vout);
return 0;
}