[luoguP2601] [ZJOI2009]对称的正方形（二维Hash + 二分 || Manacher）

传送门

很蒙蔽，不知道怎么搞。

网上看题解有说可以哈希+二分搞，也有的人说用Manacher搞，Manacher是什么鬼？以后再学。

对于这个题，可以从矩阵4个角hash一遍，然后枚举矩阵中的点，再二分半径。

但是得考虑边的长度为奇偶所带来的影响。

比如

1 1

1 1

这个边数为偶数的矩阵显然没法搞。

所以得在矩阵中插入0，

变成

0 0 00 0

0 1 0 1 0

0 0 0 0 0

0 1 0 1 0

0 0 0 0 0

具体操作就看代码好了。

然后只枚举 行 + 列 为偶数的点就行。

注意 用 unsigned long long 会超时和超空间，数据允许用 unsigned int

——代码

1 #include <cstdio> 2 #include <iostream> 3 #define UI unsigned int 4 5 const int MAXN = 2010, bs1 = 19260817, bs2 = 20011001; 6 int n, m, ans; 7 UI sum[4][MAXN][MAXN], base1[MAXN], base2[MAXN]; 8 9 inline int read() 10 17 18 inline int min(int x, int y) 19 22 23 inline bool pd(int x, int y, int l) 24 47 48 inline int work(int i, int j) 49 57 return s; 58 } 59 60 int main() 61 73 base1[0] = base2[0] = 1; 74 for(i = 1; i <= n; i++) base1[i] = base1[i 1] * bs1; 75 for(i = 1; i <= m; i++) base2[i] = base2[i 1] * bs2; 76 for(i = 1; i <= n; i++) 77 for(j = 1; j <= m; j++) 78 sum[0][i][j] += sum[0][i 1][j] * bs1; 79 for(i = 1; i <= n; i++) 80 for(j = 1; j <= m; j++) 81 sum[0][i][j] += sum[0][i][j 1] * bs2; 82 for(i = 1; i <= n; i++) 83 for(j = m; j; j) 84 sum[1][i][j] += sum[1][i 1][j] * bs1; 85 for(i = 1; i <= n; i++) 86 for(j = m; j; j) 87 sum[1][i][j] += sum[1][i][j + 1] * bs2; 88 for(i = n; i; i) 89 for(j = 1; j <= m; j++) 90 sum[2][i][j] += sum[2][i + 1][j] * bs1; 91 for(i = n; i; i) 92 for(j = 1; j <= m; j++) 93 sum[2][i][j] += sum[2][i][j 1] * bs2; 94 for(i = n; i; i) 95 for(j = m; j; j) 96 sum[3][i][j] += sum[3][i + 1][j] * bs1; 97 for(i = n; i; i) 98 for(j = m; j; j) 99 sum[3][i][j] += sum[3][i][j + 1] * bs2; 100 for(i = 1; i <= n; i++) 101 for(j = 1; j <= m; j++) 102 if((i ^ j ^ 1) & 1) 103 ans += work(i, j) >> 1; 104 printf("%d\n", ans); 105 return 0; 106 }
View Code

Manacher的话，学完再搞吧。

上一篇：[luoguP1970] 花匠（DP）

下一篇：[BZOJ3555] [Ctsc2014]企鹅QQ（Hash）

---

二分 hash Manacher