首页 > 代码库 > [luoguP2601] [ZJOI2009]对称的正方形（二维Hash + 二分 || Manacher）
[luoguP2601] [ZJOI2009]对称的正方形（二维Hash + 二分 || Manacher）
传送门
很蒙蔽，不知道怎么搞。
网上看题解有说可以哈希+二分搞，也有的人说用Manacher搞，Manacher是什么鬼？以后再学。
对于这个题，可以从矩阵4个角hash一遍，然后枚举矩阵中的点，再二分半径。
但是得考虑边的长度为奇偶所带来的影响。
比如
1 1
1 1
这个边数为偶数的矩阵显然没法搞。
所以得在矩阵中插入0，
变成
0 0 0 0 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 { 11 int x = 0, f = 1; 12 char ch = getchar(); 13 for(; !isdigit(ch); ch = getchar()) if(ch == ‘-‘) f = -1; 14 for(; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + ch - ‘0‘; 15 return x * f; 16 } 17 18 inline int min(int x, int y) 19 { 20 return x < y ? x : y; 21 } 22 23 inline bool pd(int x, int y, int l) 24 { 25 UI t, h; 26 h = sum[0][x + l - 1][y + l - 1] 27 - sum[0][x - l][y + l - 1] * base1[l + l - 1] 28 - sum[0][x + l - 1][y - l] * base2[l + l - 1] 29 + sum[0][x - l][y - l] * base1[l + l - 1] * base2[l + l - 1]; 30 t = sum[1][x + l - 1][y - l + 1] 31 - sum[1][x - l][y - l + 1] * base1[l + l - 1] 32 - sum[1][x + l - 1][y + l] * base2[l + l - 1] 33 + sum[1][x - l][y + l] * base1[l + l - 1] * base2[l + l - 1]; 34 if(h ^ t) return 0; 35 t = sum[2][x - l + 1][y + l - 1] 36 - sum[2][x + l][y + l - 1] * base1[l + l - 1] 37 - sum[2][x - l + 1][y - l] * base2[l + l - 1] 38 + sum[2][x + l][y - l] * base1[l + l - 1] * base2[l + l - 1]; 39 if(h ^ t) return 0; 40 t = sum[3][x - l + 1][y - l + 1] 41 - sum[3][x + l][y - l + 1] * base1[l + l - 1] 42 - sum[3][x - l + 1][y + l] * base2[l + l - 1] 43 + sum[3][x + l][y + l] * base1[l + l - 1] * base2[l + l - 1]; 44 if(h ^ t) return 0; 45 return 1; 46 } 47 48 inline int work(int i, int j) 49 { 50 int mid, s = 0, x = 1, y = min(min(i, n - i + 1), min(j, m - j + 1));//二分半径 51 while(x <= y) 52 { 53 mid = (x + y) >> 1; 54 if(pd(i, j, mid)) s = mid, x = mid + 1; 55 else y = mid - 1; 56 } 57 return s; 58 } 59 60 int main() 61 { 62 int i, j, k, x; 63 n = read(); 64 m = read(); 65 n = n << 1 | 1; 66 m = m << 1 | 1; 67 for(i = 2; i <= n; i += 2) 68 for(j = 2; j <= m; j += 2) 69 { 70 x = read(); 71 for(k = 0; k < 4; k++) sum[k][i][j] = x; 72 } 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 }
Manacher的话，学完再搞吧。
[luoguP2601] [ZJOI2009]对称的正方形（二维Hash + 二分 || Manacher）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。