题目传送门: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; }